一、树的概述
1.树的基本概念
N个结点组成一对多关系的层次结构。
N = 0 为空树，N = 1 只有根结点的树，N > 1 树。
A 逻辑定义（前驱后继）
有且仅有一个根结点，除根结点外，每一个节点有且仅有一个前驱结点，每个结点可以有0个或多个后继结点。
没后继结点称为“叶子结点”（终端结点），有后继结点的称为“分支结点”（非终端结点）。
结点数目为0的树称为空树。
B 递归定义
树是n(n>=0)个结点的有限集合，n=0时，称为空树。
在任意一棵非空树中满足：
a.有且仅有一个根结点
b.当n>1时，其余结点可分为m(m>0)个互不相交的有限集合T1,T2,...Tm，其中每个集合本身又是一棵树，称为根结点的子树。
C 度为m的树 与 m叉树（易错点）
度为m的树：至少有一个结点度为m，那么一定是非空树，至少有 m + 1个结点。
m叉树：每个结点最多只能有m个孩子的树，也可以没有。m叉树是有序树，孩子不能互换。
树的逻辑结构的应用
省份地点模型 家族关系模型 商品分类模型 文件目录模型
2.相关术语
A 结点之间的关系描述
祖先结点、子孙结点、双亲结点、孩子结点、兄弟结点、堂兄弟结点
两个结点间的路径：从上往下经过的边数。
树的路径长度：树中所有结点的边数总和，有带权路径长度。
B 结点、树的属性描述
结点的层次（深度），从上往下数，默认从1开始
结点的高度，从下往上数
树的高度（深度），总共多少层
结点的度：有几个孩子结点（分支），叶子结点度为0
树的度：各结点度的最大值
C 有序树和无序树
树中结点的各子树从左至右是有次序的，不能互换。
树中结点各子树从左至右是无次序的，可以互换。
具体看实际应用是否需要位置反映逻辑关系，如省份层次模型可以不需要，家族关系需要按年龄。
D 森林
森林是m棵互不相交的树的集合。m = 0 或 1 或大于 1
如全中国所有人家的家谱。
3.树的性质
A 结点与度数
除根结点外，每个结点都有一个父结点的度。结点数 = 总度数 + 1
设结点总数为N，则度为0的结点为N0，度为1的结点为N1，度为2的结点为N2，以此类推。
N = N0 + N1 + ...... + Nn
N = 1 + 0 *N0 + 1* N1 + 2*N2 + ...... + n * Nn
B 层次与结点分析（第i层的结点数）
度为m的树，第i层结点数目，最多时每个结点的孩子结点都为m，第i层为 m ^ (i - 1)
每个结点都只有1个结点，倒数第二层有m个孩子结点，有m个。
同样m叉树第i层最多有m ^ (i - 1)个结点。最少没有结点。
C 高度与结点分析
高度为h的m叉树，每个结点都有m个孩子结点，至多共有 m^0 + m^1 + ... + m^(h-1)。
高度为h的m叉树至少有h个结点。
高度为h，度为m的树至少有 h - 1 + m 个结点
具有n个结点的m叉树的最小高度为
4.树的存储结构
A 双亲表示法（顺序存储）
结点结构：关键字 + 指向双亲的位置下标。
存储结构：需要一块连续的空间存储结点。
优点：查指定结点的双亲很方便；缺点：查指定结点的孩子需要重新遍历。
B 孩子表示法（顺序+链式）
C 孩子兄弟表示法
二、二叉树的概述
1.二叉树的概念
每个结点最多只有两棵子树，可以有0个，1个（左右不一样），2个。
左右子树不能颠倒，二叉树是有序树。
二叉树的五种状态：空树，只有根节点，只有左子树，只有有子树，左右子树都有。
与度为2的的树是必须至少有一个结点的孩子为2。
2.几个特殊的二叉树
满二叉树：按序号层次编号，孩子结点的度都为2，没有度为1的结点，只有最后一层有叶子结点。
完全二叉树：每个结点都与的编号都与其对应的满二叉树编号相同。
二叉排序树：左子树上的关键字均小于根借点的关键字，右子树上所有结点的关键字均大于根结点的关键字。
平衡二叉树：树上任一结点的左右子树之差不超过1。-1 0 1
3.二叉树的性质
A 结点与度
非空二叉树度为0、1、2的结点个数分别为n0，n1，n2.
n = n0 + n1 + n2；n = 1 + 0*n0 + 1*n1 + 2*n2
n0 = n2 + 1;叶子结点比二分支结点多一个。
B 结点与层数
二叉树第i层至多有2^(i-1)个结点。
C 结点与高度
高度为h的二叉树至多有2^h - 1个结点。（满二叉树）
具有n个结点的完全二叉树的高度h为
D 完全二叉树的性质
完全儿叉树最有只有一个度为1的结点，即n1 = 0 或 1。
n0 = n2 + 1，n0 + n2 一定是奇数。
若n0 + n1 + n2 为偶数 2k个，则 n1 = 1，n0 = k , n2 = k -1。
若n0 + n1 + n2 为奇数 2k-1个，则 n1 = 0，n0 = k , n2 = k -1
4.二叉树的存储结构
A 顺序存储
按照完全二叉树的方式存储二叉树。
定义一个长度为MaxSize的数组t，按照从上至下、从左至右的顺序依次存储完全二叉树中的各个结点。
结点结构 TreeNode：结点中的数据元素；结点是否为空。
顺序存储下结点的分析
如果不是完全二叉树各结点顺序存储，一定要将二叉树的结点编号与完全二叉树对应起来。
最坏情况：高度为h且只有h个结点的单支树，也至少需要2^h -1 个存储单元。
因此，二叉树的顺序存储只适合存储完全二叉树。
B 链式存储
结点结构 BiTNode：数据元素 ElemType data; 左右孩子指针 struct BiTNode *lchild,*rchild
n个结点的二叉树结点，共有2n个指针域，有n-1个度占用，还剩n+1个空链域。可以用于构造线索二叉树。
可以很方便的找个指定结点的左右孩子结点。
要找父结点只能从根结点开始遍历。
可以增加一个父结点指针，组成三叉链表，方便寻找父结点。
5.二叉树的遍历
遍历：按照某种次序把所有结点都访问一遍。
层次遍历：基于树的层次特性确定的次序规则。
先中后序遍历：基于树的递归特性确定的次序序列。
先序（NLR）根左右，中序（LNR）左根右，后序（NRL）左右根。
遍历算术表达式
代码实现
|
层序遍历
不同二叉树的先中后层序列都可能对应多个二叉树形态。因此，只给出其中一种不能唯一确定。
6.树和二叉树的转换
树和森林
森林和二叉树的转换
7.树的遍历
三、树的应用
1.线索二叉树
A 线索二叉树的作用
二叉树的中序遍历序列：D G B E A F C
能否从一个指定结点开始继续中序遍历？
如何找到指定结点在中序遍历序列中的前驱和后继？从根结点出发往下访问。
这样操作很不方便，遍历操作必须从根结点开始出发。
n个结点的二叉树有n+1个空链域，可用来记录前驱、后继的信息。
指向前驱或后继的指针称为线索，用左孩子指针充当前驱线索，右孩子指针充当后继线索。
B 线索二叉树的存储结构
C 三种线索二叉树
2.二叉树线索化
A 中序线索化
B 先序线索化
C 后序线索化
3.在线索二叉树中找前驱和后继
A 中序线索二叉树
B 先序线索二叉树
C 后序线索二叉树
2.二叉排序树（BST，Binary Search Tree）
A 定义
左子树上的结点值 < 根结点的值 < 右子树上结点值。
左子树和右子树又各是一个二叉排序树。
进行中序遍历可得到一个递增的有序序列。
B 查找
若树为非空，目标值与根结点值进行比较，相等查找成功，小于根结点在左子树查找，否则在右子树查找。查找成功返回结点指针，查找失败返回null。
循环实现最坏空间复杂度为O(1)，递归实现最坏空间复杂度为O(h)。
C 插入
若原二叉树为空，则直接插入结点；否则，若关键字小于根结点的值，则插入左子树；否则插入右子树。
如按照序列{50,66,60,26,21,30,76,68}构造二叉排序树。
不同的序列可能得到相同或者不同的二叉排序树。
D 删除
先搜索找到目标结点，
若被删除的结点z是叶子结点，则直接删除，不会破坏二叉树的性质。
若被删除的结点z只有一棵左子树或右子树，则让z的子树成为z父结点的子树，替代z的位置。
若被删除的结点z有左右两棵子树，让z的直接前驱或后继替代z（这里的直接前驱和后继指遍历后的前驱后继），删除直接前驱或后继，变成判断直接前驱或后继的左右子树情况。。
E 查找效率分析
查找长度，在查找运算中，需要对比关键字的次数称为查找长度，反映查找操作时间复杂度。
若树高为h，找到最下层的一个结点需要对比h次。
最好情况，n个结点的二叉树最小高度为 logn + 1 , 平均查找长度为 log
最坏情况，每个结点只有一个分支，树高h = 结点树n。平均查找长度 = O(n)
查找成功的平均查找长度ASL
第一层 1次 第二层 2次 第h层 h次
[ 1 * (第1层结点数) + 2 * (第2层结点数) + ... + h * (第h层结点数) ] / n
查找失败的平均查找长度ASL
3.平衡二叉树（AVL树）
A 概述
对n个序列的顺序查找，时间复杂度为O(n)，将n个序列进行分层构造成树，可以优化查找速度，时间复杂度为树的高度O(h)。
构造一棵平衡二叉树可使得树的高度最小，即左右子树的高度之差不超过1。
结点的平衡因子 = 左子树高 - 右子树高 -1 0 1
B 平衡二叉树的插入
在二叉排序树中插入新的结点后，如何保持平衡?
插入一个结点后可能会使查找路径上的所有结点都有可能受到影响。从插入点往回找到第一个不平衡结点，调整以该结点为根的子树。每次调整的对象都是“最小不平衡子树”。只要将最小不平衡子树调整平衡，则其他祖先结点都会恢复平衡。
C 调整最小不平衡子树A（重点）
LL：在A的左孩子的左子树插入导致不平衡
RR：在A的右孩子的右子树插入导致不平衡
LR：在A的左孩子的右子树中插入导致不平衡
RL：在A的右孩子的左子树中插入导致不平衡
D 查找效率分析
若树高为h，则最坏情况下，查找一个关键字最多需要对比h次，即查找操作的时间复杂度不可能超过O(h)。
平衡二叉树--树上任一结点的左子树和右子树的高度之差不超过1。
假设以Nh表示深度为h的平衡树中含有的最少结点数。n0 = 0，n1 = 1，n2 = 2
并且有 nh = n h-1 + n h-2 + 1
可以证明含有n个结点的平衡二叉树的最大深度为O(log)，平衡二叉树的平均查找长度为O(log)
4.哈弗曼树
A 概述
结点的权：结点关键字表示的数值。
结点的带权路径长度：从树的根到该结点的路径长度（经过的边数）与该结点上权值的乘积。
树的带权路径长度：树中所有结点的带权路径长度之和。WPL
在含有n个带权叶结点的二叉树中，其中带权路径长度（WPL）最小的二叉树称为哈夫曼树，也成最优二叉树。
B 构造
C 哈夫曼编码
固定长度编码：对每个字符用相等长度的二进制位表示。如A--00 B--01 C--10 D--11
对80个C，10个选A，8个B，2个D，总的二进制长度为 100 * 2 = 200 bit
可变长度编码：允许对不同字符用不等长的二进制位表示。根据出现频率大小构造哈弗曼树，得如C--0 A--10 B--111 D--110
前缀编码：一组编码内，没有一个编码是另一个编码的前缀，则称前缀编码。
在连续编码串内才能识别出对应的编码。
哈夫曼树可用于数据压缩。
