中序遍历【递归算法】和【非递归算法】

2019/11/19

二叉树中序遍历的非递归算法 

void InOrder(BiTree T){
    if(T!=NULL){
        InOrder(T->lchild);//递归遍历左子树
        visit(T);　　　　　　//访问根节点
        InOrder(T->rchild);//递归遍历左子树
    }
}

二叉树中序遍历的非递归算法 

 1 void InOrder2(BitTree T){
 2 //二叉树中序遍历的非递归算法，算法需要借助一个栈
 3     InitStack(S);                   //初始化栈
 4     BitTree p=T;                    //p是遍历指针
 5     while( p || !IsEmpty(S) ){
 6         if(p){                      //根指针进栈，遍历左子树。
 7             Push(S,p);              //每遇到非空二叉树先向左走。
 8             p=p->lchild;
 9         }
10         else{                       //根指针退栈，访问根节点，遍历右子树。
11             Pop(S,p);               //退栈。
12             visit(p);               //访问根节点。
13             p=p->rchild;            //再向右子树走
14         }
15     }
16 }