二叉树的遍历(先序、中序、后序和层次法)
一、二叉树的遍历
●遍历是指按指定的规律从根结点开始,对二叉树中的每个结点遍历一次且仅遍历一次。
●遍历可以采用递归方法(程序简单)和非递归方法(程序稍复杂)。从中可以寻出“足迹”。
例如下列一颗简单的二叉树:
遍历二叉树,可有3+1种方法:先序、中序、后序和层次法。
以下前三种方法从根部开始逆时针方向绕过各结点,形成一条蜿蜒“足迹”。
(1)先序法(又称先根法)
先序遍历:根,左子树,右子树
遍历的结果:A,B,C
遍历的足迹:沿途经过各结点的“左部”
(2)中序法(又称中根法)
中序遍历:左子树,根,右子树
遍历的结果:B,A,C
遍历的足迹:沿途经过各结点的“下部”
(3)后序法(又称后根法)
后序遍历:左子树,右子树,根
遍历的结果:B,C,A
遍历的足迹:沿途经过各结点的“右部”
(4)层次法
层次遍历:从根开始,层次自上到下,同层结点自左至右进行。
遍历的结果:A,B,C
遍历的足迹:第一层A,第二层B,C
例:下列二叉树的四种遍历
(1)先序遍历的结果:A,B,D,F,C,E,G
- A(根)
- B,D,F(先序根的左子树)
- C,E,G(先序根的右子树)
(2)中序遍历的结果:B,F,D,A,E,G,C
- B,F,D(中序根的左子树)
- A(根)
- E,G ,C(中序根的右子树)
(3)后序遍历的结果:F,D,B,G,E,C,A
- F,D,B(后序根的左子树)
- G,E,C(后序根的右子树)
- A(根)
注意:蜿蜒的路线仅用于展示思路,熟悉后心里知晓即可,不必画出。
(4)按层次遍历的结果:A,B,C,D,E,F,G
- A根 (第一层)
- B,C (第二层)
- D,E (第三层)
- F,G (第四层)
现象:左右子树次序打乱
A(根),B(左),C(右),D(左),E(右),F(左),G(右)
二、通过两个序列确定唯一二叉树
1.若中序确定,若再有先序(或后序)也确定,则该二叉树唯一确定;
注意:两个序列中必须有一个中序。
前序第一个是根节点。
后序最后一个是根节点。
而将如上节点放在中序序列中,左侧是根节点的左子树,右侧是根节点的右子树。
例如:
(1) 已知一棵二叉树的中序和后序遍历序列分别是:BFDGAEC和FGDBECA,试画出这棵二叉树。
(2) 已知一棵二叉树的先序和中序遍历序列分别是:ABCDEFG和CBDAFEG,试画出这棵二叉树。
2.若二叉树的先序和后序确定,则该二叉树不能唯一确定;
如:下列两棵不同的二叉树先序都是(A,B),而后序都是(B,A)。
三、二叉树的遍历算法
二叉树的先序遍历
遍历规律:先遍历根结点,再遍历左子树,最后遍历右子树
●先序遍历的递归算法和程序(较简单)
void PreOrder(BTree *bt)
{
if(bt!=NULL)
{
printf(“%c ”,bt->data);
//遍历根结点(输出数据)
PreOrder(bt->lchild); //递归遍历左子树
PreOrder(bt->rchild); //递归遍历右子树
}
}
●先序遍历的非递归算法和程序(稍复杂)
使用一个一维数组作为栈,存储二叉链表中的结点。思路为:从二叉树的根结点开始,沿左子树一直走到末端(左孩子为空)为止,在遍历过程中,依次把所遇结点入栈,当左子树为空时,从栈中退出栈顶结点,并将指针指向该结点的右孩子。如此重复,直到栈为空或指针为空时止。
void PreOrder1(BTree *bt)
{
BTree *s[100],*p=bt; //数组s作为栈
int top=0; //top为栈顶指针
while(p!=NULL||top>0)
{
while(p!=NULL) //遍历根和左子树
{
printf(“%c ”,p->data);
s[++top]=p; p=p->lchild;
}
p=s[top--];p=p->rchild; //遍历右子树
}
}
二叉树的中序遍历
遍历规律:先遍历左子树,再遍历根结点,最后遍历右子树。
●中序遍历的递归算法和程序(较简单)
在这里插入代码片
void InOrder(BTree *bt)
{
if(bt!=NULL)
{
InOrder(bt->lchild); //递归遍历左子树
printf(“%c ”,bt->data);
//遍历根结点(输出数据)
InOrder(bt->rchild); //递归遍历右子树
}
}
●中序遍历的非递归算法和程序(稍复杂)
使用一个一维数组作为栈,存储二叉链表中的结点。思路为:从二叉树的根结点开始,沿左子树一直走到末端(左孩子为空)为止,在走的过程中,把依次遇到的结点入栈,待左子树为空时,从栈中退出结点并访问,然后再转向它的右子树。如此重复,直到栈为空或指针为空为止。
void InOrder1(BTree *bt)
{
BTree *s[100],*p=bt; //数组s作为栈
int top=0; //top为栈顶指针
while(p!=NULL||top>0)
{
while(p!=NULL){s[++top]=p;p=p->lchild;}
//遍历左子树
p=s[top--];
printf(“%c ”,p->data);p=p->rchild;
//遍历根和右子树
}
}
标题二叉树的后序遍历
遍历规律:先遍历左子树,再遍历右子树,最后遍历根结点。
●后序遍历的递归算法和程序(较简单)
void PostOrder(BTree *bt)
{
if(bt!=NULL)
{
PostOrder(btlchild); //递归遍历左子树
PostOrder(btrchild); //递归遍历右子树
printf(“%c ”,btdata);
//遍历根结点(输出数据)
}
}
●后序遍历的非递归算法和程序(稍复杂)
利用栈来实现二叉树的后序遍历比先序和中序复杂得多,在后序遍历中,当搜索指针指向某一个结点时,不能马上进行访问,而先要遍历左子树,所以此结点先要入栈保存,当遍历完它的左子树后,再次回到该结点,还不能访问它,再次退栈时,才能访问该结点。
为了区分同一结点的两次进栈,引入一个次数标志,一个元素第一次进栈标志为0,第二次为1,并将标志存入另一个栈中,当从标志栈中退出的元素为1时,访问结点。
void PostOrder1(BTree *bt)
{
BTree *s1[100],*p=bt;
//栈s1存放树中的结点
int s2[100],b,top=0; //栈s2存放进栈标志
do
{
while(p!=NULL) //遍历左子树
{
s1[top]=p;s2[top++]=0;
//第一次进栈标志为0
p=plchild;}
if(top>0)
{
b=s2[--top]; p=s1[top];
if(b==0)
{
s1[top]=p;s2[top++]=1;
//第二次进栈标志为1
p=prchild;
} //遍历右子树
else {printf(“%c ”,pdata); p=NULL;}
//遍历根
}
}while(top>0);
}
例:算术表达式a+bc-d-e/f按不同的次序遍历此二叉树,将访问的结点按先后次序排列起来的次序是:
先序序列为(前缀表达式):-+ab-cd/ef
中序序列为(中缀表达式):a+bc-d-e/f
后序序列为(后缀表达式):abcd-+ef/-
上一篇: 通过中序和先序/后序序列创建二叉树
推荐阅读
-
Python实现输入二叉树的先序和中序遍历,再输出后序遍历操作示例
-
PHP实现二叉树深度优先遍历(前序、中序、后序)和广度优先遍历(层次)实例详解
-
[PHP] 算法-根据前序和中序遍历结果重建二叉树的PHP实现
-
Python实现二叉树前序、中序、后序及层次遍历示例代码
-
【算法】二叉树的前序、中序、后序、层序遍历和还原。
-
PHP基于非递归算法实现先序、中序及后序遍历二叉树操作示例
-
Python二叉树的遍历操作示例【前序遍历,中序遍历,后序遍历,层序遍历】
-
已知后序遍历和中序遍历求层序遍历(树的遍历)
-
C++实现LeetCode(105.由先序和中序遍历建立二叉树)
-
C++实现LeetCode(889.由先序和后序遍历建立二叉树)