二叉树遍历方法的非递归实现

作者: 曲谐_ | 来源:发表于2017-08-07 00:34 被阅读0次

算法之二叉树
左神算法笔记——Morris遍历
总结
二叉树，非递归法
Java二叉树的遍历
二叉树的遍历实现递归与非递归
二叉树的各类遍历方法
二叉树遍历java,非递归、层次。
数据结构——树
数据结构-树的遍历

之前递归实现的方法可以看我前段时间的博客：
http://www.jianshu.com/p/1a81f7a9d106

那么这次来写一下非递归如何实现前序，中序与后序遍历。

前序，中序，后序非递归遍历

思路：

利用STL适配器stack，也就是入栈出栈功能来实现。
实际写代码时，要注意跟着遍历思路去走，走不通的时候适当假设。

步骤：

首先先在原有BinaryTree.h头文件中添加如下接口：

void PreNoRecursion(BtreeNode * root);//前序非递归遍历
void InNoRecursion(BtreeNode * root);//中序非递归遍历
void PostNoRecursion(BtreeNode * root);//后序非递归遍历

之后在具体实现中写代码，代码如下：

void BinaryTree::PreNoRecursion(BtreeNode * root)
{
    if(!root)
        return;
    stack<BtreeNode*> s;
    while(!s.empty() || root)
    {
        while(root)
        {
            s.push(root);
            cout << root->alpha << " ";
            root = root->lchild;
        }
        if(!s.empty())
        {
            root = s.top();
            s.pop();
            root = root->rchild;
        }
    }
}
void BinaryTree::InNoRecursion(BtreeNode * root)
{
    if(!root)
        return;
    stack<BtreeNode*> s;
    while(!s.empty() || root)
    {
        while(root)
        {
            s.push(root);
            root = root->lchild;
        }
        if(!s.empty())
        {
            root = s.top();
            cout << root->alpha << " ";
            s.pop();
            root = root->rchild;
        }
    }
}
void BinaryTree::PostNoRecursion(BtreeNode * root)
{
    if(!root)
        return;
    stack<BtreeNode*> s;
    BtreeNode * p1 = root;
    BtreeNode * pLast = NULL;
    while(p1)
    {
        s.push(p1);
        p1 = p1->lchild;
    }
    while(!s.empty())
    {
        p1 = s.top();
        s.pop();
        if (p1->rchild == NULL || p1->rchild == pLast)
//注意此时左子树已经到头了，下面没有了，只需判断右子树有没有遍历过。
//如果有就可以打印了。
        {
            cout << p1->alpha << " ";
            pLast = p1;
        }
        else//else if(p1->lchild == pLast)
        {
            s.push(p1);
            p1 = p1->rchild;
            while(p1)
            {
                s.push(p1);
                p1 = p1->lchild;
            }
        }
    }
}

那么，我们分别分析一下前序，中序，后序遍历时应注意的细节。

前序非递归遍历

首先建立Stack模板类容器，用于对BtreeNode*类型压栈出栈的操作。用栈的操作模拟遍历操作（遍历与栈都是先进后出型操作）
先建立大的循环体，也就是当栈内有元素或是根节点有值时就进行操作。（到最后栈内有元素时可能已经打印完毕，但我们要出栈，释放资源）
从根结点开始，每遍历一个数就打印，用while循环体结构，一直遍历到结点没有左孩子为止，循环体结束。此时root为叶子结点的空左孩子，方便跳出循环。
此时上一子树的根结点左孩子已经遍历且为空，那么继续遍历该根结点的右孩子。此时有两种情况：
1）如果为空结点，那么跳过上面while循环，继续弹出栈返回上一层结点，寻找上一层结点的右孩子。
2）如果不为空结点，那么执行上面while语句，再对这个结点的所有子树做前序遍历。如果不能理解，将这个结点看作整棵树的根结点，那么我们上面分析的都是从树的根结点出发的，只是出发点的不同罢了。代码都是一样的。

中序非递归遍历

中序与前序非常相像，唯一的变化便是cout位置的变化，因为他是对结点先遍历左孩子，然后打印该结点，再遍历右孩子。

先遍历结点所有左孩子，此时指向最左端叶子结点的空左孩子（NULL）。
进入if语句，将栈顶元素（即那个左孩子）赋值给root，此时没有左孩子可以遍历了，因此根据中序遍历的原理先打印结点。然后弹出栈（可以看成递归返回了上一级），再遍历这个结点的右孩子，此时有两种情况：
1）右孩子里有左孩子或只有右孩子，那么像前序遍历一样把这个右孩子看成根结点（上面有提到这个思路），利用while和if进行中序遍历。
注意：打印完的结点就要从栈内弹出了，因为遍历结束且打印了，它就没有继续在栈内存在的必要了，只有未打印的结点才能留在栈内。
2）右孩子为空，那么这个结点执行完毕返回上一层结点（在递归中为返回上一级递归，在非递归中，即为跳出while循环，继续在if程序块中弹栈并打印上一级根结点）。

后序非递归遍历

后序递归遍历稍微有些复杂，不过我们稍微分析一下就很简单了。
后序遍历需要额外建立一个BTreeNode*类型的变量pLast，用来指向上一个遍历的结点，初始值为NULL。之所以这么做，是因为前一个遍历的结点如果是一个结点的左孩子，那么就须跳过它的根结点，先遍历右结点；如果是一个结点的右孩子，那么直接打印该根结点。
那么，为什么要这么判断呢？举一个简单的例子。

二叉树举例.png

这是一个非常简单的二叉树模型，由这个模型我们可以知道：
1）前序遍历不存在先遍历下两个孩子的情况。
2）中序遍历在之前遍历的只能是B，而不可能是C。
因此，先遍历左右孩子都有可能的只能是后序遍历，所以我们要分情况讨论。

步骤：

首先依旧是先遍历到最左下角。
p1就表示当前结点（即上面两个的root），栈顶元素赋值给它。赋值完就弹出。
判断它的右孩子是不是上一个遍历过的也即pLast或为空，如果是这两种情况，那么根据后序遍历思想，可以打印该结点。然后根据递归思想，将当前结点设置成上一个结点。
判断它的左孩子是不是上一个遍历过的，如果是，它的结点原来被栈弹出，这时要重新压入。再遍历它的右孩子，再将当前右孩子看做树的根结点，再后序遍历。于是就有了下面的那段与上面相同的循环代码。