欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

二叉树的遍历(先序、中序、后序和层次法)

程序员文章站 2022-05-06 21:34:48
...

一、二叉树的遍历

●遍历是指按指定的规律从根结点开始,对二叉树中的每个结点遍历一次且仅遍历一次。
●遍历可以采用递归方法(程序简单)和非递归方法(程序稍复杂)。从中可以寻出“足迹”。
例如下列一颗简单的二叉树:二叉树的遍历(先序、中序、后序和层次法)

遍历二叉树,可有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(btlchild); //递归遍历左子树
 		PostOrder(btrchild); //递归遍历右子树
 		printf(%c ”,btdata);
 		//遍历根结点(输出数据)
	}
}

●后序遍历的非递归算法和程序(稍复杂)
利用栈来实现二叉树的后序遍历比先序和中序复杂得多,在后序遍历中,当搜索指针指向某一个结点时,不能马上进行访问,而先要遍历左子树,所以此结点先要入栈保存,当遍历完它的左子树后,再次回到该结点,还不能访问它,再次退栈时,才能访问该结点。
为了区分同一结点的两次进栈,引入一个次数标志,一个元素第一次进栈标志为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=plchild;}
 			if(top>0)
 			{
  				b=s2[--top]; p=s1[top];
  				if(b==0)
  				{
  					s1[top]=p;s2[top++]=1;
					//第二次进栈标志为1
   					p=prchild;
   				} //遍历右子树
			else {printf(%c ”,pdata); p=NULL;} 
			//遍历根
		}
	}while(top>0);
}

例:算术表达式a+bc-d-e/f按不同的次序遍历此二叉树,将访问的结点按先后次序排列起来的次序是:
二叉树的遍历(先序、中序、后序和层次法)
先序序列为(前缀表达式):-+a
b-cd/ef
中序序列为(中缀表达式):a+bc-d-e/f
后序序列为(后缀表达式):abcd-
+ef/-