首页 / 算法 / 二叉树遍历-非递归算法
二叉树遍历-非递归算法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了二叉树遍历-非递归算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含4859字，纯文字阅读大概需要7分钟。
内容图文
构建一颗二叉树
A
/ \
B C
/ \ / \
D E F G
前序：ABDECFG
中序：DBEAFCG
后序：DEBFGCA上述完全二叉树可以利用先序遍历（递归）的方式输入，代码如下（‘#’代表空树）：
void CreateBiTree(BiTree *T)
{
TElemType e;
if ((e=getchar()) == '#')
{
*T = NULL;
}
else
{
*T = (BiTree) malloc(sizeof(BiTNode));
if (!T)
{
exit(0);
}
(*T)->data = e;
CreateBiTree(&(*T)->lchild); //创建左子树
CreateBiTree(&(*T)->rchild); //创建右子树
}
}中序遍历（非递归算法）
原理： 依次访问二叉树的左子树，并将指向结点的指针存入栈中，当指针为空时，表示左子树访问完毕，此时应退栈输出结点数据，然后访问右子树；
以上面二叉树的中序遍历为例，遍历过程如下（建议对照代码分析）；
- 结点A、B、D入栈 ， 栈内元素【A，B，D】
- 结点D的左子树为空，然后D退栈并输出 ，栈内元素【A，B】
- 进入D的右子树，D的右子树为空， 栈内元素【A，B】
- 继续退栈，即输出B 栈内元素【A】
- 访问B的右子树E，E进栈 栈内元素【A，E】
- 访问E的左子树为空，退栈输出E 栈内元素【A】
- 访问E的右子树为空，退栈输出A 栈内元素【】
- 访问A的右子树，C，F入栈 栈内元素【C，F】
- F的左右子树均为空，退栈输出F，C 栈内元素【】
- 访问C的右子树G 栈内元素【G】
- G的左右子树均为空，退栈并输出G 栈内元素【】
- 此时结点指针为空，并且栈也为空，遍历结束
代码：
void InorderTraverse(BiTree T,Stack *s)
{
BiTree P=T;
while(P||s->stacksize!=0)
{
if(P)
{
Push(s, P);
P=P->lchild;
}
else
{
P=Pop(s);
printf("%c ",P->data);
P=P->rchild;
}
}
}先序遍历（非递归算法）
先序遍历的思想与中序的思想基本一致，只是代码在输出位置上的不同；
void preOrderTraverse(BiTree T,Stack *s)
{
BiTree p=T;
while(p||s->stacksize!=0)
{
if(p)
{
printf("%c ",p->data);
Push(s, p);
p=p->lchild;
}
else
{
p=Pop(s);
p=p->rchild;
}
}
}遍历过程：
输出A，A入栈 栈内元素【A】
输出B，B入栈 栈内元素【A，B】
输出D，D入栈 栈内元素【A，B，D】
D退栈，输出E，E入栈 栈内元素【A，B，E】
E退栈，输出C，C入栈 栈内元素【A，B，C】
输出F，F入栈 栈内元素【A，B，C，F】
F退栈，输出G，G入栈 栈内元素【A，B，C，G】
G，C，B，A的右子树均为空，依次出栈
后序遍历（非递归算法）
后序遍历为 左、右、根，和先序，中序相比较为复杂；因为先序与后序遍历，根结点与左孩子都是相邻输出的，而后序遍历需要最后输出根结点，因此应先访问右子树，下面的算法，借助另外一个栈完成后序遍历；
void PostOrderTraverse(BiTree T,Stack *s1,Stack *s2)
{
BiTree p=T;
while(p||s1->stacksize!=0)
{
if(p)
{
Push(s1,p);
Push(s2,p);
p=p->rchild;
}
else
{
p=Pop(s1);
p=p->lchild;
}
}
while(s2->stacksize!=0)
{
p=Pop(s2);
printf("%c ",p->data);
}
}遍历过程：
- A，C，G入栈 栈1【A，C，G】 栈2【A，C，G】
- G退，F进 栈1【A,C,F 】 栈2【A,C,G,F】
- F,C 退，B进 栈1【A，B 】 栈2【A,C,G,F,B】
- E进 栈1【A，B，E】 栈2【A,C,G,F,B,E】
- E退，D进 栈1【A，B，D】 栈2【A,C,G,F,B,E,D】
- 输出栈2，即为后序序列
这种算法，要求二叉树的所有结点都要进栈，因此比较消耗存储空间
完整代码：
#include <stdio.h>
#include<stdlib.h>
typedef char TElemType;
//树结构
typedef struct BiTNode
{
TElemType data;
struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;
//栈结构
typedef struct Stack
{
BiTree date;
int stacksize; //记录元素个数
struct Stack *next;
struct Stack *base; //栈底指针
struct Stack *top; //栈顶指针
}Stack;
//栈初始化
void InitStack(Stack *s)
{
s->stacksize=0;
s->base=NULL;
s->top=s->base;
}
//插入数据
void Push(Stack *s,BiTree T)
{
Stack *p;
p=(Stack *)malloc(sizeof(Stack));
if(!p)
exit(0);
p->date=T;
if(s->stacksize==0) //当插入第一个元素时，指针的变化
{
s->base=p; //赋给栈底指针
s->top=p;
p->next=NULL;
}
else
{
p->next=s->top;
s->top=p;
}
s->stacksize++;
}
//删除并返回栈顶元素
BiTree Pop(Stack *s)
{
BiTree t;
Stack *p;
p=s->top;
t=p->date;
s->top=p->next;
free(p);
s->stacksize--;
return t;
}
/*构建二叉树*/
void CreateBiTree(BiTree *T)
{
TElemType e;
if ((e=getchar()) == '#')
{
*T = NULL;
}
else
{
*T = (BiTree) malloc(sizeof(BiTNode));
if (!T)
{
exit(0);
}
(*T)->data = e;
CreateBiTree(&(*T)->lchild); //创建左子树
CreateBiTree(&(*T)->rchild); //创建右子树
}
}
//中序遍历(非递归)
void InorderTraverse(BiTree T,Stack *s)
{
BiTree P=T;
while(P||s->stacksize!=0)
{
if(P)
{
Push(s, P);
P=P->lchild;
}
else
{
P=Pop(s);
printf("%c ",P->data);
P=P->rchild;
}
}
}
//先序遍历(非递归)
void preOrderTraverse(BiTree T,Stack *s)
{
BiTree p=T;
while(p||s->stacksize!=0)
{
if(p)
{
printf("%c ",p->data);
Push(s, p);
p=p->lchild;
}
else
{
p=Pop(s);
p=p->rchild;
}
}
}
//后序遍历
void PostOrderTraverse(BiTree T,Stack *s1,Stack *s2)
{
BiTree p=T;
while(p||s1->stacksize!=0)
{
if(p)
{
Push(s1,p);
Push(s2,p);
p=p->rchild;
}
else
{
p=Pop(s1);
p=p->lchild;
}
}
while(s2->stacksize!=0)
{
p=Pop(s2);
printf("%c ",p->data);
}
}
int main()
{
printf("请输入二叉树，#代表空树：\n");
BiTree T;
Stack stack1,stack2,*p1,*p;
p=&stack1;p1=&stack2;
InitStack(p);
InitStack(p1);
CreateBiTree(&T);
printf("前序遍历结果为：");
preOrderTraverse(T, p);
printf("\n");
printf("中序遍历结果为：");
InorderTraverse(T, p);
printf("\n");
printf("后序遍历结果为：");
PostOrderTraverse(T, p,p1);
printf("\n");
return 0;
}
/* 测试
ABD##E##CF##G##
前序遍历结果为：A B D E C F G
中序遍历结果为：D B E A F C G
后序遍历结果为：D E B F G C A
Program ended with exit code: 0
*/后记：我不知道这篇博客算不算详解，在写的过程中，对代码有了更深的理解，也对整个遍历过程有了更深的了解，希望这篇文章对你可以有一点点帮助
内容总结
以上是互联网集市为您收集整理的二叉树遍历-非递归算法全部内容，希望文章能够帮你解决二叉树遍历-非递归算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。