二叉树前序、中序和后序遍历的非递归实现

二叉树前序、中序和后序遍历的非递归实现

二叉树的遍历是数据结构中的一个重要概念，常见的遍历方式包括前序遍历、中序遍历和后序遍历。虽然递归实现是最直观的方式，但在某些场景下，非递归实现可能更为高效。本文将详细介绍二叉树前序、中序和后序遍历的非递归实现方法。

前序遍历（非递归实现）

前序遍历的顺序是根左右，当根节点不为空时，该节点才可以被打印。递归方法会自动保存现场信息，而非递归实现则需要使用栈来手动保存这些信息。

伪代码实现

void PreOrderTraverse(BinaryTree root)  
{  
    BinaryTree cur = root;  
    stack s;  
    while(null != cur || !s.empty())  
    {  
        while(null != cur)  
        {  
            print cur.data;  
            s.push(cur);  
            cur = cur.left;  
        }  
        if(!s.empty()) {  
            cur = s.top();  
            s.pop();  
            cur = cur.right;  
        }  
    } //loop end!  
}

实现原理

• 第3行的cur相当于递归中的现场信息，而第4行声明的栈则用来保存它。
• 第5行的循环条件是结点不为空或者用户栈不空。
• 第7行到第12行的代码主要做的是，如果当前节点不为空，则打印，同时将该结点的信息保存到用户栈中，接着把当前节点改变成它的左子。当左子为空时，循环结束。
• 第13行到第16行的代码做的是取栈顶的现场信息（也就是最后一次保存的现场信息），然后改变当前结点为它的右子。

后序遍历（非递归实现）

后序遍历的顺序是左右根，我们要保证根节点在左孩子和右孩子访问之后才能访问。

实现条件

• P的左孩子和右孩子都为空，则该节点可以被直接访问；
• P有左孩子或右孩子，但左孩子和右孩子都已经被访问过，那么结点P也可以直接访问。

如果不是上面两种条件，那我们将P的右孩子和左孩子依次入栈，这样就可以保证每次取栈顶元素的时候，左孩子在右孩子的前面被访问，左孩子和右孩子都在根节点的前面被访问。

伪代码实现

void PostOrderTraverse(BinaryTree root)  
{  
    if(null == root)  
        return;  
    stack s;  
    s.push(root);  
    BinaryTree pre = null;  
    BinaryTree cur;  
    while(!s.empty())  
    {  
        cur = s.top();  
        if((null == cur.lchild && null == cur.rchild)  
            || (null != pre) && (pre == cur.lchild || pre == cur.rchild)) {  
            print cur.data;  
            s.pop();  
            pre = cur;  
        }  
        else {  
            if(null != cur.rchild) {  
                s.push(cur.rchild);  
            }  
            if(null != cur.lchild) {  
                s.push(cur.lchild);  
            }  
        }  
    } //loop end!  
}

总结

通过上述分析，我们可以看到非递归遍历方法虽然在代码实现上相对复杂，但其效率通常高于递归方法。在实际开发中，可以根据具体需求选择合适的遍历方式。