关于数据结构:二叉树遍历算法的改进非递归实现

二叉树遍历算法的改良

二叉树的深度优先遍历算法都是用递归函数实现的，这是很低效的，起因在于零碎帮你调用了一个栈并做了诸如爱护现场和复原现场等简单的操作，才使得遍历能够用十分简洁的代码实现。二叉树深度优先遍历算法的非递归实现用用户定义的栈来代替零碎栈，也就是用非递归的形式来实现遍历算法，能够失去不小的效率晋升。

二叉树深度优先遍历算法的非递归实现

（1）先序遍历非递归算法

要写出其遍历的非递归算法，其次要工作是用本人定义的栈来代替零碎栈的性能。

以图 1 所示的二叉树为例，过程为图二所示

初态栈空

1. 结点 1 入栈。
2. 出栈，输入栈顶结点 1，并将 1 的左、右孩子结点（2 和 4）入栈；右孩子先入栈，左孩子后入栈，因为对左孩子的拜访要先于右孩子，后入栈的会先出栈拜访。
3. 出栈，输入栈顶结点 2，并将 2 的左、右孩子结点（3 和 5）入栈。
4. 出栈，输入栈顶结点 3，3 为叶子结点，无孩子，本步无结点入栈。
5. 出栈，输入栈顶结点 5。

出栈，输入栈顶结点 4，此时栈空，进入终态。

遍历序列为 1，2，3，5，4。

代码如下

void preorderNonrecursion(BTNode *bt)
{if(bt != NULL)
    {BTNode *Stack[maxSize];                // 定义一个栈
        int top = -1;                        // 初始化栈
        BTNode *p;
        Stack[++top] = bt;                    // 根结点入栈
        while(top != -1)                    // 栈空循环完结
        {p = Stack[top--];                // 出栈并输入栈顶结点
            Visit(p);                        //Visit() 为拜访 p 的函数
            if(p->rchild != NULL)            // 栈顶结点的右孩子存在，则右孩子入栈
                Stack[++top] = p->rchild;
            if(p->lchild != NULL)            // 栈顶结点的左孩子存在，则左孩子入栈
                Stack[++top] = p->lchild;
        }
    }
}

（2）中序遍历非递归算法

相似于先序遍历，对图 1 中的二叉树进行中序遍历，各个结点进栈、出栈过程如图 3 所示。

初态栈空。

1. 结点 1 入栈，1 左孩子存在。
2. 结点 2 入栈，2 左孩子存在。
3. 结点 3 入栈，3 左孩子不存在。
4. 出栈，输入栈顶结点 3，3 右孩子不存在。
5. 出栈，输入栈顶结点 2，2 右孩子存在，右孩子 5 入栈，5 左孩子不存在。
6. 出栈，输入栈顶结点 5，5 右孩子不存在。
7. 出栈，输入栈顶结点 1，1 右孩子存在，右孩子 4 入栈，4 左孩子不存在。

出栈，输入栈顶结点 4，此时栈空，进入终态。

遍历序列为 3，2，5，1，4。

由以上步骤能够看出，中序非递归遍历过程如下：

1. 开始根结点入栈
2. 循环执行如下操作：如果栈顶结点左孩子存在，则左孩子进栈；如果栈顶结点左孩子不存在，则出栈并输入栈顶结点，而后查看其右孩子是否存在，如果存在，则右孩子入栈。
3. 当栈空时算法完结。

代码如下

void inorderNonrecursion(BTNode *bt)
{if(bt != NULL)
    {BTNode *Stack[maxSize];
        int  top = -1;
        BTNode *p;
        p = bt;
        /* 下边循环实现中序遍历。留神：图 3 进栈、出栈过程在 7 中会呈现栈空状态，然而这时遍历还没有完结，因根结点的右子树还没有遍历，此时 p 非空，依据这一点来维持循环的进行 */
        while(top != -1 || p != NULL)
        {while(p != NULL)        // 左孩子存在，则左孩子入栈
            {Stack[++top] = p;
                p = p->lchild;
            }
            if(top != -1)            // 在栈不空的状况下出栈并输入出栈结点
            {p = Stack[top--];
                Visit(p);
                p = p->rchild;
            }
        }
    }
}

（3）后序遍历非递归算法

首先写出图 1 中二叉树进行先序遍历和后序遍历的序列。

先序遍历序列：1、2、3、5、4

后序遍历序列：3、5、2、4、1

把后序遍历序列逆序得：

逆后序遍历序列：1、4、2、5、3

发现，逆后序遍历序列和先序遍历序列有一点的分割， 逆后序遍历序列只不过是先序遍历过程中对左右子树遍历程序交换所失去的后果 ，如图 4 所示。

因而，只须要将后面的非递归先序遍历算法中对左右子树的遍历程序替换就能够失去逆后序遍历序列，而后将逆后序遍历序列逆序就失去了后序遍历序列。因而须要两个栈，一个栈 stack1 用来辅助做逆后序遍历（将先序遍历的左、右子树遍历程序替换的遍历形式称为逆后序遍历）并将遍历后果序列压入另一个栈 stack2，而后将 stack2 中的元素全副出栈，所失去的序列即为后序遍历序列。具体过程如图 5 所示。

初态栈空。

1. 结点 1 如 stack1。
2. stack1 元素出栈，并将出栈结点 1 入 stack2，结点 1 的左、右孩子存在，左孩子结点 2 入 stack1，右孩子结点 4 入 stack1，这里留神和先序遍历进出栈过程比照，恰好是将其左、右孩子入栈程序调换，以实现拜访程序的调换。
3. stack1 元素出栈，并将出栈结点 4 入 stack2，结点 4 的左、右孩子不存在。
4. stack1 元素出栈，并将出栈结点 2 入 stack2，结点 2 的左、右孩子存在，左孩子结点 3 入 stack1，右孩子结点 5 入 stack1。
5. stack1 元素出栈，并将出栈结点 5 入 stack2。
6. stack1 元素出栈，并将出栈结点 3 入 stack2。

此时 stack1 空，stack2 中元素自顶向下顺次为：3、5、2、4、1，正好为后序遍历序列。

代码如下：

void postorderNonrecursion(BTNode *bt)
{if(bt != NULL)
    {
        /* 定义两个栈 */
        BTNode *Stack1[maxSize];int top1 = -1;
        BTNode *Stack2[maxSize];int top2 = -1;
        BTNode *p = NULL;
        Stack1[++top1] = bt;
        while(top1 != -1)
        {p = Stack1[top1--]；Stack2[++top2] = p;// 留神这里和先序遍历的区别，输入改为入 Stack2
            /* 留神下边这两个 if 语句和先序遍历的区别，左、右孩子的入栈程序相同 */
            if(p->lchild != NULL)
                Stack1[++top1] = p->lchild;
            if(p->rchild != NULL)
                Stack1[++top1] = p->rchild;
        }
        while(top2 != -1)
        {
            /* 出栈序列即为后序遍历序列 */
            p = Stack2[top2--];
            Visit(p);
        }
    }
}