二叉树遍历算法的改善

二叉树的深度优先遍历算法都是用递归函数实现的，这是很低效的，缘故原由在于系统帮你调用了一个栈并做了诸如珍爱现场和恢复现场等庞大的操作，才使得遍历可以用异常简练的代码实现。二叉树深度优先遍历算法的非递归实现用用户界说的栈来取代系统栈，也就是用非递归的方式来实现遍历算法，可以获得不小的效率提升。

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

（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。

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

,

以太坊开奖

www.326681.com采用以太坊区块链高度哈希值作为统计数据，联博以太坊统计数据开源、公平、无任何作弊可能性。联博统计免费提供API接口，支持多语言接入。

,

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);
        }
    }
}