树与二叉树

博主： wmicheng
发布时间：2025 年 02 月 10 日
28 次浏览
暂无评论
12935字数
分类：数据结构

## **树&二叉树基本概念**

| 树基本概念                              | 二叉树基本概念                                  |
| --------------------------------------- | ----------------------------------------------- |
| ![树的基本概念1](https://wmicheng.top/images/note/img/树的基本概念1.png) | ![二叉树的基本概念1](https://wmicheng.top/images/note/img/二叉树的基本概念1.png) |
| ![树的基本概念1](https://wmicheng.top/images/note/img/树的基本概念2.png) | ![二叉树的基本概念3](https://wmicheng.top/images/note/img/二叉树的基本概念3.png) |
| ![树的基本概念1](https://wmicheng.top/images/note/img/树的基本概念3.png) | ![二叉树的基本概念2](https://wmicheng.top/images/note/img/二叉树的基本概念2.png) |

> #### 相关定义

**祖先结点**：从一个结点往上一直走到的根结点叫做祖先结点

**子孙结点**：从一个结点出发，下面的结点都是子孙结点

**双亲结点**（父结点）：一个结点的直接前驱结点

**孩子结点**：一个结点的直接后继结点

**兄弟结点**：同属于一个父结点的结点

**堂兄弟结点**：（一般来说不同属于一个父结点但是）同一层的结点

**两结点的路径**：只能同下往上（或者从上往下）的线段个数，注意，如果需要拐弯的情况则称没有路径

**路径长度**：经过几条边

**结点的`层次`**（**深度**）：从上往下数的层数

**结点的`高度`**：从下往上数（越往上高度越高）

**树的`深度`：整个数的层数**

`结点的度：对于这个结点总共有几个孩子（分支`）**，度为0的结点也就是叶子结点

`数的度：各个结点的度的最大值`

**注意深度和高度、层次一般从`1`开始，除非题意要求从`0`开始**

## 有序树和无序树

- **有序树**：树中结点各子树从左往右是`有次序`的，**不能**交换
- **无序树**：树中结点各子树从左往右是`没有次序`的，**可以**交换

## 森林

表示有`n`棵**互不相交**的树组成的集合
森林和树可以互相表示

> #### 树的性质

**结点数=总度数+1**（这里的总度数表示每个结点度的和）

**度为m的树和m叉树的区别**

| 度为m的树                         | m叉树                         |
| --------------------------------- | ----------------------------- |
| 任意结点的度≤m（最多m个孩子）     | 任意结点的度≤m（最多m个孩子） |
| 至少有一个结点的度=m（有m个孩子） | 允许所有的结点的度都\

**度为m的树第i层至多有mi-1个结点**

**高度为h的m叉树至多有$\frac{m^h-1}{m-1}$ 个结点**（使用等比数列计算得到）

**高度为h，的m叉树至少有h个结点（每层只有一个结点）**

**高度为h，度为m的树至少有h+m-1个结点（只有一层有m个结点，其它层均为1个结点）**

**具有n个结点的m叉树最小高度为$⌈log_m(n(m-1)+1)⌉$**

> #### 二叉树的性质

| 二叉树的性质                            | 完全二叉树的性质                                |
| --------------------------------------- | ----------------------------------------------- |
| ![二叉树的性质1](https://wmicheng.top/images/note/img/二叉树的性质1.png) | ![完全二叉树的性质1](https://wmicheng.top/images/note/img/完全二叉树的性质1.png) |
| ![二叉树的性质2](https://wmicheng.top/images/note/img/二叉树的性质2.png) | ![完全二叉树的性质2](https://wmicheng.top/images/note/img/完全二叉树的性质2.png) |
| ![二叉树的性质3](https://wmicheng.top/images/note/img/二叉树的性质3.png) | ![完全二叉树的性质3](https://wmicheng.top/images/note/img/完全二叉树的性质3.png) |

<https://wmicheng.top/images/note/img src="https://wmicheng.top/images/note/img/完全二叉树的性质4.png" alt="完全二叉树的性质4" style="zoom: 80%;" />

> #### 几种特殊的二叉树

| 满二叉树                            | 完全二叉树                          |
| ----------------------------------- | ----------------------------------- |
| ![特殊二叉树1](https://wmicheng.top/images/note/img/特殊二叉树1.png) | ![特殊二叉树2](https://wmicheng.top/images/note/img/特殊二叉树2.png) |

| 二叉排序树                                                   | 平衡二叉树                                                   |
| ------------------------------------------------------------ | ------------------------------------------------------------ |
|  |  |

> #### 树与二叉树概念总结

|                   树                    |                        二叉树                         |
| :-------------------------------------: | :---------------------------------------------------: |
| ![树的基本概念4](https://wmicheng.top/images/note/img/树的基本概念4.png) | ![二叉树的基本概念4png](https://wmicheng.top/images/note/img/二叉树的基本概念4png.png) |

## **二叉树存储结构**

| 二叉树顺序存储                              | 二叉树链式存储                              |
| ------------------------------------------- | ------------------------------------------- |
| ![二叉树顺序存储1](https://wmicheng.top/images/note/img/二叉树顺序存储1.png) | ![二叉树链式存储1](https://wmicheng.top/images/note/img/二叉树链式存储1.png) |
| ![二叉树顺序存储2](https://wmicheng.top/images/note/img/二叉树顺序存储2.png) | ![二叉树链式存储2](https://wmicheng.top/images/note/img/二叉树链式存储2.png) |
| ![二叉树顺序存储3](https://wmicheng.top/images/note/img/二叉树顺序存储3.png) | ![二叉树链式存储3](https://wmicheng.top/images/note/img/二叉树链式存储3.png) |
| ![二叉树顺序存储4](https://wmicheng.top/images/note/img/二叉树顺序存储4.png) | ![二叉树链式存储4](https://wmicheng.top/images/note/img/二叉树链式存储4.png) |

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

`树的遍历`

**遍历**：按照某种次序把所有结点都访问一遍

**层序遍历**：基于树的层次特性确定的次序规则

**先/中/后序遍历**：基于树的递归特性确定的次序规则

`二叉树的遍历`

**二叉树的递归特性**：

- 要么是个空二叉树
- 要么就是由“根结点+左子树+右子树”组成的二叉树

**先序遍历**：`根左右`（NLR）

**中序遍历**：`左根右`（LNR）

**后序遍历**：`左右根`（LRN）

![二叉树的遍历](https://wmicheng.top/images/note/img/二叉树的遍历.png)

![先序遍历](https://wmicheng.top/images/note/img/先序遍历.png)

> #### 中序遍历

![中序遍历](https://wmicheng.top/images/note/img/中序遍历.png)

> #### 后序遍历

![后序遍历](https://wmicheng.top/images/note/img/后序遍历.png)

`二叉树遍历总结`

- 空间复杂度为$O(h)$，$h$为树的高度
- 每个结点都会被路过3次

`求树的深度`
![]([https://wmicheng.top/images/note/img/后序遍历.png](https://wmicheng.top/images/note/img/TreeDeep.png))

- 是后序遍历的变种
- 先后访问左右儿子，得出对应深度返回左右儿子深度更高的那个就是树的深度

### 二叉树的层序遍历

| 算法思想                                        | 代码实现                                        |
| ----------------------------------------------- | ----------------------------------------------- |
| ![二叉树的层序遍历1](https://wmicheng.top/images/note/img/二叉树的层序遍历1.png) | ![二叉树的层序遍历2](https://wmicheng.top/images/note/img/二叉树的层序遍历2.png) |

### 由遍历序列构造二叉树

`结论`：前序、后序、层序序列的**两两组合**无法唯一确定一颗二叉树（`必须与中序结合`才能确定一颗二叉树）

**通过两种遍历序列确定二叉树**：

> #### 前序+中序

![二叉树的遍历1](https://wmicheng.top/images/note/img/二叉树的遍历1.png)

> #### 中序+后序

![二叉树的遍历2](https://wmicheng.top/images/note/img/二叉树的遍历2.png)

> #### 层序+中序

![二叉树的遍历3](https://wmicheng.top/images/note/img/二叉树的遍历3.png)

## **线索二叉树的概念**

> #### 中序遍历的问题

如何找到指定结点p在q 中序遍历序列中的前驱？

如何找到p的中序后继？

能否从一个指定结点开始中序遍历？

完成上述需求的思路：

- 从根结点出发，重新进行一次中序遍历，指针q记录当前访问的结点，指针pre记录上一个被访问的结点
- 当q == p时，pre为前驱
- 当pre == p时，q为后继

缺点：找前驱、后继很不方便； 操作必须从根开始

> #### 中序线索二叉树

> #### 线索二叉树的存储结构

![线索二叉树存储结构](https://wmicheng.top/images/note/img/线索二叉树存储结构.png)

先/中/后序线索二叉树同理

> #### 三种线索二叉树的对比

![三种线索二叉树存储结构](https://wmicheng.top/images/note/img/三种线索二叉树存储结构.png)

## 二叉树的线索化

> #### 通过头结点找到中序前驱

`中序二叉树线索化`

| 中序二叉树线索化                                | 中序二叉树线索化                                |
| ----------------------------------------------- | ----------------------------------------------- |
| ![中序二叉树线索化1](https://wmicheng.top/images/note/img/中序二叉树线索化1.png) | ![中序二叉树线索化2](https://wmicheng.top/images/note/img/中序二叉树线索化2.png) |

`先序二叉树线索化`

| 先序二叉树线索化                              | 先序二叉树线索化                                |
| --------------------------------------------- | ----------------------------------------------- |
| ![先序二叉树线索化](https://wmicheng.top/images/note/img/先序二叉树线索化.png) | ![先序二叉树线索化2](https://wmicheng.top/images/note/img/先序二叉树线索化2.png) |

- 由于先序遍历先遍历根结点然后再遍历左结点，若左孩子为空，通过线索化后会指回前驱结点（他的根结点）
- 这时在此访问左孩子时候会又访问回根结点，因此需要增加一个判断来确定左孩子不是真正的左孩子而是线索化后的前驱结点

`后序二叉树线索化`

![后序二叉树线索化2](https://wmicheng.top/images/note/img/后序二叉树线索化2.png)

![先序二叉树线索化23](https://wmicheng.top/images/note/img/先序二叉树线索化23.png)

> #### 在线索二叉树中找前驱后驱

`中序线索二叉树找中序前驱后继`

| 中序线索二叉树找中序前驱                                     | 中序线索二叉树找中序后继                                     |
| ------------------------------------------------------------ | ------------------------------------------------------------ |
| ![中序线索二叉树找中序前驱1](https://wmicheng.top/images/note/img/中序线索二叉树找中序前驱1.png) | ![中序线索二叉树找中序后继1](https://wmicheng.top/images/note/img/中序线索二叉树找中序后继1.png) |
| ![中序线索二叉树找中序前驱2](https://wmicheng.top/images/note/img/中序线索二叉树找中序前驱2.png) | ![中序线索二叉树找中序后继2](https://wmicheng.top/images/note/img/中序线索二叉树找中序后继2.png) |

`先序线索二叉树找先序前驱后继`

| 先序线索二叉树找先序前驱                                     | 先序线索二叉树找先序后继                                     |
| ------------------------------------------------------------ | ------------------------------------------------------------ |
| ![先序线索二叉树找先序前驱1](https://wmicheng.top/images/note/img/先序线索二叉树找先序前驱1.png) | ![先序线索二叉树找先序后继1](https://wmicheng.top/images/note/img/先序线索二叉树找先序后继1.png) |

![先序线索二叉树找先序前驱2](https://wmicheng.top/images/note/img/先序线索二叉树找先序前驱2.png)

在先序线索二叉树中找到指定结点\*p的先序后继next

- 若p->rtag == 1，则next = p->rchild
- 若p->rtag == 0，说明p必定有右孩子
  
  - 若p有左孩子，则先序后继为左孩子
  - 若p没有左孩子，则先序后继为右孩子

在先序线索二叉树中找到指定结点\*p的先序前驱pre

- 若p->ltag == 1，则pre = p->lchild
- 若p->ltag == 0，说明p必定有左孩子
  
  - 先序遍历中，左右子树中的结点只可能是根的后继，不可能是前驱
  - 方法1：用土办法从头开始先序遍历
  - 方法2：可以改用三叉链表以找到父结点

`后序线索二叉树找后序前驱后继`

| 后序线索二叉树找后序前驱                                     | 后序线索二叉树找后序后继                                     |
| ------------------------------------------------------------ | ------------------------------------------------------------ |
| ![后序线索二叉树找后序前驱](https://wmicheng.top/images/note/img/后序线索二叉树找后序前驱.png) | ![后序线索二叉树找后序后继](https://wmicheng.top/images/note/img/后序线索二叉树找后序后继.png) |

![后序线索二叉树找后序后继1](https://wmicheng.top/images/note/img/后序线索二叉树找后序后继1.png)

在后序线索二叉树中找到指定结点\*p的后序前驱pre

- 若p->ltag == 1，则pre = p->lchild
- 若p->ltag == 0，说明p必有左孩子
  
  - 若p有右孩子，则后序前驱为右孩子
  - 若p没有右孩子，则后序前驱为左孩子

在后序线索二叉树中找到指定结点\*p的后序后继next

- 若p->rtag == 1，则next = p->rchild
- 若p->rtag == 0，说明p必定有右孩子
  
  - 后序遍历中，左右子树中的结点只可能是根的前驱，不可能是后继
  - 方法1：用土办法从头开始先序遍历
  - 方法2：可以改用三叉链表以找到父结点

![后序线索二叉树找后序后继2](https://wmicheng.top/images/note/img/后序线索二叉树找后序后继2.png)

## **树的储存结构**

> #### 双亲表示法（顺序存储）

每个结点中保存指向双亲的“指针”，`data`，`parrent`

根结点固定存储在0，-1表示没有双亲

新增数据元素，无需按逻辑上的次序存储，只需说明新增元素的data，parrent即可

删除数据元素

- 方案1：把要删除的数据元素data设为空，parent设为-1
- 方案2：将数组尾部的数据元素覆盖要删除的数据元素

查询数据元素

- 优点：查指定结点的双亲很方便
- 缺点：查指定结点的孩子只能从头遍历

> #### 孩子表示法（顺序+链式存储）

优点：找孩子很方便

缺点：找双亲（父节点） 不方便，只能遍历每个链表 适用于“找孩子”多，“找父亲”少的应用场景。

如：服务流程树

| 双亲表示法（顺序存储）              | 孩子表示法（顺序+链式存储）         |
| ----------------------------------- | ----------------------------------- |
| ![双亲表示法](https://wmicheng.top/images/note/img/双亲表示法.png)   | ![孩子表示法2](https://wmicheng.top/images/note/img/孩子表示法2.png) |
| ![双亲表示法2](https://wmicheng.top/images/note/img/双亲表示法2.png) | ![孩子表示法3](https://wmicheng.top/images/note/img/孩子表示法3.png) |
| ![双亲表示法3](https://wmicheng.top/images/note/img/双亲表示法3.png) | ![孩子表示法](https://wmicheng.top/images/note/img/孩子表示法.png)   |

### `孩子兄弟表示法（链式存储）★★★`

![孩兄弟表示法1](https://wmicheng.top/images/note/img/孩兄弟表示法1.png)

`规则`：

1. 左指针指向第一个孩子
2. 右指针指向自己的第一个兄弟

> #### 森林和二叉树的转换

本质：用二叉链表存储森林

规则：

- 各个树的根结点视为兄弟关系

左指针指向第一个孩子

- 右指针指向自己的第一个兄弟

![孩兄弟表示法2](https://wmicheng.top/images/note/img/孩兄弟表示法2.png)

![孩兄弟表示法3](https://wmicheng.top/images/note/img/孩兄弟表示法3.png)

### 树和森林的遍历

> #### 树的先根遍历

- 先根遍历：若树非空，先访问根结点，再依次对每棵子树进行先根遍历。
- 树的先根遍历序列与这棵树相应二叉树的先序序列相同。

![树的先根遍历](https://wmicheng.top/images/note/img/树的先根遍历.png)

> #### 树的后根遍历

- 后根遍历：若树非空，先依次对每棵子树进行后根遍历，最后再访问根结点
- 树的后根遍历序列与这棵树相应二叉树的中序序列相同
- 也被称为深度优先遍历

![树的后根遍历](https://wmicheng.top/images/note/img/树的后根遍历.png)

> #### 树的层次遍历

用**队列**实现，又被称为`广度优先遍历`

步骤

- 若树非空，则根结点入队

若队列非空，队头元素出队并访问，同时将该元素的孩子依次入队

- 重复第二步直到队列为空

![树的层次遍历](https://wmicheng.top/images/note/img/树的层次遍历.png)

**森林的先序遍历：**

若森林为非空，则按如下规则进行遍历：

- 访问森林中第一棵树的根结点。
- 先序遍历第一棵树中根结点的子树森林。
- 先序遍历除去第一棵树之后剩余的树构成的森林。

效果等同于依次对各个树进行先根遍历

用孩子兄弟表示法转换为二叉树，效果等同于依次对二叉树的先序遍历

| 森林的先序遍历                            |                                             |
| ----------------------------------------- | ------------------------------------------- |
| ![森林的先序遍历](https://wmicheng.top/images/note/img/森林的先序遍历.png) | ![森林的先序遍历1](https://wmicheng.top/images/note/img/森林的先序遍历1.png) |

**森林的中序遍历：**

若森林为非空，则按如下规则进行遍历：

- 中序遍历森林中第一棵树的根结点的子树森林。
- 访问第一棵树的根结点。
- 中序遍历除去第一棵树之后剩余的树构成的森林。

效果等同于依次对各个树进行后根遍历

用孩子兄弟表示法转换为二叉树，效果等同于依次对二叉树的中序遍历

| 森林的中序遍历                              |                                             |
| ------------------------------------------- | ------------------------------------------- |
| ![森林的中序遍历1](https://wmicheng.top/images/note/img/森林的中序遍历1.png) | ![森林的中序遍历2](https://wmicheng.top/images/note/img/森林的中序遍历2.png) |

## 哈夫曼树

**带权路径长度：**

- 结点的权：有某种现实含义的数值（如：表示结点的重要性等）
- 结点的带权路径长度：从树的根到该结点的路径长度（经过的边数）与该结点上权值的乘积
- 树的带权路径长度：树中所有叶结点的带权路径长度之和（WPL, Weighted Path Length）

**哈夫曼树的定义：**

在含有n个带权叶结点的二叉树中，其中带权路径长度（WPL）最小的二叉树称为哈夫曼树，也称最优二叉树

![哈夫曼树](https://wmicheng.top/images/note/img/哈夫曼树.png)

**哈夫曼树的构造：**

![哈夫曼树1](https://wmicheng.top/images/note/img/哈夫曼树1.png)

**哈夫曼编码：**

![哈夫曼树2](https://wmicheng.top/images/note/img/哈夫曼树2.png)

![哈夫曼树3](https://wmicheng.top/images/note/img/哈夫曼树3.png)

## 并查集

![并查集](https://wmicheng.top/images/note/img/并查集.png)

**定义：**

并查集（Disjoint Set）是逻辑结构`集合`的一种具体实现，只进行“`并`”和“`查`”两种基本操作

**并查集的基本操作：**

![并查集2](https://wmicheng.top/images/note/img/并查集2.png)

**初始化：**

![并查集3](https://wmicheng.top/images/note/img/并查集3.png)

S\[\]实际上就是树的双亲表示法，里面的值就是自己对应根结点的下标

**并、查：**

**时间复杂度分析：**

- Find操作最坏时间复杂度O(n)
- Union操作时间复杂度O(1)

**Union操作的优化：**

- 在每次Union操作构建树的时候，尽量让树不长高
- 用根结点的绝对值表示树的结点总数（根结点从-1改成-（树的总结点））
- Union操纵，让小树合并到大树
- 该方法构造的树高不超过$[log_2n]+1$
- Find最坏时间复杂度变为$O(log_2n)$

![并查集5](https://wmicheng.top/images/note/img/并查集5.png)

![并查集6](https://wmicheng.top/images/note/img/并查集6.png)

---

最后修改：2025 年 02 月 11 日

如果觉得我的文章对你有用，请随意赞赏

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

树与二叉树

wmicheng • 2025 年 02 月 10 日

## **树&二叉树基本概念**

> #### 相关定义

**祖先结点**：从一个结点往上一直走到的根结点叫做祖先结点

**子孙结点**：从一个结点出发，下面的结点都是子孙结点

**双亲结点**（父结点）：一个结点的直接前驱结点

**孩子结点**：一个结点的直接后继结点

**兄弟结点**：同属于一个父结点的结点

**堂兄弟结点**：（一般来说不同属于一个父结点但是）同一层的结点

**两结点的路径**：只能同下往上（或者从上往下）的线段个数，注意，如果需要拐弯的情况则称没有路径

**路径长度**：经过几条边

**结点的`层次`**（**深度**）：从上往下数的层数

**结点的`高度`**：从下往上数（越往上高度越高）

**树的`深度`：整个数的层数**

`结点的度：对于这个结点总共有几个孩子（分支`）**，度为0的结点也就是叶子结点

`数的度：各个结点的度的最大值`

**注意深度和高度、层次一般从`1`开始，除非题意要求从`0`开始**

## 有序树和无序树

- **有序树**：树中结点各子树从左往右是`有次序`的，**不能**交换
- **无序树**：树中结点各子树从左往右是`没有次序`的，**可以**交换

## 森林

表示有`n`棵**互不相交**的树组成的集合
森林和树可以互相表示

> #### 树的性质

**结点数=总度数+1**（这里的总度数表示每个结点度的和）

**度为m的树和m叉树的区别**

**度为m的树第i层至多有mi-1个结点**

**高度为h的m叉树至多有$\frac{m^h-1}{m-1}$ 个结点**（使用等比数列计算得到）

**高度为h，的m叉树至少有h个结点（每层只有一个结点）**

**高度为h，度为m的树至少有h+m-1个结点（只有一层有m个结点，其它层均为1个结点）**

**具有n个结点的m叉树最小高度为$⌈log_m(n(m-1)+1)⌉$**

> #### 二叉树的性质

<https://wmicheng.top/images/note/img src="https://wmicheng.top/images/note/img/完全二叉树的性质4.png" alt="完全二叉树的性质4" style="zoom: 80%;" />

> #### 几种特殊的二叉树

> #### 树与二叉树概念总结

## **二叉树存储结构**

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

`树的遍历`

**遍历**：按照某种次序把所有结点都访问一遍

**层序遍历**：基于树的层次特性确定的次序规则

**先/中/后序遍历**：基于树的递归特性确定的次序规则

`二叉树的遍历`

**二叉树的递归特性**：

- 要么是个空二叉树
- 要么就是由“根结点+左子树+右子树”组成的二叉树

**先序遍历**：`根左右`（NLR）

**中序遍历**：`左根右`（LNR）

**后序遍历**：`左右根`（LRN）

![二叉树的遍历](https://wmicheng.top/images/note/img/二叉树的遍历.png)

![先序遍历](https://wmicheng.top/images/note/img/先序遍历.png)

> #### 中序遍历

![中序遍历](https://wmicheng.top/images/note/img/中序遍历.png)

> #### 后序遍历

![后序遍历](https://wmicheng.top/images/note/img/后序遍历.png)

`二叉树遍历总结`

- 空间复杂度为$O(h)$，$h$为树的高度
- 每个结点都会被路过3次

`求树的深度`
![]([https://wmicheng.top/images/note/img/后序遍历.png](https://wmicheng.top/images/note/img/TreeDeep.png))

- 是后序遍历的变种
- 先后访问左右儿子，得出对应深度返回左右儿子深度更高的那个就是树的深度

### 二叉树的层序遍历

### 由遍历序列构造二叉树

`结论`：前序、后序、层序序列的**两两组合**无法唯一确定一颗二叉树（`必须与中序结合`才能确定一颗二叉树）

**通过两种遍历序列确定二叉树**：

> #### 前序+中序

![二叉树的遍历1](https://wmicheng.top/images/note/img/二叉树的遍历1.png)

> #### 中序+后序

![二叉树的遍历2](https://wmicheng.top/images/note/img/二叉树的遍历2.png)

> #### 层序+中序

![二叉树的遍历3](https://wmicheng.top/images/note/img/二叉树的遍历3.png)

## **线索二叉树的概念**

> #### 中序遍历的问题

如何找到指定结点p在q 中序遍历序列中的前驱？

如何找到p的中序后继？

能否从一个指定结点开始中序遍历？

完成上述需求的思路：

- 从根结点出发，重新进行一次中序遍历，指针q记录当前访问的结点，指针pre记录上一个被访问的结点
- 当q == p时，pre为前驱
- 当pre == p时，q为后继

缺点：找前驱、后继很不方便； 操作必须从根开始

> #### 中序线索二叉树

> #### 线索二叉树的存储结构

![线索二叉树存储结构](https://wmicheng.top/images/note/img/线索二叉树存储结构.png)

先/中/后序线索二叉树同理

> #### 三种线索二叉树的对比

![三种线索二叉树存储结构](https://wmicheng.top/images/note/img/三种线索二叉树存储结构.png)

## 二叉树的线索化

> #### 通过头结点找到中序前驱

`中序二叉树线索化`

`先序二叉树线索化`

`后序二叉树线索化`

![后序二叉树线索化2](https://wmicheng.top/images/note/img/后序二叉树线索化2.png)

![先序二叉树线索化23](https://wmicheng.top/images/note/img/先序二叉树线索化23.png)

> #### 在线索二叉树中找前驱后驱

`中序线索二叉树找中序前驱后继`

`先序线索二叉树找先序前驱后继`

![先序线索二叉树找先序前驱2](https://wmicheng.top/images/note/img/先序线索二叉树找先序前驱2.png)

在先序线索二叉树中找到指定结点\*p的先序后继next

- 若p->rtag == 1，则next = p->rchild
- 若p->rtag == 0，说明p必定有右孩子
  
  - 若p有左孩子，则先序后继为左孩子
  - 若p没有左孩子，则先序后继为右孩子

在先序线索二叉树中找到指定结点\*p的先序前驱pre

`后序线索二叉树找后序前驱后继`

![后序线索二叉树找后序后继1](https://wmicheng.top/images/note/img/后序线索二叉树找后序后继1.png)

在后序线索二叉树中找到指定结点\*p的后序前驱pre

- 若p->ltag == 1，则pre = p->lchild
- 若p->ltag == 0，说明p必有左孩子
  
  - 若p有右孩子，则后序前驱为右孩子
  - 若p没有右孩子，则后序前驱为左孩子

在后序线索二叉树中找到指定结点\*p的后序后继next

![后序线索二叉树找后序后继2](https://wmicheng.top/images/note/img/后序线索二叉树找后序后继2.png)

## **树的储存结构**

> #### 双亲表示法（顺序存储）

每个结点中保存指向双亲的“指针”，`data`，`parrent`

根结点固定存储在0，-1表示没有双亲

新增数据元素，无需按逻辑上的次序存储，只需说明新增元素的data，parrent即可

删除数据元素

- 方案1：把要删除的数据元素data设为空，parent设为-1
- 方案2：将数组尾部的数据元素覆盖要删除的数据元素

查询数据元素

- 优点：查指定结点的双亲很方便
- 缺点：查指定结点的孩子只能从头遍历

> #### 孩子表示法（顺序+链式存储）

优点：找孩子很方便

缺点：找双亲（父节点） 不方便，只能遍历每个链表 适用于“找孩子”多，“找父亲”少的应用场景。

如：服务流程树

### `孩子兄弟表示法（链式存储）★★★`

![孩兄弟表示法1](https://wmicheng.top/images/note/img/孩兄弟表示法1.png)

`规则`：

1. 左指针指向第一个孩子
2. 右指针指向自己的第一个兄弟

> #### 森林和二叉树的转换

本质：用二叉链表存储森林

规则：

- 各个树的根结点视为兄弟关系

左指针指向第一个孩子

- 右指针指向自己的第一个兄弟

![孩兄弟表示法2](https://wmicheng.top/images/note/img/孩兄弟表示法2.png)

![孩兄弟表示法3](https://wmicheng.top/images/note/img/孩兄弟表示法3.png)

### 树和森林的遍历

> #### 树的先根遍历

- 先根遍历：若树非空，先访问根结点，再依次对每棵子树进行先根遍历。
- 树的先根遍历序列与这棵树相应二叉树的先序序列相同。

![树的先根遍历](https://wmicheng.top/images/note/img/树的先根遍历.png)

> #### 树的后根遍历

![树的后根遍历](https://wmicheng.top/images/note/img/树的后根遍历.png)

> #### 树的层次遍历

用**队列**实现，又被称为`广度优先遍历`

步骤

- 若树非空，则根结点入队

若队列非空，队头元素出队并访问，同时将该元素的孩子依次入队

- 重复第二步直到队列为空

![树的层次遍历](https://wmicheng.top/images/note/img/树的层次遍历.png)

**森林的先序遍历：**

若森林为非空，则按如下规则进行遍历：

- 访问森林中第一棵树的根结点。
- 先序遍历第一棵树中根结点的子树森林。
- 先序遍历除去第一棵树之后剩余的树构成的森林。

效果等同于依次对各个树进行先根遍历

用孩子兄弟表示法转换为二叉树，效果等同于依次对二叉树的先序遍历

**森林的中序遍历：**

若森林为非空，则按如下规则进行遍历：

- 中序遍历森林中第一棵树的根结点的子树森林。
- 访问第一棵树的根结点。
- 中序遍历除去第一棵树之后剩余的树构成的森林。

效果等同于依次对各个树进行后根遍历

用孩子兄弟表示法转换为二叉树，效果等同于依次对二叉树的中序遍历

## 哈夫曼树

**带权路径长度：**

**哈夫曼树的定义：**

在含有n个带权叶结点的二叉树中，其中带权路径长度（WPL）最小的二叉树称为哈夫曼树，也称最优二叉树

![哈夫曼树](https://wmicheng.top/images/note/img/哈夫曼树.png)

**哈夫曼树的构造：**

![哈夫曼树1](https://wmicheng.top/images/note/img/哈夫曼树1.png)

**哈夫曼编码：**

![哈夫曼树2](https://wmicheng.top/images/note/img/哈夫曼树2.png)

![哈夫曼树3](https://wmicheng.top/images/note/img/哈夫曼树3.png)

## 并查集

![并查集](https://wmicheng.top/images/note/img/并查集.png)

**定义：**

并查集（Disjoint Set）是逻辑结构`集合`的一种具体实现，只进行“`并`”和“`查`”两种基本操作

**并查集的基本操作：**

![并查集2](https://wmicheng.top/images/note/img/并查集2.png)

**初始化：**

![并查集3](https://wmicheng.top/images/note/img/并查集3.png)

S\[\]实际上就是树的双亲表示法，里面的值就是自己对应根结点的下标

**并、查：**

**时间复杂度分析：**

- Find操作最坏时间复杂度O(n)
- Union操作时间复杂度O(1)

**Union操作的优化：**

![并查集5](https://wmicheng.top/images/note/img/并查集5.png)

![并查集6](https://wmicheng.top/images/note/img/并查集6.png)

---

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

树与二叉树

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款