二叉树的遍历（先序、中序、后序和层次法）

╰+攻爆jí腚メ 2022-12-25 01:00 399阅读 0赞

# 一、二叉树的遍历 #

●遍历是指按指定的规律从根结点开始，对二叉树中的每个结点遍历一次且仅遍历一次。  
●遍历可以采用递归方法（程序简单）和非递归方法（程序稍复杂）。从中可以寻出“足迹”。  
例如下列一颗简单的二叉树：![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjYzNjYzMg_size_16_color_FFFFFF_t_70]

遍历二叉树，可有3+1种方法：先序、中序、后序和层次法。  
以下前三种方法从根部开始逆时针方向绕过各结点，形成一条蜿蜒“足迹”。

**(1)先序法（又称先根法）**  
先序遍历：根，左子树，右子树  
遍历的结果：A，B，C  
遍历的足迹：沿途经过各结点的“左部”

**(2)中序法（又称中根法）**  
中序遍历：左子树，根，右子树  
遍历的结果：B，A，C  
遍历的足迹：沿途经过各结点的“下部”

**(3)后序法（又称后根法）**  
后序遍历：左子树，右子树，根  
遍历的结果：B，C，A  
遍历的足迹：沿途经过各结点的“右部”

**(4)层次法**  
层次遍历：从根开始，层次自上到下，同层结点自左至右进行。  
遍历的结果：A，B，C  
遍历的足迹：第一层A，第二层B，C

例：下列二叉树的四种遍历  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjYzNjYzMg_size_16_color_FFFFFF_t_70 1]  
(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，试画出这棵二叉树。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjYzNjYzMg_size_16_color_FFFFFF_t_70 2]

（2） 已知一棵二叉树的先序和中序遍历序列分别是：ABCDEFG和CBDAFEG，试画出这棵二叉树。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjYzNjYzMg_size_16_color_FFFFFF_t_70 3]

**2.若二叉树的先序和后序确定，则该二叉树不能唯一确定；**  
如：下列两棵不同的二叉树先序都是（A，B），而后序都是（B，A）。  
![在这里插入图片描述][20201129233258745.png]

# 三、二叉树的遍历算法 #

## 二叉树的先序遍历 ##

遍历规律：先遍历根结点，再遍历左子树，最后遍历右子树  
**●先序遍历的递归算法和程序（较简单）**

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+b*c-d-e/f按不同的次序遍历此二叉树，将访问的结点按先后次序排列起来的次序是：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjYzNjYzMg_size_16_color_FFFFFF_t_70 4]  
先序序列为(前缀表达式)：-+a*b-cd/ef  
中序序列为(中缀表达式)：a+b*c-d-e/f  
后序序列为(后缀表达式)：abcd-*\+ef/-

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjYzNjYzMg_size_16_color_FFFFFF_t_70]: /images/20221120/c329c36f67cc4c53a9c1f3f33912d0eb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjYzNjYzMg_size_16_color_FFFFFF_t_70 1]: /images/20221120/fc59f8c451b140399423725ca022ec29.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjYzNjYzMg_size_16_color_FFFFFF_t_70 2]: /images/20221120/a1a737500f8b430cbc594fd4946bcf75.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjYzNjYzMg_size_16_color_FFFFFF_t_70 3]: /images/20221120/3b2fcdc5d0864321b66681a8c7d65731.png
[20201129233258745.png]: /images/20221120/582903521ccb460b8bb4d3f79b072a54.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjYzNjYzMg_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20201129235725842.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjYzNjYzMg==,size_16,color_FFFFFF,t_70