第五章树与二叉树

第五章树与二叉树

5.1 树的基本概念

5.1.1 树的定义

树是 n（n≥0）个结点的有限集合，n = 0 时，称为空树，这是一种特殊情况。

在任意一棵非空树中应满足：

1）有且仅有一个特定的称为根的结点。

2）当 n > 1 时，其余结点可分为 m（m > 0）个互不相交的有限集合 T 1, T 2,…, Tm，其中每个集合本身又是一棵树，并且称为根结点的子树。

非空树的特性：

1. 有且仅有一个根节点
2. 没有后继的结点称为 “叶子结点”（或终端结点）
3. 有后继的结点称为 “分支结点”（或非终端结点）
4. 除了根节点外，任何一个结点都有且仅有一个前驱
5. 每个结点可以有 0 个或多个后继。

树是一种递归定义的数据结构

5.1.2 基本术语

1. 结点的度一个结点的子结点个数
2. 树的度树中结点的最大度数
3. 结点的深度 从根结点开始自顶向下逐层累加
4. 结点的高度 从叶结点开始自底向上逐层累加
5. 树的高度 (深度) 树中结点的最大层数
6. 两结点之间的路径 两结点之间经过的结点序列
7. 路径长度 路径上经过的边的个数
8. 注意树中的分支是有向的 (双亲指向孩子), 路径从上向下, 两个孩子之间不存在路径

有序树——逻辑上看，树中结点的各子树从左至右是有次序的，不能互换

无序树——逻辑上看，树中结点的各子树从左至右是无次序的，可以互换

** 森林：** 森林是 m（m≥0）棵互不相交的树的集合

5.1.3 树的性质

1. 结点数 = 总度数 + 1
2. 度为 m 的树、m 叉树的区别

3. 度为 m 的树第 i 层至多有 mi-1 个结点（i≥1）

   M 叉树第 i 层至多有 mi-1 个结点（i≥1）

4. 高度为 h 的 m 叉树至少有 h 个结点

   高度为 h、度为 m 的树至少有 h+m-1 个结点

5. 高度为 h 的 m 叉树至多有 (mh -1)/m-1 个结点

6. 具有 n 个结点的 m 叉树的最小高度为 [logm (n (m - 1) + 1)]

   

5.2 二叉树的概念

5.2.1 二叉树的定义及主要特征

二叉树是 n（n≥0）个结点的有限集合：

① 或者为空二叉树，即 n = 0。

② 或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别是一棵二叉树。

特点：①每个结点至多只有两棵子树 ②左右子树不能颠倒（二叉树是有序树）

二叉树与度为 2 的有序树的区别

1. 度为 2 的树至少有 3 个结点, 二叉树可为空

2. 度为 2 的有序树的孩子的左右次序相对于另一个孩子无须区分左右

   二叉树是有序树

特殊的二叉树

1. 满二叉树：一棵高度为 h，且含有 2 h - 1 个结点的二叉树

   树中的每层都含有最多的结点，只有最后一层有叶子结点且不存在度为 1 的结点

2. 满二叉树：当且仅当其每个结点都与高度为 h 的满二叉树中编号为 1～n 的结点一一对应时，称为完全二叉树

   叶子结点只在最大的两层上 ，若有度为 1 的结点, 只有一个, 该结点只能是左孩子

3. 二叉排序树

   （1）左子树上所有结点的关键字小于根结点

   （2）右子树上所有结点的关键字大于根结点

   （3）左右子树又各是一颗二叉排序树

   

4. 平衡二叉树：树上任一结点的左子树和右子树的深度之差不超过 1（搜索效率高）

5.2.2 二叉树的性质

1. 设非空二叉树中度为 0、1 和 2 的结点个数分别为 n 0、n 1 和 n 2，则 n 0 = n 2 + 1 （叶子结点比二分支结点多一个）

2. 二叉树第 i 层至多有 2 i-1 个结点（i≥1）

   M 叉树第 i 层至多有 mi-1 个结点（i≥1）

3. 高度为 h 的 m 叉树至多有 (mh -1)/m-1 个结点

   高度为 h 的 2 叉树至多有 2 h-1 个结点

完全二叉树的常见考点

1. 具有 n 个（n > 0）结点的完全二叉树的高度 h 为 log 2 (n + 1) 或 log 2 n + 1

2. 对于完全二叉树，可以由的结点数 n 推出度为 0、1 和 2 的结点个数为 n 0、n 1 和 n 2

   若完全二叉树有 2 k 个（偶数）个结点，则必有 n 1=1， n 0 = k， n 2 = k-1

   若完全二叉树有 2 k-1 个（奇数）个结点，则必有 n 1=0， n 0 = k， n 2 = k-1

5.2.3 二叉树的存储结构

顺序存储

几个重要常考的基本操作：

1. I 的左孩子 ——2 i
2. I 的右孩子 ——2 i+1
3. I 的父节点—— i/2
4. I 所在的层次 —— log 2 (n + 1) 或 log 2 n+ 1

若完全二叉树中共有 n 个结点，则

1. 判断 i 是否有左孩子？ ——2 i ≤ n
2. 判断 i 是否有右孩子？ ——2 i+1 ≤ n
3. 判断 i 是否是叶子 / 分支结点？——i > n/2

二叉树的顺序存储中，一定要把二叉树的结点编号与完全二叉树对应起来

最坏情况：高度为 h 且只有 h 个结点的单支树（所有结点只有右孩子），也至少需要 2 h-1 个存储单元

结论：二叉树的顺序存储结构，只适合存储完全二叉树

链式存储

1. 二叉链表 3 个域: data, lchild, rchild

2. N 个结点的二叉链表有 n+1 个空链域 (根结点不用指针) 形成线索链表

5.3 二叉树的遍历和线索二叉树

5.3.1 二叉树的遍历

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

先序遍历：根左右（NLR）

中序遍历：左根右（LNR）

后序遍历：左右根（LRN）

层序遍历

算法思想：

①初始化一个辅助队列

②根结点入队

③若队列非空，则队头结点出队，访问该结点，并将其左、右孩子插入队尾（如果有的话）

④重复③直至队列为空

由遍历序列构造二叉树

若只给出一棵二叉树的前 / 中 / 后 / 层序遍历序列中的一种，不能唯一确定一棵二叉树

1. 先序和中序

（1）先序中: 第一个为根结点

（2）中序中: 根结点分割成两个子序列, 前左子树, 后右子树

（3）先序中: 找到两个子序列, 各自的第一个结点又是根结点

2. 后序和中序 后序最后一个结点相当于先序第一个结点

   

3. 层序和后序不可以

   

5.3.2 线索二叉树 (没理解)

目的: 加快查找结点前驱和后继的速度

线索: 指向前驱和后继的指针

线索化: 对二叉树以某种次序遍历使其成为线索二叉树的过程

无左子树, 令 lchild 指向前驱结点; 无右子树, 令 rchild 指向后继结点前驱, 后继由具体的遍历方式决定

二叉树线索化

5.4 树、森林

5.4.1 树的存储结构

双亲表示法（顺序存储）

1. 定义: 连续空间存储, 每个结点增设一个伪指针, 指示双亲在数组中位置, 根结点下标为 0, 其伪指针为 - 1
2. 特点: 可以很快得到双亲, 但求孩子要遍历整个结构

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

1. 定义：顺序存储各个节点，每个结点中保存孩子链表头指针

2. 特点: 求孩子很方便, 求双亲不方便

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

1. 定义: 左指针指向第一个孩子, 右指针指向第一个兄弟, 二叉链表作为存储结构
2. 优点: 方便实现树转化为二叉树, 易于查找孩子
3. 缺点: 查找双亲麻烦, 若增设 parent 指向双亲, 会方便

5.4.2 树、森林和二叉树的转换

树转换为二叉树

左指针指向第一个孩子, 右指针指向第一个兄弟, 根没有兄弟, 二叉树没有右子树

森林转化为二叉树

森林中的树依次转化为二叉树，每棵二叉树的根依次作为上一颗二叉树的右子树

二叉树转化为森林

1. 二叉树的根及左子树作为第一棵树的二叉树形态, 再转换为树 (右孩子变为兄弟)
2. 根的右子树及其左孩子作为第二棵树, 右孩子作为第三棵树, 反复下去

5.4.3 树和森林的遍历

树的先根遍历（深度优先遍历）

先访问根, 再从左到右遍历每棵子树, 与相应二叉树的先序序列相同

树的后根遍历（深度优先遍历）

从左到右遍历每棵子树, 再访问根，与这棵树相应二叉树的中序序列相同

树的层次遍历（广度优先遍历）

①若树非空，则根节点入队

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

③重复②直到队列为空

森林的先序遍历 == 依次对各个子树进行先序遍历

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

​ (1) 访问森林中第一棵树的根结点。

​ (2) 先序遍历第一棵树中根结点的子树森林。

​ (3) 先序遍历除去第一棵树之后剩余的树构成的森林。

森林的中序遍历 == 依次对各个子树进行后序遍历

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

​ （1） 中序遍历森林中第一棵树的根结点的子树森林。

​ （2） 访问第一棵树的根结点。

​ （3）中序遍历除去第一棵树之后剩余的树构成的森林

5.5 树与二叉树的应用

5.5.1 哈夫曼树和哈夫曼编码

结点的权：有某种现实含义的数值（如：表示结点的重要性等）

结点的带权路径长度：从树的根到该结点的路径长度（经过的边数）与该结点上权值的乘积

树的带权路径长度：树中所有叶结点的带权路径长度之和

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

哈夫曼树的构造

给定 n 个权值分别为 w 1, w 2,…, wn 的结点，构造哈夫曼树的算法描述如下：

​ （1）将这 n 个结点分别作为 n 棵仅含一个结点的二叉树，构成森林 F。

​ （2）构造一个新结点，从 F 中选取两棵根结点权值最小的树作为新结点的左、右子树，并且将新结点的权值置为左、右子树上根结点的权值之和。

​ （3）从 F 中删除刚才选出的两棵树，同时将新得到的树加入 F 中。

​ （4）重复步骤 2）和 3），直至 F 中只剩下一棵树为止。

特点

1. 每个初始结点最终都成为叶结点，且权值越小的结点到根结点的路径长度越大 
2. 哈夫曼树的==结点总数为2n − 1== 
3. 哈夫曼树中不存在度为1的结点。 
4. 哈夫曼树并==不唯一==，但==WPL必然相同且为最优==

哈夫曼编码

** 固定长度编码:** 每个字符用相等长度的二进制位表示

可变长度编码：允许对不同字符用不等长的二进制位表示

前缀编码 : 没有一个编码是另一个编码的前缀

构造哈夫曼编码：

​ （1）字符集中的每个字符作为一个叶子结点，各个字符出现的频度作为结点的权值，根据之前介绍的方法构造哈夫曼树

​ （2）从根结点到叶子结点的路径上标记序列, 0 转向左孩子, 1 转向右孩子

5.5.2 并查集