[数据结构] 树与二叉树的超详细解析【建议收藏看它就够了】

墨蓝 2022-10-22 04:25 12阅读 0赞

这篇文章篇幅较长，可以点击下方目录查看对应内容。

### 目录 ###

*  一. 树
 *   *  1. 基本概念
     *  2. 树的基本性质
     *  3. 树的表示方法
     *   *  1). 孩子表示法
         *  2). 双亲表示法
         *  3). 孩子双亲表示法
         *  4). 孩子兄弟表示法
     *  4. 树的应用
 *  二. 二叉树
 *   *  1. 概念
     *  2. 特殊二叉树
     *  3. 二叉树的性质
     *  4. 二叉树的存储方式
     *   *  1). 顺序存储方式
         *  2). 链式存储方式
 *  三. 二叉树的顺序结构与实现(堆)
 *   *  1. 堆的概念
     *  2. 堆的性质
     *  3. 堆的实现
     *   *  1). \*\*堆的向下调整算法\*\*
         *  2). 堆的创建
         *  3). 堆的插入
         *  4). 堆的删除操作
     *  4. 堆的应用
     *   *  应用一：堆排序
         *  应用二：Top-K
 *  四. 二叉树的链式存储
 *   *  1. 二叉树的链式存储结构
     *  2. 二叉树的遍历操作
     *  3. 二叉树的其他操作
     *   *  1). 创建树
         *  2). 计算树中节点个数
         *  3). 求第k层节点个数
         *  4). 求叶子节点个数
         *  5). 计算树的高度
         *  6). 在树中查找指定元素
         *  7). 销毁树
         *  8). \*\*判断二叉树是否为完全二叉树\*\*
 *  五. 给定两种遍历方式确定树形
 *   *  1. 前序 + 中序
     *  2. 中序 + 后序
     *  3. 前序 + 后序
 *  六. 总结

# 一. 树 #

## 1. 基本概念 ##

树是一种非线性的数据结构，由n个节点组成具有层次关系的集合。其实就是一颗倒着长得大树，一个树根加了好多叶子。  
  树中必定含有一颗**根节点**，和若干**分支节点**与**叶子节点**。并且每个分支节点的孩子构成了一颗子树。每个子树的根节点只有一个前驱，但是可以由很多的后继。除了根节点外，每个节点有且只有一个父节点。  
    
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcxNzUyMA_size_16_color_FFFFFF_t_70_pic_center]

## 2. 树的基本性质 ##

1.  节点的度：一个节点含有子树的个数成为该节点的度，上图中A的度为2，B的度为3，D的度为0.
2.  叶节点或终端节点：度为0的节点为叶节点。上图中 D、E、F、G、H。
3.  分支节点：度不为0的节点。上图中B、C。
4.  父节点：若一个含有子节点，则称这个节点为父节点。上图中A是B、C的父节点，B是D、E、F的父节点。
5.  子节点：一个节点含有的子树的根节点称为该节点的子节点，上图中B、C是A的子节点
6.  兄弟节点：由相同父节点的节点互称兄弟节点，上图中B、C互为兄弟，D、E、F互为兄弟。
7.  树的度：一棵树中最大节点的度为数的度。上图中度最大的节点为B 3，所以3为树的度。
8.  节点的层次：以根节点所在的层次定义为第1层，根的子节点为第2层。
9.  树的高度或深度：树中节点的最大层次。上图高度为3
10. 堂兄弟节点：父节点在同一层的节点。上图中 DEFGH互为堂兄弟。
11. 节点的祖先：从根节点到该节点所经分支上的所有节点。上图中A是所有节点的祖先
12. 森林：由N棵互不相交的树构成的集合称为森林。

## 3. 树的表示方法 ##

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

### 1). 孩子表示法 ###

1.  数据结构

// 孩子节点结构
    struct BiTreeNode
    { 
    	int child; // 孩子节点的下标
    	BiTreeNode* next;  // 指向下一节点的指针
    }
    
    // 
    struct BiTreeHead
    { 
    	DataType data;		// 存放树中节点的数据
    	BiTreeNode* firstchild;  // 指向第一个孩子的指针
    }
    
    struct CTree{ 
        CTBox BiTreeHead[MAX_SIZE]; //存储结点的数组
        int n,r; //结点数量和树根的位置
    };

1.  图示  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcxNzUyMA_size_16_color_FFFFFF_t_70_pic_center 2]
2.  优缺点  
    优点：找孩子方便。缺点：找双亲不方便

### 2). 双亲表示法 ###

1.  数据结构

struct PTNode{ 
        DataType data; //树中结点的数据类型
        int parent;    //结点的父结点在数组中的位置下标
    };
    struct PTree{ 
        PTNode tnode[MAX_SIZE]; //存放树中所有结点
        int n;    //根的位置下标和结点数
    };

1.  图示  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcxNzUyMA_size_16_color_FFFFFF_t_70_pic_center 3]
2.  优缺点  
    优点：找双亲方便。缺点：找孩子不方便

### 3). 孩子双亲表示法 ###

实则为孩子表示法与双亲表示法的整合。

1.  数据结构

// 孩子节点结构
    struct BiTreeNode
    { 
    	int child; // 孩子节点的下标
    	BiTreeNode* next;  // 指向下一节点的指针
    }
    
    // 
    struct BiTreeHead
    { 
    	DataType data;		// 存放树中节点的数据
    	BiTreeNode* firstchild;  // 指向第一个孩子的指针
    	int parent; // 双亲的下标
    }
    
    struct CTree{ 
        CTBox BiTreeHead[MAX_SIZE]; //存储结点的数组
        int n,r; //结点数量和树根的位置
    };

1.  图示  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcxNzUyMA_size_16_color_FFFFFF_t_70_pic_center 4]

### 4). 孩子兄弟表示法 ###

1.  数据结构

struct BiNode{ 
        ElemType data;
        BiNode* firstchild;	// 孩子指针
        BiNode* nextsibling; // 兄弟指针
    };

1.  图示  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcxNzUyMA_size_16_color_FFFFFF_t_70_pic_center 5]

## 4. 树的应用 ##

文件系统的目录结构

# 二. 二叉树 #

## 1. 概念 ##

一颗二叉树是节点的一个有限集合，该集合为空，或是由一个**根节点加上两棵左右子树构成**。**每个节点至多由两颗子树**。  
  二叉树是一颗有序树，子树有左右之分。

## 2. 特殊二叉树 ##

1.  满二叉树：一个二叉树有n层，每一层的节点都达到了最大值 `2^(n-1)`，该树的节点总数为`2^n - 1`  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcxNzUyMA_size_16_color_FFFFFF_t_70_pic_center 6]
2.  完全二叉树：一颗二叉树有n个节点，每个节点都与它所对应的满二叉树节点对应，则该树就是一棵完全二叉树。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcxNzUyMA_size_16_color_FFFFFF_t_70_pic_center 7]

完全二叉树中节点总个数如果为偶数，则只有一个节点具有左孩子，倒数第一个非叶子节点一定是只有一个左孩子。  
  完全二叉树中节点总个数如果为奇数，则所有的非叶子节点都有两个孩子。

## 3. 二叉树的性质 ##

1.  性质1：若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有`2^(i-1)`个节点
2.  性质2：若规定根节点的层数为1，则深度为h的二叉树的最大节点数是`2^h - 1`
3.  性质3：对任何一颗二叉树，如果度为0的节点个数为`n0`，度为2的节点个数为`n2`，则有 `n0 = n2 + 1`
4.  性质4：若规定根节点的层数为1，具有n个节点的满二叉树深度，`h=log2(n+1)`
5.  性质5：对于具有n个节点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对于序号为i的节点有以下推导：
    
        1.若 i>0, i位置的双亲序号为: (i-1)/2;  若i=0,i为根节点无双亲
         2.若 2i+1<n, 左孩子序号为: 2i+1, 2i+1>=n 否则无左孩子
         3.若 2i+2<n, 右孩子序号为: 2i+2, 2i+2>=n 否则无右孩子

接下来根据上述性质，看一道例题：  
  假设完全二叉树中有1000个节点，则该树中共有多个叶子几点，多少个分支节点，多少个节点只有左孩子。

已知二叉树的节点总数 n = n0 + n1 + n2;
    	因为树的节点总数为偶数，所以 n1=0
    	根据性质3，我们可知 n0 = n2 + 1;
    		所以可以得出, 
    		n = n0 + n2 --> 1000 = n2+1+n2
    		所以n2 = 499, n0 = 500 没有直接点只有左节点

## 4. 二叉树的存储方式 ##

### 1). 顺序存储方式 ###

顺序存储方式利用数组来进行对二叉树的节点进行存储，通过下标表示节点间关系。  
  顺序存储方式只适合存储完全二叉树，利用`性质5`对二叉树的每个节点进行编号，数组小标与元素编号相同。  
  如果一定要使用顺序方式存储非完全二叉树，则需要将该树在逻辑上补充为完全二叉树，并且在存储时将该树作为完全二叉树的形式存储。但是使用这种形式进行存储，会造成空间的大量浪费，对于非完全二叉树，推荐使用链式的形式进行存储。  
**具体的实现会在下文中堆的实现进行详细解释**

### 2). 链式存储方式 ###

通过指针的形式表示节点间关系，形如上文中树的表示形式，具体内容，会在下文详细解释。

# 三. 二叉树的顺序结构与实现(堆) #

## 1. 堆的概念 ##

将所有元素按照完全二叉树的顺序存储方式存储在一个一维数组中。并且该树要满足以下条件：对于任意节点，如果节点值都比其孩子节点大，则称为大根堆。如果节点值都比其任意一个孩子小则称为小根堆。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcxNzUyMA_size_16_color_FFFFFF_t_70_pic_center 8]

## 2. 堆的性质 ##

1 堆顶元素一定是堆中最小或最大元素
    2 堆中存储的树结构一定是一颗完全二叉树
    3 堆序为升序或降序(从根节点到叶子节点的路径)
    4 双亲节点比其任意子孙节点小(大)

## 3. 堆的实现 ##

在实现堆时，给定一个数组，这个数组在逻辑上可以看作为一棵完全二叉树，但这个数组的树形式，可能不满足堆的定义，所以需要通过一些算法，将该数组调整为一个符合堆性质的数组。  
  在这里我们介绍对的向下调整算法。

### 1). **堆的向下调整算法** ###

**1.思路：**  
  判断每个父节点是否满足大于或小于其子节点，如果需要交换则交换两节点，交换后可能还是不满足堆特性，所以移动父节点与子节点位置继续判断是否满足特性，直到满足堆特性，此次调整结束。

下图示例，为左右子树满足堆特性，但根节点加入后不满足堆特性，所以只需要对根节点调整即可。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcxNzUyMA_size_16_color_FFFFFF_t_70_pic_center 9]  
**2. 代码实现**

// 堆的向下调整算法：
    // 传入的节点为双亲节点，判断当前双亲节点是否满足堆的性质，不满足则将当前父节点与子节点进行比较
    // 如果有两个孩子，则与值较小的孩子进行交换位置，一致按照这种方式比较下去，直到到达叶子节点或不满足条件退出
    void AdjustDown(Heap* hp, int nodeId)
    { 
    	HPDataType* data = hp->_a;
    	int child = 2 * nodeId + 1;
    
    	while (child < hp->_size)
    	{ 
    		// 找到两个孩子中的小值
    		if (child + 1 < hp->_size && hp->_cmp(data[child + 1], data[child]))
    			child++;
    
    		// 判断该子树中的节点是否满足堆的性质，不满足则交换
    		if (hp->_cmp(data[child], data[nodeId]))
    		{ 
    			Swap(&data[nodeId], &data[child]);
    
    			// 交换完该节点后，下方子树可能不满足堆的性质，所以移动父节点与孩子节点的位置，继续判断
    			nodeId = child;
    			child = 2 * nodeId + 1;
    		}
    		else
    		{ 
    			return;
    		}
    	}
    }

### 2). 堆的创建 ###

创建堆的过程实则就是将一个数组调整为符合堆性质的过程，与堆的向下调整过程完全相同。

找到倒数第一个非叶子节点 `lastNotLeaf = ((size-1)-1)/2`
    从该节点开始一直到根节点逐个向前对每个节点应用向下调整算法

代码部分：

void HeapCreate(Heap* hp, HPDataType* a, int n, CMP cmp)
    { 
    	// 初始化
    	hp->_a = (HPDataType*)malloc(sizeof(HPDataType) * n);
    	if (NULL == hp->_a)
    	{ 
    		assert(0);
    		return;
    	}
    	hp->_size = 0;
    	hp->_capacity = n;
    	hp->_cmp = cmp;
    
    	// 导入数据
    	memcpy(hp->_a, a, sizeof(HPDataType) * n);
    	hp->_size = n;
    
    	// 使用向下调整算法，将堆调整为符合性质的堆 从倒数第一个节点的父节点开始遍历，直到遍历至根节点
    	for (int root = (n - 2) / 2; root >= 0; root--)
    	{ 
    		AdjustDown(hp, root);
    	}
    }

### 3). 堆的插入 ###

**堆的插入过程为**

1 检测堆空间是否足够，不够则需要扩容
    2 将元素插入至堆尾，插入堆尾后可能会破坏堆的特性
    3 对插入元素使用向上调整算法，通过孩子求双亲，进行比较

**堆的向上调整算法**  
  该算法与向下调整算法一致，不再赘述。

堆插入过程的图示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcxNzUyMA_size_16_color_FFFFFF_t_70_pic_center 10]  
**代码部分**

void CheckCapacity(Heap* hp)
    { 
    	if (hp->_size == hp->_capacity)
    	{ 
    		hp->_a = (HPDataType*)realloc(hp->_a, sizeof(HPDataType) * hp->_capacity * 2);
    		if (NULL == hp->_a)
    		{ 
    			assert(0);
    			return;
    		}
    
    		hp->_capacity *= 2;
    	}
    }
    
    // 向上调整算法
    // 思路相同，传入的节点为孩子节点，判断孩子与双亲的关系，是否满足条件，满足则逐个交换，直到根节点或不满足条件
    void AdjustUp(Heap* hp, int nodeId)
    { 
    	HPDataType* data = hp->_a;
    	int parent = (nodeId - 1) / 2;
    
    	while (nodeId > 0)
    	{ 
    		if (parent >= 0 && hp->_cmp(data[nodeId], data[parent]))
    		{ 
    			Swap(&data[parent], &data[nodeId]);
    
    			nodeId = parent;
    			parent = (nodeId - 1) / 2;
    		}
    		else
    		{ 
    			return;
    		}
    	}
    }
    
    // 堆的插入
    // 判断空间是否足够，空间足够则将该元素插入到队尾的位置，判断该节点是否满足堆的性质，不满足则向上调整，使其满足性质
    void HeapPush(Heap* hp, HPDataType x)
    { 
    	assert(hp);
    
    	// 扩容
    	CheckCapacity(hp);
    
    	// 将元素插入队尾
    	hp->_a[hp->_size++] = x;
    
    	AdjustUp(hp, hp->_size - 1);
    }

### 4). 堆的删除操作 ###

堆删除的过程删除堆顶元素，在删除堆顶元素时，为了简化流程，使用如下思路删除堆顶元素：

1 将堆顶元素与堆尾元素进行交换
    2 删除堆尾元素
    3 再对堆顶元素利用向下调整算法，使其符合堆的特性。

删除过程图示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcxNzUyMA_size_16_color_FFFFFF_t_70_pic_center 11]  
  
  
**代码部分**

// 堆的删除
    // 从堆头删除，交换堆头和堆尾元素，忽略队尾元素，因为调整了堆的结构，可能导致堆不满足性质，
    // 所以，对根节点进行向下调整
    void HeapPop(Heap* hp)
    { 
    	HPDataType* data = hp->_a;
    	
    	Swap(&data[0], &data[hp->_size - 1]);
    	hp->_size--;
    
    	AdjustDown(hp, 0);
    }

## 4. 堆的应用 ##

### 应用一：堆排序 ###

利用删除堆的思想对堆进行排序。删除堆的过程是，将堆头元素与堆尾元素交换，堆头元素为该堆中的最大值或者最小值，所以每次都是将最大值最小值向堆尾移动，移动完成后利用向下调整算法。  
  当每个元素都经历上述这个过程后，该堆就变得有序了。  
  需要注意的是，排升序建大根堆，排降序建小根堆。

**图示**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcxNzUyMA_size_16_color_FFFFFF_t_70_pic_center 12]  
**代码实现**

// 思路：
    // 1. 先将n个元素建立一个大堆或这小堆
    // 2. 建成之后，堆头元素要么最大或者最小
    // 3. 将堆头元素与堆尾元素交换，并将队尾元素剔除，
    // 4. 一直重复上述过程，直到堆中元素全部剔除完成
    
    // 对数组进行堆排序
    void HeapSort(int* a, int n, CMP cmp)
    { 
    	Heap hp;
    	// 建堆
    	HeapCreate(&hp, a, n, cmp);
    
    	// 将堆头元素放置堆尾，并且剔除该元素，该操作与删除堆元素相同
    	while (hp._size > 0)
    	{ 
    		HeapPop(&hp);
    	}
    
    	for (int i = 0; i < n; i++)
    	{ 
    		printf("%d ", hp._a[i]);
    	}
    	printf("\n");
    }

### 应用二：Top-K ###

求最小或最大的前k个数据，eg：数据集合中的最大的10个元素。通常这类问题，所提供的数据量会十分的巨大，使用普通排序时间复杂度最低也是O(logn)，所以再在求解Top-k问题上使用堆来进行求解，时间复杂度为O(n).

**思路**  
  1. 使用前k个元素建堆，取最小值建大堆，取最大值建小堆。  
  2. 使用剩余的n-k个元素依次与堆顶元素进行比较，如果满足条件则交换两值，交换后使用向下调整算法使其满足堆特性。一直往复上述操作，直至比较完成。因为堆顶元素要么是最大值要么是最小值。

**图示**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcxNzUyMA_size_16_color_FFFFFF_t_70_pic_center 13]

**代码实现**

// 找最大的前K个，建立K个数的小堆
    // 找最小的前K个，建立K个数的大堆
    // 思路: 1 建堆 用前k个元素建堆
    // 2 使用剩余的 n-k 个元素依次与堆顶元素比较，如果堆顶元素大于/小于该元素，
    // 则将该元素与堆顶元素进行替换，替换后使用向下调整算法调整该堆符合性质
    // 根据用户选择计算top-k最大的还是最小的
    void PrintTopK(int* a, int n, int k, CMP cmp)
    { 
    	Heap hp;
    	// 建堆
    	HeapCreate(&hp, a, k, cmp);
    
    	// 用n-k个元素与堆顶进行比较
    	for (int i = k; i < n; i++)
    	{ 
    		if (hp._cmp(hp._a[0], a[i]))
    		{ 
    			// 交换堆头元素
    			Swap(&(hp._a[0]), &a[i]);
    
    			// 向下调整
    			AdjustDown(&hp, 0);
    		}
    	}
    
    	for (int i = 0; i < k; i++)
    	{ 
    		printf("%d ", hp._a[i]);
    	}
    }
    
    void TestTopk()
    { 
    	int arr[] = {  42, 65, 12, 65, 12, 56, 654, 12, 654, 12312, 656, 12,1, 233, 3, 5, 6, 7, 8,100 ,9 ,10 };
    	int k = 0;
    	int flag = 0;
    
    	printf("输入格式: num1 num2 ---> num1 显示前多少位, num2 显示最大还是最小，最大1 最小0\n");
    	printf("请输入参数:> ");
    	scanf("%d %d", &k, &flag);
    
    	if(1 == flag)
    		PrintTopK(arr, sizeof(arr) / sizeof(arr[0]), 5, Less);
    	else
    		PrintTopK(arr, sizeof(arr) / sizeof(arr[0]), 5, Greater);
    }

# 四. 二叉树的链式存储 #

## 1. 二叉树的链式存储结构 ##

struct BiTreeNode
    { 
    	DataType data;
    	BiTreeNode* lchild;	// 指向左孩子
    	BiTreeNode* rchild; // 指向右孩子
    };

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

## 2. 二叉树的遍历操作 ##

遍历是指按照某种特定的规则，对二叉树中的节点进行某种相应的操作，并且每个节点只操作一次。

**二叉树中的遍历方式共分为三种，命名方式按照根节点的访问次序进行命名。在下文中的遍历，通过递归对树进行遍历。**

1). 前序遍历  
  先访问根节点，再访问左子树，最后访问右子树。（根-左-右）  
2). 中序遍历  
  先访问左子树，再访问根节点，最后访问右子树。（左-根-右）  
3). 前序遍历  
  先访问左子树，再访问右子树，最后访问根节点。（左-右-根）

**图示**  
使用中序遍历举例：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcxNzUyMA_size_16_color_FFFFFF_t_70_pic_center 15]  
以上图为例：

前序遍历: A B D F C G H
    中序遍历: D B F A C G H
    后序遍历: D F B C G H A

**代码实现**

// 前序遍历二叉树
    void PreOrderTraversal(BTNode* bt, int level)
    { 
    	if (bt != NULL)
    	{ 
    		Vist(bt->data, level);
    		PreOrderTraversal(bt->lchild, level + 1);
    		PreOrderTraversal(bt->rchild, level + 1);
    	}
    }
    
    // 中序遍历
    void InOrderTraversal(BTNode* bt, int level)
    { 
    	if (bt != NULL)
    	{ 
    		InOrderTraversal(bt->lchild, level + 1);
    		Vist(bt->data, level);
    		InOrderTraversal(bt->rchild, level + 1);
    	}
    }
    
    // 后序遍历
    void PostOrderTraversal(BTNode* bt, int level)
    { 
    	if (bt != NULL)
    	{ 
    		PostOrderTraversal(bt->lchild, level + 1);
    		PostOrderTraversal(bt->rchild, level + 1);
    		Vist(bt->data, level);
    	}
    }

**4). 二叉树的层序遍历**  
  这种遍历方式较好理解，就是将每一层的元素从左至右依次输出。但是它的实现方式与上述的三种遍历方式完全不同。  
  因为要实现层序遍历，就要存储每一层的所有子节点，如果树的深度较大，则数据量是巨大的。所以在层序遍历中，使用**队列**来进行二叉树的层序遍历。  
**关于队列操作，点击此处[队列操作][Link 1]**

**层序遍历过程**

1. 定义一个队列结构并初始化，将根节点入队。
    2. 从队列头取出队头节点，遍历该节点的左右子树，并将左右子树入队。
    3. 循环上述操作，直至队列为空。

// 层序遍历 按照树的层次关系，从第一层开始从左至右遍历出现的节点。
    // 遍历时，利用队列的特性，将根节点先入队，之后遍历左右子树的根节点，将左右子树加入队列节点。
    void BinaryTreeLevelOrder(BTNode* root)
    { 
    	if (NULL == root)
    		return;
    
    	Queue queue;
    
    	// 初始化一个队列，并且将根节点加入队列中
    	QueueInit(&queue);
    	QueuePush(&queue, root);
    
    	// 将根节点的左右子树进行遍历，并输出
    	while (!QueueEmpty(&queue))
    	{ 
    		BTNode* cur = QueueFront(&queue);
    		PrintNodeData(cur);
    
    		// 将该根节点的左右子树进行入队列
    		if (NULL != cur->_left)
    			QueuePush(&queue, cur->_left);
    
    		if (NULL != cur->_right)
    			QueuePush(&queue, cur->_right);
    
    		QueuePop(&queue);
    	}
    
    	QueueDestroy(&queue);
    }

## 3. 二叉树的其他操作 ##

### 1). 创建树 ###

二叉树的创建过程，与上述的遍历过程相同，这里我们使用二叉树的前序遍历方式创建二叉树。  
  **在创建树的过程中，对传入的数组要进行数据的读取，因为采用的是递归方式，所以要注意传递下标时，通过地址传递**

// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
    // 如果 pi 按照值的方式传递，因为它是局部变量，每次修改后不会将修改后的值带出去。
    // 因为递归时，为了保护现场，将函数上一次执行的内容，都进行了入栈处理，函数递归结束后，会一步步出栈，所以值传递的无法将结果带出
    BTNode* _BinaryTreeCreate(BTDataType* a, int n, int* pi)
    { 
    	if (a[*pi] == '#' || *pi > n)
    	{ 
    		(*pi)++;
    		return NULL;
    	}
    
    	BTNode* root = BuyBinTreeNode(a[(*pi)++]);
    
    	root->_left = _BinaryTreeCreate(a, n, pi);
    	root->_right = _BinaryTreeCreate(a, n, pi);
    
    	return root;
    }
    
    BTNode* BinaryTreeCreate(BTDataType* a, int n)
    { 
    	int index = 0;
    
    	return _BinaryTreeCreate(a, n, &index);
    }

### 2). 计算树中节点个数 ###

计算节点个数也是通过递归方式实现，分别求出根节点左右子树的节点个数，最后相加得到结果。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcxNzUyMA_size_16_color_FFFFFF_t_70_pic_center 17]

// 遍历左右子树，递归遍历
    int BinaryTreeSize(BTNode* root)
    { 
    	if (NULL == root)
    		return 0;
    
    	return BinaryTreeSize(root->_lchild) + 
    		   BinaryTreeSize(root->_rchild) + 1;
    }

### 3). 求第k层节点个数 ###

如果直接求第k层元素个数，较难求解，所以可以通过第`k-1`层求解其孩子节点的个数。

**思路**

1. 树空 或 k<0, 则无法计算。 k = 1, 则代表只有根节点。
    2. 找到第k-1层的节点，求子节点的总个数。

**代码**

// 通过k-1层计算第k层几点个数
    int BinaryTreeLevelKSize(BTNode* root, int k)
    { 
    	if(NULL == root || k < 0)
    	{ 
    		return 0;
    	}
    
    	if(NULL != root && 1 == k)
    	{ 
    		return 1;
    	}
    	
    	return BinaryTreeLevelKSize(root->_lchild, k - 1) + 
    	   	   BinaryTreeLevelKSize(root->_rchild, k - 1);
    }

### 4). 求叶子节点个数 ###

与上述方法基本相同，左右子树为空时，则它就是叶子节点.

int BinaryTreeLeafSize(BTNode* root)
    { 
    	if(NULL == root)
    	{ 
    		return 0;
    	}
    
    	if(NULL == root->_lchild&& NULL == root->_rchild)
    	{ 
    		return 1;
    	}
    
    	return BinaryTreeLeafSize(root->_lchild) + 
    		   BinaryTreeLeafSize(root->_rchild);
    }

### 5). 计算树的高度 ###

树中包含左子树和右子树，所以只需要求出左右子树高度，取最大值即可。

int BinaryTreeHeight(BTNode* root)
    { 
    	if(NULL == root)
    	{ 
    		return 0;
    	}
    	
    	int lHeight = BinaryTreeHeight(root->_lchild);
    	int rHeight = BinaryTreeHeight(root->_rchild);
    
    	return lHeight > rHeight ? lHeight + 1 : rHeight + 1;
    }

### 6). 在树中查找指定元素 ###

思路依旧相同，分别从左右子树中查找指定元素。

// 二叉树查找值为x的节点
    // 通过序遍历查找节点值
    BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
    { 
    	if (NULL == root)
    		return NULL;
    
    	if (root->_data == x)
    	{ 
    		return root;
    	}
    
    	// 先递归查找左子树，再递归查找右子树，如果查找到则会返回非空值，这一步的bool运算就会为真
    	return BinaryTreeFind(root->_left, x) || BinaryTreeFind(root->_right, x);
    }

### 7). 销毁树 ###

通过后序遍历销毁树，如果使用其他遍历方式，会先销毁子树的根节点，导致后续销毁无法正常进行，所以使用后序遍历方式销毁树。

// 二叉树销毁
    // 后续遍历二叉树，先销毁叶子节点，后销毁根节点
    void BinaryTreeDestory(BTNode** root)
    { 
    	assert(root);
    
    	if (NULL == *root)
    		return;
    
    	BinaryTreeDestory(&(*root)->_left);
    	BinaryTreeDestory(&(*root)->_right);
    
    	free(*root);
    	*root = NULL;
    }

### 8). **判断二叉树是否为完全二叉树** ###

完全二叉树与满二叉树的节点位置相同，最后一层从左至右依次排列。所以只需要**找到最后一个不饱和的节点位置，并且后续节点不能有孩子**。

提供两种方法实现

// 判断二叉树是否是完全二叉树
    // 与层序遍历思路相同，需要用到队列操作
    // 完全二叉树的节点分为下列几种情况
    // 1. 根节点的左右子树都存在，则对接下来的节点不会造成任何影响，所以继续将该根节点的子树入队
    // 2. 根节点的左子树存在、右子树不存在 OR 根节点的左右子树都不存在
    // 这种情况对于上述节点是最后一个节点的根节点满足，但是如果为其他情况就不满足了，
    // 所以对这种情况加入标志位，当不满足条件则激活标志位，
    // 再接下来的循环需要判断标志位，如果标志位激活，并且下一个节点的左右子树为空，则无影响。如果下一个节点的子树不为空，则代表该树不满足完全二叉树
    int BinaryTreeComplete(BTNode* root)
    { 
    	// 树为空也为完全二叉树
    	if (NULL == root)
    		return 1;
    
    	// 初始化队列
    	Queue queue;
    	QueueInit(&queue);
    	QueuePush(&queue, root);
    
    	int flag = 0;
    
    	// 如果左右节点都存在则遍历下一个节点，如果左孩子存在但右孩子不存在则标记，
    	while (!QueueEmpty(&queue))
    	{ 
    		BTNode* cur = QueueFront(&queue);
    
    		// 情况二
    		if ((NULL != cur->_left && NULL == cur->_right) || (NULL == cur->_left && NULL == cur->_right))
    		{ 
    			flag = 1;
    		}
    
    		// 情况三
    		if (NULL == cur->_left && NULL != cur->_right)
    		{ 
    			QueueDestroy(&queue);
    			return 0;
    		}
    
    		// 情况二
    		if (flag && (NULL != cur->_left) && NULL != cur->_right)
    		{ 
    			QueueDestroy(&queue);
    			return 0;
    		}
    
    		if (NULL != cur->_left)
    		{ 
    			QueuePush(&queue, cur->_left);
    		}
    
    		if (NULL != cur->_right)
    		{ 
    			QueuePush(&queue, cur->_right);
    		}
    
    		QueuePop(&queue);
    	}
    
    	QueueDestroy(&queue);
    	return 1;
    }
    
    int BinaryTreeComplete2(BTNode* root)
    { 
    	// 树为空也为完全二叉树
    	if (NULL == root)
    		return 1;
    
    	// 初始化队列
    	Queue queue;
    	QueueInit(&queue);
    	QueuePush(&queue, root);
    
    	int flag = 0;
    
    	// 如果左右节点都存在则遍历下一个节点，如果左孩子存在但右孩子不存在则标记，
    	while (!QueueEmpty(&queue))
    	{ 
    		BTNode* cur = QueueFront(&queue);
    
    		if (flag)
    		{ 
    			// 从第一个不饱和节点之后，所有节点不能有孩子
    			if (cur->_left || cur->_right)
    			{ 
    				QueueDestroy(&queue);
    				return 0;
    			}
    		}
    		else
    		{ 
    			// 找第一个不饱和节点
    			if (cur->_left && cur->_right)
    			{ 
    				QueuePush(&queue, cur->_left);
    				QueuePush(&queue, cur->_right);
    			}
    			else if (cur->_left)
    			{ 
    				QueuePush(&queue, cur->_left);
    				flag = 1;
    			}
    			else if (cur->_right)
    			{ 
    				QueueDestroy(&queue);
    				return 0;
    			}
    			else
    			{ 
    				flag = 1;
    			}
    		}
    
    		QueuePop(&queue);
    	}
    
    	QueueDestroy(&queue);
    	return 1;
    }

# 五. 给定两种遍历方式确定树形 #

有好多题目都是给定了两种遍历方式，通过这两种遍历方式确定树形，并且求出另外一种遍历的结果。下文就会详细介绍如果通过两种方式确定另外一种遍历结果。

## 1. 前序 + 中序 ##

**求解步骤**

1.  根据前序遍历找到根节点。
2.  在中序遍历的结果中找到根的位置，以该位置将中序遍历的结果分为两个序列，该位置左侧就是根的左子树中点，该位置右侧就是根的右子树中点。
3.  递归还原左右子树。

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

## 2. 中序 + 后序 ##

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

## 3. 前序 + 后序 ##

前序：根 -> 左 -> 右  
  后序：左 -> 右 ->根  
  这两种遍历方式组合起来，根本无法分辨左右子树，所以这两种方式出现时，就不要费尽心思取计算树形了，都是徒劳的。

# 六. 总结 #

以上的所有内容，就是关于树相关的所有知识点，其中难免会出现一些错误，欢迎大家批评指正。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcxNzUyMA_size_16_color_FFFFFF_t_70_pic_center 20]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcxNzUyMA_size_16_color_FFFFFF_t_70_pic_center]: /images/20221022/62d17c4e89c24a2c9dff37f589befbd5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcxNzUyMA_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221022/4c13631554a94485b6553e4c9a4bfc2d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcxNzUyMA_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221022/2a325895613449968a87160210a89915.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcxNzUyMA_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221022/2ed0e75005344b6d9e262d326dc2a9e9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcxNzUyMA_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221022/ebf3d9d4e0d34fe294ab214d0bb672fc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcxNzUyMA_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221022/c9d257e9a761434989aea0942923ab10.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcxNzUyMA_size_16_color_FFFFFF_t_70_pic_center 6]: /images/20221022/992d29929e4141eb9bcc0f092c9ad6fb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcxNzUyMA_size_16_color_FFFFFF_t_70_pic_center 7]: /images/20221022/e6a393142f1d4b50b62af594fb5114e5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcxNzUyMA_size_16_color_FFFFFF_t_70_pic_center 8]: /images/20221022/898eb34b76c0407ab42c6667e4dca0d0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcxNzUyMA_size_16_color_FFFFFF_t_70_pic_center 9]: /images/20221022/297ccd4c93dd42309d2b5f42cede19c0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcxNzUyMA_size_16_color_FFFFFF_t_70_pic_center 10]: /images/20221022/537bc37524bc4fe8ae962855e0f492a7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcxNzUyMA_size_16_color_FFFFFF_t_70_pic_center 11]: /images/20221022/9415c7265f7844de9e9cc65b216e99ee.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcxNzUyMA_size_16_color_FFFFFF_t_70_pic_center 12]: /images/20221022/3c387f1eb95c4491bc0282857d542cb5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcxNzUyMA_size_16_color_FFFFFF_t_70_pic_center 13]: /images/20221022/783388da87d0498f90dfe00bcef816a0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcxNzUyMA_size_16_color_FFFFFF_t_70_pic_center 14]: /images/20221022/504cb54ad87c4f8fb2a056680fb93512.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcxNzUyMA_size_16_color_FFFFFF_t_70_pic_center 15]: /images/20221022/34f6c3dad02e4166b3769fd8b155ed17.png
[Link 1]: https://blog.csdn.net/weixin_43717520/article/details/117151413?spm=1001.2014.3001.5501
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcxNzUyMA_size_16_color_FFFFFF_t_70_pic_center 16]: /images/20221022/23eb15a058064e5d9708581a350e4541.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcxNzUyMA_size_16_color_FFFFFF_t_70_pic_center 17]: /images/20221022/4015bcdacaee4fe7aa4e3b40534e38c6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcxNzUyMA_size_16_color_FFFFFF_t_70_pic_center 18]: /images/20221022/3c2500331bf04ef997fb9eb07b6652ee.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcxNzUyMA_size_16_color_FFFFFF_t_70_pic_center 19]: /images/20221022/026a7e5be3e845b0b0ff458baaaf0d53.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcxNzUyMA_size_16_color_FFFFFF_t_70_pic_center 20]: /images/20221022/132f670160d244838e4dfd0c17945f73.png