一、树的基本概念
1、树的定义
树是n（n≥0）个结点的有限集合，n = 0时，称为空树，这是一种特殊情况。在任意一棵非空树中应满足：
1）有且仅有一个特定的称为根的结点。
2）当n > 1时，其余结点可分为m（m > 0）个互不相交的有限集合T1, T2,…, Tm，其中每个集合本身又是一棵树，并且称为根结点的子树。
空树——结点数为0的树
非空树的特性：
- 有且仅有一个根节点
- 没有后继的结点称为“叶子结点”（或终端结点）
- 有后继的结点称为“分支结点”（或非终端结点）
- 除了根节点外，任何一个结点都有且仅有一个前驱
- 每个结点可以有0个或多个后继。
2、基本术语
结点的层次（深度）——从上往下数
结点的高度——从下往上数
树的高度（深度）——总共多少层
结点的度——有几个孩子（分支）
树的度——各结点的度的最大值
有序树——逻辑上看，树中结点的各子树从左至右是有次序的，不能互换
无序树——逻辑上看，树中结点的各子树从左至右是无次序的，可以互换
森林：森林是m（m≥0）棵互不相交的树的集合
考点：森林和树相互转化问题
3、树的性质
常见考点1：结点数=总度数+1
结点的度——结点有几个孩子（分支）
常见考点2：度为m的树、m叉树 的区别
常见考点3：度为m的树第 i 层至多有 m的i次方-1 个结点（i≥1）
m叉树第 i 层至多有 mi-1 个结点（i≥1）
常见考点4：高度为h的m叉树至多有多少个结点
常见考点5：高度为h的m叉树至少有 h 个结点。
高度为h、度为m的树至少有 h+m-1 个结点。
常见考点6：具有n个结点的m叉树的最小高度为 【logm(n(m - 1) + 1)】
小结考点
二、二叉树的概念
1、二叉树的定义及其主要特性
二叉树是n（n≥0）个结点的有限集合：
① 或者为空二叉树，即n = 0。
② 或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别是一棵二叉树。
特点：①每个结点至多只有两棵子树 ②左右子树不能颠倒（二叉树是有序树）
- 二叉树是递归定义的数据结构
二叉树的五种状态
满二叉树：一棵高度为h，且含有2h - 1个结点的二叉树
特点：
①只有最后一层有叶子结点
②不存在度为 1 的结点
③按层序从 1 开始编号，结点 i 的左孩子为 2i，右孩子为 2i+1；结点 i 的父节点为【i/2】（如果有的话）
完全二叉树：当且仅当其每个结点都与高度为h的满二叉树中编号为1～n的结点一一对应时，称为完全二叉树。
特点：
①只有最后两层可能有叶子结点
②最多只有一个度为1的结点
③按层序从 1 开始编号，结点 i 的左孩子为 2i，右孩子为 2i+1；结点 i 的父节点为【i/2】（如果有的话）
④ i≤ n/2 为分支结点， i> n/2 为叶子结点
完全二叉树：如果某结点只有一个孩子，那么一定是左孩子，若只有右孩子，而没有左孩子，那么，则不为完全二叉树。
二叉排序树。一棵二叉树或者是空二叉树，或者是具有如下性质的二叉树：
左子树上所有结点的关键字均小于根结点的关键字；
右子树上所有结点的关键字均大于根结点的关键字。
左子树和右子树又各是一棵二叉排序树。
左子树和右子树又各是一棵二叉排序树。
- 二叉排序树可用于元素的排序、搜索。
平衡二叉树：树上任一结点的左子树和右子树的深度之差不超过1。
小结
![]()
二叉树小结
二叉树的常考性质
常见考点1：设非空二叉树中度为0、1和2的结点个数分别为n0、n1和n2，则 n0 = n2 + 1
（叶子结点比二分支结点多一个）
假设树中结点总数为 n，则
① n = n0 + n1 + n2
② n = n1 + 2n2 +1（树的结点数=总度数+1 ）
② - ①：n0 = n2 + 1
常见考点2：二叉树第 i 层至多有 2的i-1次方个结点（i≥1）
m叉树第 i 层至多有 m的i-1次方个结点（i≥1）
常见考点3：高度为h的二叉树至多有 2的ℎ次方 − 1个结点（满二叉树）
完全二叉树的常考性质
常见考点1：具有n个（n > 0）结点的完全二叉树的高度h。
高为 h 的满二叉树共有 2的ℎ次方 − 1 个结点
高为 h-1 的满二叉树共有 2的h-1次方− 1个结点
常见考点2：对于完全二叉树，可以由的结点数 n 推出度为0、1和2的结点个数为n0、n1和n2
完全二叉树最多只有一个度为1的结点，即n1=0或1
n0 = n2 + 1→n0 + n2 一定是奇数
若完全二叉树有2k个（偶数）个结点，则必有 n1=1， n0 = k， n2 = k-1
若完全二叉树有2k-1个（奇数）个结点，则必有 n1=0， n0 = k， n2 = k-1
考点小结
二叉树：
• n0 = n2 + 1
• 第 i 层至多有 2i-1 个结点（i≥1）
• 高度为h的二叉树至多有 2ℎ − 1个结点
完全二叉树：
• 具有n个（n > 0）结点的完全二叉树的高度h为log2(n + 1)或log2n+ 1
• 对于完全二叉树，可以由的结点数 n 推出为0、1和2的结点个数为n0、n1
和n2（突破点：完全二叉树最多只会有一个度为1的结点）
2、二叉树的存储结构
二叉树的顺序储存
-
二叉树的顺序存储中，一定要把二叉树的结点编号与完全二叉树对应起来
节点编号对应
二叉树的链式储存
- n个结点的二叉链表共有 n+1 个空链域
三、二叉树的遍历和线索二叉树
1、二叉树的遍历
- 遍历：按照某种次序把所有结点都访问一遍
层次遍历：基于树的层次特性确定的次序规则
先/中/后序遍历：基于树的递归特性确定的次序规则
先序遍历：根左右（NLR）
先序遍历（PreOrder）的操作过程如下：
- 若二叉树为空，则什么也不做；
- 若二叉树非空：
①访问根结点；
②先序遍历左子树；
③先序遍历右子树。
中序遍历：左根右（LNR）
中序遍历（InOrder）的操作过程如下：
- 若二叉树为空，则什么也不做；
- 若二叉树非空：
①先序遍历左子树；
②访问根结点；
③先序遍历右子树。
后序遍历：左右根（LRN）
后序遍历（InOrder）的操作过程如下：
- 若二叉树为空，则什么也不做；
-
若二叉树非空：
①先序遍历左子树；
②先序遍历右子树；
③访问根结点。
先、中、后序遍历图示
结合算术表达式的遍历
考点小结
二叉树层次遍历
算法思想：
①初始化一个辅助队列
②根结点入队
③若队列非空，则队头结点出队，访问该结点，并将其左、右孩子插入队尾（如果有的话）
④重复③直至队列为空
2、线索二叉树
重要考点
四、树、森林
1、树的存储结构
树是n（n≥0）个结点的有限集合，n = 0时，称为空树，这是一种特殊情况。在任意一棵非
空树中应满足：
1）有且仅有一个特定的称为根的结点。
2）当n > 1时，其余结点可分为m（m > 0）个互不相交的有限集合T1, T2,…, Tm，其中每个集合本身又是一棵树，并且称为根结点的子树。
双亲表示法（顺序储存）
孩子表示法（顺序+链式存储）
孩子兄弟表示法（链式存储）
将树转化为二叉树，左孩子右兄弟
2、树、森林与二叉树的转换
将树转化为二叉树，左孩子右兄弟。
3、树和森林的遍历
树的先根遍历
先根遍历。若树非空，先访问根结点，再依次对每棵子树进行先根遍历。
*树的先根遍历序列与这棵树相应二叉树的先序序列相同。
树的后根遍历
后根遍历。若树非空，先依次对每棵子树进行后根遍历，最后再访问根结点。
*树的后根遍历序列与这棵树相应二叉树的中序序列相同。
树的层次遍历
层次遍历（用队列实现）
①若树非空，则根节点入队
②若队列非空，队头元素出队并访问，同时将该元素的孩子依次入队
③重复②直到队列为空
森林的先序遍历
先序遍历森林。
若森林为非空，则按如下规则进行遍历：
访问森林中第一棵树的根结点。
先序遍历第一棵树中根结点的子树森林。
先序遍历除去第一棵树之后剩余的树构成的森林。
- 效果等同于依次对二叉树的先序遍历
森林的中序遍历（ 实则个人所认为的后序遍历）
中序遍历森林。
若森林为非空，则按如下规则进行遍历：
中序遍历森林中第一棵树的根结点的子树森林。
访问第一棵树的根结点。
中序遍历除去第一棵树之后剩余的树构成的森林。
*效果等同于依次对二叉树的中序遍历
小结
![]()
小结
4、树的应用——并查集
五、树与二叉树的应用
1、二叉排序树（BST）
二叉排序树，又称二叉查找树（BST，Binary Search Tree）
一棵二叉树或者是空二叉树，或者是具有如下性质的二叉树：
左子树上所有结点的关键字均小于根结点的关键字；
右子树上所有结点的关键字均大于根结点的关键字。
左子树和右子树又各是一棵二叉排序树。
左子树结点值 < 根结点值 < 右子树结点值
进行中序遍历，可以得到一个递增的有序序列
2、平衡二叉树
平衡二叉树——树上任一结点的左子树和右子树的深度之差不超过1。
查找长度——在查找运算中，需要对比关键字的次数称为查找长度。
平衡二叉树的插入
每次调整的对象都是“最小不平衡子树”
在插入操作中，只要将最小不平衡子树调整平衡，则其他祖先结点都会恢复平衡
调整最小不平衡子树
1）LL平衡旋转（右单旋转）。
由于在结点A的左孩子（L）的左子树（L）上插入了新结点，A的平衡因子由1增至2，导致以A为根的子树失去平衡，需要一次向右的旋转操作。将A的左孩子B向右上旋转代替A成为根结点，将A结点向右下旋转成为B的右子树的根结点，而B的原右子树则作为A结点的左子树。
2）RR平衡旋转（左单旋转）。
由于在结点A的右孩子（R）的右子树（R）上插入了新结点，A的平衡因子由-1减至-2，导致以A为根的子树失去平衡，需要一次向左的旋转操作。将A的右孩子B向左上旋转代替A成为根结点，将A结点向左下旋转成为B的左子树的根结点，而B的原左子树则作为A结点的右子树
3）LR平衡旋转（先左后右双旋转）。
由于在A的左孩子（L）的右子树（R）上插入新结点，A的平衡因子由1增至2，导致以A为根的子树失去平衡，需要进行两次旋转操作，先左旋转后右旋转。先将A结点的左孩子B的右子树的根结点C向左上旋转提升到B结点的位置，然后再把该C结点向右上旋转提升到A结点的位置
4）RL平衡旋转（先右后左双旋转）。
由于在A的右孩子（R）的左子树（L）上插入新结点，A的平衡因子由-1减至-2，导致以A为根的子树失去平衡，需要进行两次旋转操作，先右旋转后左旋转。先将A结点的右孩子B的左子树的根结点C向右上旋转提升到B结点的位置，然后再把该C结点向左上旋转提升
到A结点的位置
小结
![]()
小结
3、哈夫曼树和哈夫曼编码
结点的权：有某种现实含义的数值（如：表示结点的重要性等）
结点的带权路径长度：从树的根到该结点的路径长度（经过的边数）与该结点上权值的乘积
树的带权路径长度：树中所有叶结点的带权路径长度之和（WPL, Weighted Path Length）
-
在含有n个带权叶结点的二叉树中，其中带权路径长度（WPL）最小的二叉树称为哈夫曼树，也称最优二叉树
哈夫曼树
哈夫曼树的构造
给定n个权值分别为w1, w2,…, wn的结点，构造哈夫曼树的算法描述如下：
1）将这n个结点分别作为n棵仅含一个结点的二叉树，构成森林F。
2）构造一个新结点，从F中选取两棵根结点权值最小的树作为新结点的左、右子树，并且将新
结点的权值置为左、右子树上根结点的权值之和。
3）从F中删除刚才选出的两棵树，同时将新得到的树加入F中。
4）重复步骤2）和3），直至F中只剩下一棵树为止。
1）每个初始结点最终都成为叶结点，且权值越小的结点到根结点的路径长度越大
2）哈夫曼树的结点总数为2n − 1
3）哈夫曼树中不存在度为1的结点。
4）哈夫曼树并不唯一，但WPL必然相同且为最优
哈夫曼编码
固定长度编码——每个字符用相等长度的二进制位表示
