二叉树的深度优先遍历算法都是用递归函数实现的,这是很低效的,原因在于系统帮你调用了一个栈并做了诸如保护现场和恢复现场等复杂的操作,才使得遍历可以用非常简洁的代码实现。二叉树深度优先遍历算法的非递归实现用用户定义的栈来代替系统栈,也就是用非递归的方式来实现遍历算法,可以得到不小的效率提升。
要写出其遍历的非递归算法,其主要任务是用自己定义的栈来代替系统栈的功能。
以图1所示的二叉树为例,过程为图二所示
初态栈空
出栈,输出栈顶结点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;
}
}
}
类似于先序遍历,对图1中的二叉树进行中序遍历,各个结点进栈、出栈过程如图3所示。
初态栈空。
出栈,输出栈顶结点4,此时栈空,进入终态。
遍历序列为3,2,5,1,4。
由以上步骤可以看出,中序非递归遍历过程如下:
代码如下
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;
}
}
}
}
首先写出图1中二叉树进行先序遍历和后序遍历的序列。
先序遍历序列:1、2、3、5、4
后序遍历序列:3、5、2、4、1
把后序遍历序列逆序得:
逆后序遍历序列:1、4、2、5、3
发现,逆后序遍历序列和先序遍历序列有一点的联系,逆后序遍历序列只不过是先序遍历过程中对左右子树遍历顺序交换所得到的结果,如图4所示。
因此,只需要将前面的非递归先序遍历算法中对左右子树的遍历顺序交换就可以得到逆后序遍历序列,然后将逆后序遍历序列逆序就得到了后序遍历序列。因此需要两个栈,一个栈stack1用来辅助做逆后序遍历(将先序遍历的左、右子树遍历顺序交换的遍历方式称为逆后序遍历)并将遍历结果序列压入另一个栈stack2,然后将stack2中的元素全部出栈,所得到的序列即为后序遍历序列。具体过程如图5所示。
初态栈空。
此时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);
}
}
}
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
扫码关注腾讯云开发者
领取腾讯云代金券
Copyright © 2013 - 2025 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号:粤B2-20090059 深公网安备号 44030502008569
腾讯云计算(北京)有限责任公司 京ICP证150476号 | 京ICP备11018762号 | 京公网安备号11010802020287
Copyright © 2013 - 2025 Tencent Cloud.
All Rights Reserved. 腾讯云 版权所有