注册 登录
编程论坛 数据结构与算法

二叉树非递归遍历算法

朔州小子 发布于 2013-07-11 15:05, 854 次点击
Status InOrderTracerse(BiTree T,Status (* Visit)(TElemType e)//中序二叉树非递归遍历
{
 InitStack(S); Push(S,T);
 while(!StackEmpty(s))
 {while(GetTop(S,p)&&p) Push(S,p->lchild);//向左走到尽头
  Pop(S,p);                              //空指针退栈
  if(!StackEmpty(S))                    //访问结点,向右一步
   {Pop(S,p);
    if(!Visit(p->data)) return ERROR;
    Push(S,p->rchild);
    }//if
  }//while
 return OK;
}//InOrderTraverse
算法中 if(!StackEmpty(S))有啥作用?为啥不省略?
3 回复
#2
yuccn2013-07-11 23:05
不是有注释吗?接点要的右子接点也要遍历的,非空则保存一下右接点。。

#3
beyondyf2013-07-14 20:37
用自建栈代替程序栈,本质上和递归没什么区别。

你可以尝试给结点增加一个指向父结点的指针,这才是真正摆脱了栈的遍历。

另外建议学学线索二叉树。
#4
bo6305401322013-07-15 17:41
沒看明白呢...什么時候才可以看懂這段文字哦...
1