【数据结构】遍历二叉树的方法（C语言）

淡淡的烟草味﹌ 2023-02-19 11:25 58阅读 0赞

### 文章目录 ###

*   *  二叉树遍历原理
     *  二叉树遍历方法
     *   *  前序遍历
         *  中序遍历
         *   *  中序遍历算法
         *  后序遍历
         *   *  后续遍历算法
         *  层序遍历
         *  二叉树遍历的性质

## 二叉树遍历原理 ##

**二叉树的遍历是指从根结点出发，按照某种次序依次访问二叉树中所有结点，使得每个结点被访问一次且仅被访问一次。**  
两个关键字：“访问”和“次序”。  
访问其实是要根据实际的需要来确定具体做什么，比如对每个结点进行相关计算，输出打印等，它算作是一个抽象操作等。在这里我们可以简单的假设就是输出结点的数据信息。  
二叉树的遍历次序不同于线性结构，最多也就是从头到尾，循环，双向等简单的遍历方式。树的结点之间不存在唯一的前驱和后继的关系，在访问一个结点之后，下一个被访问的结点面临着不同的选择。

## 二叉树遍历方法 ##

二叉树的遍历方式可以很多 ，如果我们限制了从左到右的习惯方式，那么主要就分为四种

### 前序遍历 ###

若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，在前序遍历右子树。如图1-1所示，遍历的顺序为：ABDGHCEIF。  
![在这里插入图片描述][20200620140618123.png_pic_center]

图1-1  \#\#\#\# 前序遍历算法 二叉树的定义是用递归的方式，所以遍历算法也可以采用递归，而且极其简洁。

//二叉树前序遍历递归算法
    void PreOrderTraverse(BiTree T)
    {
        
    	if(T == NULL)
    	{
        
    		return;
    	}
    	printf("%C",T->data); //显示结点数据
    	PreOrderTraverse(T->lchild); //先序遍历左子树
    	PreOrderTraverse(T->rchild);//最后先序遍历右子树
    	
    }

假设我们有如图1-1-1这样的二叉树T，这树已经用二叉链表结构存储在内存中。

![在这里插入图片描述][20200620150014809.png_pic_center]

图1-1-1  当调用PreOrderTraverse(T)函数时，看一下步骤 （1）调用PreOrderTraverse(T),T根结点不为null，所以执行printf，打印字母A。 （2）调用PreOrderTraverse(T->lchild)，访问了B结点的左孩子，执行printf显示字母D，如图1-1-2所示。

![在这里插入图片描述][20200620150538128.png_pic_center]

图1-1-2  
（3）此时在递归调用PreOrderTraverse(T->lchild)，访问了B结点的左孩子，执行printf显示字母D，如图1-1-3所示。  
![在这里插入图片描述][20200620150757303.png_pic_center]

图1-1-3  （4）在次递归调用PreOrderTraverse(T->lchild)，访问了结点D的左孩子，执行printf输出H。

（5）在次递归调用PreOrderTraverse(T->lchild)，访问了H结点的左孩子，此时因为H结点无左孩子，所以T ==null，返回此函数，此时递归调用PreOrderTraverse(T->rchild),访问 了结点H的右孩子，输出K，如图1-1-4所示。  
![在这里插入图片描述][20200620151200117.png_pic_center]

图1-1-4

（6）再次递归调用PreOrderTraverse(T->lchild)，访问K的左孩子，K结点无左孩子，返回，调用PreOrderTraverse(T->rchild)，访问了K结点的右孩子，也是null，返回，于是此函数执行完毕，返回到上一级递归的函数(即输出H结点是函数)，也执行完毕，返回到输出结点D的函数，调用PreOrderTraverse(T->rchild)，访问了结点D的右孩子，不存在，返回到B结点，调用PreOrderTraverse(T->rchild)，找到了结点E。输出E，如图1-1-5所示。  
![在这里插入图片描述][20200620151651624.png_pic_center]

图1-1-5  
（7）由于结点E没有左右孩子，返回结点B的递归函数，递归执行完毕，返回到最初的PreOrderTraverse，调用PreOrderTraverse（T->rchild）访问结点A的孩子，输出字母C，如图1-1-6所示。  
![在这里插入图片描述][20200620151922331.png_pic_center] 图1-1-6  
之后类似前面的递归调用，依次打印FIGJ。  
此二叉树的前序遍历顺序：ABDHKECFIGJ。

### 中序遍历 ###

若树为空，则空操作返回，否则从根结点开始（注意不是先访问根结点），中序遍历根结点的左子树，然后是访问根结点，最后中序遍历右子树。如图1-2所示，遍历顺序为GDHBAEICF。

![在这里插入图片描述][2020062014452255.png_pic_center]

图1-2

#### 中序遍历算法 ####

和前序遍历算法仅仅只是代码顺序上的差异。

//二叉树中序遍历递归算法
    void InOrderTraverse(BiTree T)
    {
        
    	if(T == NULL)
    	{
        
    		return;
    	}
    	InOrderTraverse(T->lchild); //中序遍历左子树
    	printf("%C",T->data); //显示结点数据
    	PreOrderTraverse(T->rchild);//最后中序遍历右子树
    	
    }

换句话说，它等于是把调用左孩子的递归函数提前了。

### 后序遍历 ###

若树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后访问根结点。如图1-3所示，遍历的顺序为：GHDBIEFCA。  
![在这里插入图片描述][20200620144946406.png_pic_center]

图1-3

#### 后续遍历算法 ####

//二叉树后序遍历递归算法
    void PostOrderTraverse(BiTree T)
    {
        
    	if(T == NULL)
    	{
        
    		return;
    	}
    	
    	PreOrderTraverse(T->lchild); //后续序遍历左子树
    	PreOrderTraverse(T->rchild);//后序遍历右子树
    	printf("%C",T->data); //显示结点数据
    	
    }

### 层序遍历 ###

若树为空，则空操作返回。否则从树的第一层，也就是根结点开始访问，从上而下逐层遍历，在同一层中，按从左到右的吮吸对结点逐个访问。如图1-4所示。遍历的顺序为：ABCDEFGHI。  
![在这里插入图片描述][20200620145228608.png_pic_center]

图1-4

### 二叉树遍历的性质 ###

*  已知前序遍历和中序遍历序列，可以唯一确定一颗二叉树。
 *  已知后续遍历和中序遍历序列，可以唯一缺点一颗二叉树。  
    **注意：已知前序和后续遍历，是不能确定一颗二叉树的。**

[20200620140618123.png_pic_center]: https://img-blog.csdnimg.cn/20200620140618123.png#pic_center
[20200620150014809.png_pic_center]: https://img-blog.csdnimg.cn/20200620150014809.png#pic_center
[20200620150538128.png_pic_center]: https://img-blog.csdnimg.cn/20200620150538128.png#pic_center
[20200620150757303.png_pic_center]: https://img-blog.csdnimg.cn/20200620150757303.png#pic_center
[20200620151200117.png_pic_center]: https://img-blog.csdnimg.cn/20200620151200117.png#pic_center
[20200620151651624.png_pic_center]: https://img-blog.csdnimg.cn/20200620151651624.png#pic_center
[20200620151922331.png_pic_center]: https://img-blog.csdnimg.cn/20200620151922331.png#pic_center
[2020062014452255.png_pic_center]: https://img-blog.csdnimg.cn/2020062014452255.png#pic_center
[20200620144946406.png_pic_center]: https://img-blog.csdnimg.cn/20200620144946406.png#pic_center
[20200620145228608.png_pic_center]: https://img-blog.csdnimg.cn/20200620145228608.png#pic_center