二叉树的四种遍历方式：先序遍历、中序遍历、后序遍历、层序遍历 (C语言实现)

左手的ㄟ右手 2023-03-01 06:02 142阅读 0赞

## 2.1 先序遍历、中序遍历、后序遍历 ##

我们发现二叉树中每一个结点的结构都是相同的：一个值和两个子节点的指针。所以访问每个结点的方式都是一样的。很显然，我们可以用递归的方式遍历二叉树。  
既然要用递归，必须找到递归的出口：当要访问的结点为NULL时，结束递归。

void traverse(struct Node *root) //遍历二叉树
    {
        
    	if (root == NULL) //递归的出口 
    	{
        
    		return;
    	}
    	traverse(root->leftSon); //递归访问 
    	traverse(root->rightSon); //递归访问
    }

好了，上面的traverse() 函数就可以用来遍历二叉树。但是这个函数没有输出这个结点的值。  
可以用printf("%d ", root->data) 这个语句输出结点的值，但是这个语句放在哪里才比较合适呢？两个递归之前、两个递归之间、还是两个递归之后？其实这三种方式都可以。这三种方式分别被称之为先序遍历、中序遍历、后序遍历。

void traverse(struct Node *root) //遍历树
    {
        
    	if (root == NULL) //递归的出口 
    	{
        
    		return;
    	}
    
    	printf("%d ", root->data); //先序遍历就是把这个语句放在最前面
    	traverse(root->leftSon); //递归访问 
    	printf("%d ", root->data); //中序遍历就是把这个语句放在中间
    	traverse(root->rightSon); //递归访问
    	printf("%d ", root->data); //后序遍历就是把这个语句放在最后面
    }

值得注意的是，如果按照二叉排序树的规则 (下面即将讨论) 建立一棵二叉树，用中序遍历可以获得有序的结果。

## 2.2 完全二叉树的层序遍历 (为堆做准备) ##

记得前面提到完全二叉树的特征吗：从根到倒数第二层是满二叉树；最后一层的叶子都在最左边，中间不留空位。这样的特征造成完全二叉树特别适合用数组进行储存。如果一棵树不是完全二叉树，这时使用数组方式储存就会有很多无效的位置，一个极端的例子：对于一棵深度为n的右斜树，一共需要2n - 1个储存位置，这种储存方式会浪费大量空间。例如下图中的右斜树，储存3个结点，却需要7个空间。这样显然是不合理的。  
对于一棵储存在数组中的完全二叉树，数组中间没有空位，所有空间都被有效利用，按照顺序遍历数组中的每一个元素就是对完全二叉树的层序遍历。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdlaWwwMDc_size_16_color_FFFFFF_t_70]

数组的起始元素的编号为0。在完全二叉树中，如果父节点在数组中的编号为i，而且它的两个儿子结点都存在，那么它的左儿子的编号为i \* 2 + 1，右儿子的编号为i \* 2 + 2。如果已知一个儿子 (左儿子或右儿子都一样) 的编号为k，则它的父结点的编号为 (k - 1) / 2。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdlaWwwMDc_size_16_color_FFFFFF_t_70]: /images/20230209/15bfaad9de764ef9b0962e450fa8ff67.png