MyException - 我的异常网
当前位置:我的异常网» 数据结构与算法 » 求解释,中序遍历二叉树的非递归算法,该怎么解决

求解释,中序遍历二叉树的非递归算法,该怎么解决

www.MyException.Cn  网友分享于:2013-01-02  浏览:5次
求解释,中序遍历二叉树的非递归算法
中序遍历二叉树的非递归算法
 void InOrderTraverse(BiTree bt){
 //二叉树bt采用二叉链表存储,对bt进行中序遍历
   if(bt){
     InitStack(S);   Push(S, bt);       //根指针进栈
     while(!StackEmpty(S)) {
       while(GetTop(S,p)&&p) 
         Push(S, p->lchild);    //向左一直走到尽头
       Pop(S, p); //空指针退栈
      if(! StackEmpty(S))
        {  Pop(S,p);  printf(p->data); Push(S, p->rchild);     }
     } //while
   } //if
 } // InOrderTraverse

最后面Push(S, p->rchild);这一句,前面已经到了最左下角的了(假设存在这个左孩子),printf这个data之后,将rchild入栈,因为没有右孩子,入进去的是NULL,Pop出来,P就是NULL,NULL打印,再入栈右孩子。我蒙圈了,求解释这个if循环。谢谢了,老师讲的给忘了,晚上自习看不明白了。


------解决方案--------------------
中序遍历思路应该是很明晰的啊:对于结点P,一直往左走,并把经过的结点都压栈里面,直到最左边。想想,此时这个结点是不是应该第一个访问(因为它没有左子树了)。访问这个结点,然后,判断它的右子树,如果不为空,则用同样的方式处理它的右子树。如果为空,那就从栈里面弹出来一个结点得了,栈为空就结束了。
至于代码实现,可以有两种方式:(这是我以前写的两种实现方式)
//中序遍历(非递归)
template<class T>
void mediumOrderVisitNoRecursion(Node<T>* root)
{
//遇到一非空结点,则把其压入栈中,之后遍历其左子树
//结点为空,则从栈中弹出一结点,并访问
//遍历该结点的右子树
stack<Node<T>*>sta;
Node<T>* point=root;

//空树则返回
if(root==NULL){return;}

while(!sta.empty() 
------解决方案--------------------
 point!=NULL)
{
if(point!=NULL)
{
sta.push(point);
point=point->getLeft();
}
else
{
point=sta.top();
visit(point);
sta.pop();
point=point->getRight();
}
}
}

//中序遍历(非递归)(另一种写法)
template<class T>
void mediumOrderVisitNoRecursion_1(Node<T>* root)
{
//遇到一非空结点,则把其压入栈中,往左继续走,直至为空(走到最左侧结点)
//从栈中弹出(若栈不空)一个结点访问
//遍历该结点的右子树
stack<Node<T>*>sta;
Node<T>* point=root;

//空树则返回
if(root==NULL){return;}

while(!sta.empty() 
------解决方案--------------------
 point)
{
while(point) //一直往右遍历,直到最左边的结点
{
sta.push(point);
point=point->getLeft();
}
point=NULL;
if(!sta.empty()) //栈不为空,取出栈顶值,访问。其实就是访问的最左边的结点
{
point=sta.top();
visit(point);
sta.pop();
}
point=point->getRight();
}

while(!sta.empty() 
------解决方案--------------------
 point!=NULL)
{
if(point!=NULL)
{
sta.push(point);
point=point->getLeft();
}
else
{
point=sta.top();
visit(point);
sta.pop();
point=point->getRight();
}
}
}

文章评论

软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有