二叉树非递归遍历算法思悟

本文深入分析二叉树非递归遍历算法实现背后的思想并给出实现代码；

（这是我自己实现的一套数据结构API，包括链表、栈、队列、树、图等内容，完善ing~）

一、递归算法分析

先序遍历

对于先序遍历二叉树A，首先访问A的根结点；然后递归访问A的左子树AL；然后递归访问A的右子树AR；

public void visitedByPreOrderRecursive(ITreeVisitor
     
       visitor){    //进入    visitor.visitNode(this);//访问    if(leftTree!=null){
    //入栈        leftTree.visitedByPreOrderRecursive(visitor);//进入左子树    }//出栈    if(rightTree!=null){
    //转向        rightTree.visitedByPreOrderRecursive(visitor);//再进入    }}

中序遍历

对于中序遍历二叉树A，首先递归访问A的左子树AL；然后访问A的根结点；然后递归访问A的右子树AR；

public void visitedByInOrderRecursive(ITreeVisitor
     
       visitor){    //进入    if(leftTree!=null){
    //入栈        leftTree.visitedByInOrderRecursive(visitor);//进入左子树    }//出栈    visitor.visitNode(this);//访问    if(rightTree!=null){
    //转向        rightTree.visitedByInOrderRecursive(visitor);//再进入    }}

后序遍历

对于后序遍历二叉树A，首先递归访问A的左子树；然后递归访问A的右子树；然后访问A的根结点；

public void visitedByPostOrderRecursive(ITreeVisitor
     
       visitor){    //进入    if(leftTree!=null){
    //入栈        leftTree.visitedByPostOrderRecursive(visitor);//进入左子树    }//出栈    if(rightTree!=null){
    //入栈        rightTree.visitedByPostOrderRecursive(visitor);//进入右子树    }//出栈    visitor.visitNode(this);//访问}

总结

递归算法的好处显而易见，逻辑清晰，结构鲜明，实现简单；

递归算法的主要问题在于频繁的函数调用，增加了系统负担；每调用一次函数，系统都将进行如下操作：保留调用者函数的现场，包括（但不限于）下一条指令的位置、CPU寄存器的值、调用者函数的堆栈情况；为被调用函数进行参数入栈、分配堆栈空间等；当被调用函数返回时，又要还原调用函数的现场，撤销为被调用函数分配的资源；当树比较庞大时，系统负担就很重了（系统做了很多与执行算法本身指令无关的事情），效率自然低下；

事实上，调用函数相当于一次入栈操作，函数返回相当于一次出栈操作（从系统为函数分配内存空间的角度来看，是这样的），所以我们可以自己维护一个栈，从而减少系统维护栈时的无谓开销。这也是将递归算法转变为非递归算法的核心；

二、非递归算法分析

先序遍历
```
public void visitByPreOrder(ITreeVisitor
     
       visitor){    MyLinkedDeque
      
       
        > stack=new MyLinkedDeque<>();    MyBinaryTree
        
          currentNode=this;    while(currentNode!=null||!stack.isEmpty()) {
    //进入        while (currentNode != null) {            visitor.visitNode(currentNode);//访问            stack.addFirst(currentNode);//入栈            currentNode = currentNode.leftTree;        }        if(!stack.isEmpty()){            currentNode=stack.pollFirst();//出栈            currentNode=currentNode.rightTree;//转向        }    }}
        
       
      
     
```
先序递归遍历一棵树的过程相当于：访问树X->访问X结点（如果X不为空）->访问树X的左子树（产生递归调用）->（递归调用返回后）访问树X的右子树（产生递归调用）；

先序非递归遍历一棵树的过程相当于：访问树X->访问X结点->将X结点入栈（这一过程相当于产生递归调用，效果等价于系统进行的现场保护，目的是在访问完左子树后，由它进入右子树。在递归方法里是系统帮我们做的这一步）->访问X的左子树；

上述过程直到访问的树为空时结束；当我们发现正在访问的一棵树是空的时候，就相当于递归调用返回。此时的栈顶元素为空树的父结点X，于是我们弹出结点X并开始访问X的右子树，过程同上：访问树Y->访问Y结点->将Y结点入栈->访问树Y的左子树；直到下一次遇到空树返回，此时栈顶元素则是接下来要访问的右子树的父结点；

每当我们压入一个结点，意味着我们访问了该结点，并即将访问结点的左子树；（保留现场，相当于递归访问左子树开始）；

每当我们弹出一个结点，意味着我们完全访问这个结点和其左子树，即将访问右子树；（还原现场，相当于递归访问左子树结束）；

当我们访问空树时，会弹出一个结点；（还原现场，相当于递归调用结束）；

当我们访问非空树时，会压入一个结点；（保留现场，相当于递归调用开始）；

遍历结束的条件即为栈中无元素（只要栈中有元素，就说明其右子树尚未访问）；

中序遍历
```
public void visitByInOrder(ITreeVisitor
     
       visitor ){    MyLinkedDeque
      
       
        > stack=new MyLinkedDeque<>();    MyBinaryTree
        
          currentNode=this;    while(currentNode!=null||!stack.isEmpty()){
    //进入        while(currentNode!=null) {            stack.addFirst(currentNode);//入栈            currentNode=currentNode.leftTree;        }        if(!stack.isEmpty()){
    //出栈            currentNode=stack.pollFirst();            visitor.visitNode(currentNode);//访问            currentNode=currentNode.rightTree;//转向        }    }}
        
       
      
     
```
中序递归遍历一棵树X的过程相当于：访问树X的左子树（产生递归调用）->（递归调用返回后）访问X结点（如果X不为空）->访问树X的右子树（产生递归调用）；

中序非递归遍历一棵树的过程相当于：访问树X->将X结点入栈（相当于产生递归调用，结束标记为X为空）->访问X的左子树；

上述过程直到访问的树为空时结束；当我们发现正在访问的一棵树是空的时候，就相当于递归调用返回，左子树访问完成。此时的栈顶元素为空树的父结点X，于是我们弹出结点X并访问X。然后访问X的右子树，过程同上：访问树Y->将Y结点入栈->访问Y的左子树；直到下一次遇到空树返回；

每当我们压入一个结点，意味着我们即将访问该结点的左子树；（保留现场，相当于递归访问左子树开始）；

每当我们弹出一个结点，意味着我们完全访问了这个结点的左子树，可以访问该结点；（还原现场，相当于递归访问左子树结束）；

当我们访问空树时，会弹出一个结点；（还原现场，相当于递归调用结束）；

当我们访问非空树时，会压入一个结点；（保留现场，相当于递归调用开始）；

遍历结束的条件即为栈中无元素（只要栈中有元素，就说明尚未访问该结点以及该结点的右子树）；

后序遍历

后序遍历过程中当执行出栈时（访问的树为空树）,操作是不确定的，这和先序遍历和后序遍历是不同的（详细原因见后文A分析）。所以我们需要判断对当前栈顶元素进行访问还是进行转向：出栈操作是因为结束了对一棵树的访问，而我们不知道这棵树同栈顶元素的关系（只知道是子树），如果是访问完左子树，那么如果栈顶元素有右子树，我们需要转入右子树；如果没有，那么我们需要访问该结点；如果访问完右子树，那么我们需要访问该结点；通过一个辅助变量来记录上一次访问的结点，可以实现判断：如果栈顶元素有右子树，并且该右子树并不是上一次访问的结点，那么就进入右子树；否则（要么栈顶元素没有右子树或者已经访问过啦）访问栈顶元素；
```
public void visitByPostOrder(ITreeVisitor
     
       visitor){    MyLinkedDeque
      
       
        > stack=new MyLinkedDeque<>();    MyBinaryTree
        
          currentNode=this,visited=null;    while(currentNode!=null||!stack.isEmpty()){
    //进入        while(currentNode!=null){            stack.addFirst(currentNode);//入栈            currentNode=currentNode.leftTree;        }        if(!stack.isEmpty()){            currentNode=stack.peekFirst();//检查栈顶元素            if(currentNode.rightTree!=null&&currentNode.rightTree!=visited){
    //判断对当前栈顶元素的操作                currentNode=currentNode.rightTree;//转向            }else {                visitor.visitNode(currentNode);//访问                stack.pollFirst();//弹出                visited=currentNode;//记录访问点                currentNode=null;//让它出栈            }        }    }}
        
       
      
     
```
现在来解释A：
出栈一定意味着对一个树的访问结束；
对于先序遍历，如果是左子树访问结束，那么需要进入栈顶元素的右子树；如果是右子树，那么访问结束便意味着另一棵树的访问也结束了；这样一来，只要是因为右子树访问完毕，那么一定会向上传递，直到整合二叉树的遍历完成，而此刻栈空。所以，只要存在栈顶元素，那么一定是转向进入右子树；

而对于中序遍历，是同样的道理，而背后的共性是因为：右子树的访问完成都标志着整棵二叉树的遍历完成；对于后序遍历，就不一样了，这就是后序遍历采取分类处理的原因；