树的基本概念
树的定义
- 树是n(
)个结点的有限集 - n=0为空树
- 有且只有一个称为根的结点
- n>1时，其余结点可分为m(
)个互不相交的有限集 ，每个集合也是树，称为根的子树。
树的特点
- 根没有前驱，其他点有且只有一个前驱
- 所有点都可以有零或任意多个后继
- n个点的树有n-1条边（数学归纳法易证）
基本术语
- 祖先：根到结点a唯一路径上任意结点都是a的祖先
- 子孙：结点是其祖先的子孙
- 双亲：根到结点a唯一路径是最接近a的结点是a的双亲
- 孩子：结点是其双亲的孩子
- 兄弟：双亲相同的结点互为兄弟
- 树结点的度：孩子的个数（和图中度有区别）
- 树的度：树结点度的最大值
- 分支节点（非终端结点）：度大于零的点
- 叶子结点（终端结点）：度等于零的点
- 结点的层次：从根开始为第1层，逐层增加
- 堂兄弟：双亲在同一层
- 结点的深度：从根结点向下逐层累加
- 结点的高度：从叶结点向上逐层累加
- 树的高度（深度）：树中结点最大层数
- 有序树和无序树：有序树的结点从左到右是有次序的树，互换后变成不同的树。
- 路径和路径长度：两个结点的路径是由两个结点所经过结点序列构成的，路径长度是路径上边的个数（一般来说认为分支有向，路径只能是从上往下的）
- 树的路径长度:树根到每个结点路径长的总和
- 森林：m个（
）互不相交的树的集合
树的性质
- 结点数等于所有结点的度数和加1（即边数加1）
- 度为
的树的第 层最多有 个节点，( ) - 高度为
的 叉树最多有( )个结点 - 具有n个结点的m叉树的最小高度是
二叉树
二叉树的定义
- 或者为空树，n=0
- 或者由根结点和两个互不相交的左右子树组成，左右子树都是二叉树
- 注意，二叉树是有序树，左右子树顺序不能随意交换
- 与度为2的有序树的区别
- 二叉树可以为空
- 即使只有一个孩子，二叉树也要区分左右子树，而有序树这种情况不需要区分顺序
几个特殊的二叉树
- 满二叉树：每层含有做多的结点
- 完全二叉树：编号与满二叉树完全对应（约定编号从1开始）
- 重要特征：度为1的结点必然是只有左孩子
- 其他特征：只有左孩子的结点编号后的结点都是叶子结点
- 二叉排序树：左子树关键字小于根关键字小于右子树关键字，左右子树也是二叉排序树
- 平衡二叉树：树上任一结点左右子树深度差不超过1
二叉树的性质
- 非空二叉树上的叶子结点数等于度为2的结点数加1
- 非空二叉树第k层至多有
个结点 - 高度为h的二叉树最多有
个结点 - 具有n个(
)结点的完全二叉树的高度为 ，(原理是 )
二叉树的存储结构
- 顺序存储
- 利用数组，数组下标为i的位置存储编号为i+1的结点
- 适合满二叉树或完全二叉树
- 对于一般的二叉树需要添加树中并不存在的空结点，以反映二叉树结点的逻辑关系
- 链式存储
- 解决了顺序存储中空间利用率低的问题
- 每个结点除了数据域，还有左右子树的指针域
- n个结点的二叉链表中，有n-1个非空链域，2n个链域，n+1个空链域
- 后面提到的线索链表中将利用这些空链域
树转换为二叉树
- 结点的孩子放到左子树
- 结点的兄弟放到右子树
二叉树遍历和线索化二叉树
二叉树的遍历
- 遍历：对二叉树的结点按某种顺序排队
- 先序遍历：先访问根，再访问左子树，再访问右子树，递归遍历
- 中序遍历：先访问左子树，再访问根，再访问右子树，递归遍历
- 后序遍历：先访问左子树，再访问右子树，再访问根，递归遍历
二叉树遍历的非递归算法（栈实现）
- 中序遍历
- (1)：沿着根的左孩子，依次入栈，直到左孩子为空
- (2)：栈顶元素出栈并访问，若该元素有右孩子，将右子树转(1)进行；否则继续执行(2)
- 先序遍历
- (1)：访问根，沿着根的左孩子，依次访问再入栈，直到左孩子为空
- (2)：栈顶元素出栈，若该元素有右孩子，将右子树转(1)进行；否则继续执行(2)
- 后序遍历（较复杂的一种情况）
- (1)：沿着根的左孩子，依次入栈，直到左孩子为空
- (2)：读栈顶元素，若该元素有未访问过的右孩子，将右子树转(1)进行；否则栈顶元素出栈并访问，再继续(2)
- 麻烦的地方是(2)中需要判断是从左子树返回的还是从右子树返回的，可以在结点中加一个标记，记录有无访问过。
层次遍历
- 根进队列
- 当队列不空，弹出结点，访问结点，结点如果有子结点，则从左到右依次进队列
- 返回(2)继续判断
由遍历序列构造二叉树
- 先序序列和中序序列
- 先序序列第一个为根节点
- 该点把中序序列分成左子树中序序列和右子树中序序列两部分
- 根据两部分长度可以把先序序列分成左子树先序序列和右子树先序序列两部分
- 递归构造左右子树即可
- 后序序列和中序序列
- 后序序列最后一个为根节点
- 该点把中序序列分成左子树中序序列和右子树中序序列两部分
- 根据两部分长度可以把后序序列分成左子树后序序列和右子树后序序列两部分
- 递归构造左右子树即可
- 层序序列和中序序列
- 层序序列第一个为根节点
- 该点把中序序列分成左子树中序序列和右子树中序序列两部分
- 两层遍历，把层序序列剩余点分成左子树层序序列和右子树层序序列（看层序序列点在中序序列左子树部分还是右子树部分）
- 递归构造左右子树即可
- 先序序列和后序序列：二叉树不唯一
- 但是如果先序序列有XY，后序序列有YX，说明X是Y的祖先
线索化二叉树
基本概念
- 利用二叉树n+1个空指针域存放遍历的前驱后继信息，即构造出线索化二叉树
- 线索化二叉树加快了查找结点前驱和后继的速度
- 如果没有左孩子，则左指针域存放结点前驱位置
- 如果没有右孩子，则右指针域存放结点后继位置
- 还要在结点中增加两个布尔标记变量，记录左右指针域存放的是孩子的位置还是前驱后继的位置
- 这样的结点构成的链表叫做线索链表
- 这样的结点构成的二叉树叫做线索二叉树
- 如果指针域指向了前驱和后继，该指针称为线索
中序线索二叉树
- 构造
- 本质就是中序遍历一次
- 附设pre和p两个指针，指向上一个和当前访问的结点
- p的左指针为空则指向pre
- pre的右指针为空则指向p
- 遍历
- FirstNode函数：第一个节点为最左下方的结点（不一定是叶子），不断访问左孩子即可（如果有左孩子）
- NextNode函数：访问当前结点后
- 如果其右指针不是右孩子，则右指针为后继
- 如果其右指针是右孩子，则后继为右子树的最左下方的结点，需要调用FirstNode函数
- LastNode函数：最后一个节点最右下方的结点（不一定是叶子），不断访问右孩子即可（如果有右孩子）
- PreviousNode函数：访问当前结点后
- 如果其左指针不是左孩子，则左指针为前驱
- 如果其左指针是左孩子，则前驱为左子树的最右下方的结点，需要调用LastNode函数
先序后序线索二叉树
- 构造
- 本质还是先按先序或后序遍历一次
- 附设pre和p两个指针，指向上一个和当前访问的结点
- p的左指针为空则指向pre
- pre的右指针为空则指向p
- 遍历
- 先序线索树找后继
- 如果有左孩子，左孩子为后继
- 如果没左孩子有右孩子，右孩子为后继
- 如果没孩子，右指针为后继
- 后序线索树找后继
- 如果为根，则无后继
- 如果是双亲的右孩子，则后继为双亲
- 如果是双亲的左孩子，且双亲没右孩子，则后继为双亲
- 如果是双亲的左孩子，且双亲有右孩子，则后继为双亲右子树后序遍历第一个结点
- 可以看出后序线索树找后继还需要知道双亲结点，因此要采用带双亲标志域的三叉链表
- 先序线索树找前驱
- 如果为根，则无前驱
- 如果是双亲的左孩子，则前驱为双亲
- 如果是双亲的右孩子，且双亲没左孩子，则后继为双亲
- 如果是双亲的右孩子，且双亲有左孩子，则前驱为双亲左子树先序遍历最后一个结点
- 可以看出先序线索树找前驱还需要知道双亲结点，因此要采用带双亲标志域的三叉链表
- 后序线索树找前驱
- 如果有右孩子，右孩子为前驱
- 如果没右孩子有左孩子，左孩子为前驱
- 如果没孩子，左指针为前驱
- 先序线索树找后继
树和森林
树的存储结构
双亲表示法
- 利用结点双亲的唯一性
- 采用连续顺序存储
- 记录双亲在数组的位置
- 类似于静态链表
孩子表示法
- 数据元素为链表的数组
- 每个结点的孩子都用一条链串成线性的结构
- 类似于邻接表的结构
二叉树表示法（孩子兄弟表示法）
该数据结构很适合实现前面二叉树部分的笔记提到的树转换成二叉树。其中二叉树的每个结点包含： + 结点值 + 第一个孩子的指针 + 第一个兄弟的指针
该结构的缺点是找双亲开销比较大
树、森林和二叉树的转换
树到二叉树
- 每个结点的左指针指向最左边的孩子
- 每个结点的右指针指向右边第一个兄弟
- 根没有兄弟，因此根在二叉树上没有右孩子
森林到二叉树
- 将森林的每个树转换为二叉树
- 森林的树之间看作兄弟，即二叉树之间用根的右指针链接
二叉树到森林
- 二叉树的根和其左子树为第一颗树
- 二叉树的根的右子树为森林剩下部分，递归拆分树
- 把拆分后的每个二叉树还原为树
树和森林的遍历
树的遍历
- 类似于二叉树的遍历
- 树的先根遍历：先访问根，再依次先根遍历子树，即普通树的二叉树表示的先序遍历
- 树的后根遍历：先依次后根遍历子树，再访问根，即普通树的二叉树表示的中序遍历
- 树的层次遍历：类似于二叉树层次遍历，用到队列
- 普通树一般不考虑中序遍历
森林的遍历
- 先序遍历森林
- 先访问第一棵树的根结点
- 再先序访问第一颗树去掉根的子树森林
- 最后先序访问森林剩余部分
- 即森林的二叉树表示的先序遍历
- 中序遍历森林
- 先按照中序遍历访问第一颗树去掉根的子树森林
- 再访问第一棵树的根结点
- 最后中序遍历访问森林剩余部分
- 即森林的二叉树表示的中序遍历
- 有时也把中序遍历森林称为后续遍历森林，不同教材称呼不同
树的应用之并查集
假设全集合为S，里面有若干元素。并查集支持三个操作：
- 初始化集合S的每个元素自成一个单元素子集合（构成了一个划分）
- 将两个互不相交的子集合合并
- 查询S中的元素x所在的子集合
并查集结构
- 通常是根树，结点包含双亲的位置
- 存储一般是顺序存储，根结点的双亲位置标记为-1
并查集优化
- 加权“并”：每次合并时将结点数少的集合挂到结点数多的集合的根上
- 路径压缩“查”：每次查完一个结点，把该结点到根上所有的结点都直接挂到根结点上
并查集性能
- 假定并查集包含
个元素，同时指向长度为 的并和查指令序列 - 普通并、普通查，复杂度
- 加权并、普通查，复杂度
- 加权并、路径压缩查，复杂度
，其中 的定义基于超指数函数，增长非常慢，可以近似认为，复杂度是
二叉树的应用
二叉排序树(BST)
- 定义
- 左子树非空，则左子树值小于根值
- 右子树非空，则右子树值大于根值
- 左右子树都是BST
- 查找
- 如果根值和目标值相等则找到
- 如果目标值较小则进入左子树继续找
- 如果目标值较大则进入右子树继续找
- 插入
- 如果二叉排序树为空，则直接插入
- 否则如果关键字较小，则插入左子树
- 如果关键字较大，则插入右子树
- 插入时一定是作为叶子结点
- 构造：从空树开始依次插入结点即可
- 删除
- 如果是叶子结点可以直接删除
- 如果删除结点只有左子树或只有右子树，则让该子树直接成为删除结点的子树
- 如果删除结点有左右子树，则用删除结点的直接前驱或直接后继代替删除结点，该前驱和后继原先一定是叶子结点，代替后删除该叶子结点。
- 查找效率
- 平衡二叉排序树，平均查找长度是O(log n)
- 普通二叉排序树，最坏情况查找长度O(n)
- 和二分查找类似，但二分查找表是静态的，判定唯一，二叉排序树根据元素插入顺序不同，不唯一
- 在插入删除时，为了维护表的有序性，二叉排序树平均开销O(log n)，二分查找的有序顺序表平均开销O(n)
平衡二叉树(AVL Tree)
- 定义
- 任意结点左右子树高度差不超过1的二叉树
- 该高度差叫做平衡因子（只能是-1，0，1）
- 插入
- 每插入一个结点，检查最小不平衡子树T，假设T的根为A
- 此时A是插入路径上平衡因子绝对值大于1的最接近插入点的结点（否则和最小平衡树矛盾）
- 设A,B,C是插入路径上从上到下的三个结点
- LL型：B是A左孩子，C是B左孩子，进行右单旋转，用B代替A，A是B的右孩子，B原右孩子变成A左孩子
- RR型：B是A右孩子，C是B右孩子，进行左单旋转，用B代替A，A是B的左孩子，B原左孩子变成A右孩子
- LR型：B是A左孩子，C是B右孩子，先左单旋转，用C代替B，B是C的左孩子，C的原左孩子变成B的右孩子；再右单旋转，用C代替A，A是C的右孩子，C的原右孩子变成A的左孩子
- RL型：B是A右孩子，C是B左孩子，先右单旋转，用C代替B，B是C的右孩子，C的原右孩子变成B的左孩子；再左单旋转，用C代替A，A是C的左孩子，C的原左孩子变成A的右孩子
- 删除
- 按普通二叉排序树删除
- 从删除点向根找第一个不平衡点，对于该点和该点较高子树路径上的三个点，执行类似的LL、RR、LR、RL旋转
- 如果由于旋转操作造成不平衡点上面有新的不平衡点，则继续的向根调整
- 查找
- 过程和普通二叉树查找相同
- 假设
表示深度为h的平衡树最少需要的结点数,显然 ，该结论可以解决问题：给定结点数求平衡树的最大深度问题 - 可以证明平衡二叉树最大深度是
哈夫曼树和哈夫曼编码
- 哈夫曼树定义
- 树的带权路径长度定义为
，其中 为第i个叶结点的权值， 为根结点到第i个叶结点的路径长度 - 哈夫曼树是带权路径长度最小的树，最优二叉树
- 树的带权路径长度定义为
- 哈夫曼树构造
- 将n个结点分别作为单结点二叉树，构造森林F
- 取F中最小两个权值的树，作为左右子树，构造一个新结点，权值为左右子树权值和
- 用新树代替刚刚的两棵树加入F中
- 重复前两步骤直至F中只有一棵树
- 哈夫曼树特点
- 所有初始结点最后都成为叶结点，权值小的结点到根的路径长度更大
- 构造过程新建了n-1个结点，哈夫曼树总结点数为2n-1
- 哈夫曼树不存在度为1的结点
- 哈夫曼编码
- 如果对字符用等长的二进制位表示，则是固定长度编码
- 如果对不同字符用不同长度的二进制表示，则是可变长度编码，好处是可以给高频词短的编码，给低频词长的编码，从而缩短平均编码长度，实现数据压缩
- 如果没有一个编码是一个编码的前缀，则这样的编码叫做前缀码，前缀码的优点是解码简单，识别出第一个编码就可以翻译为原码
- 很容易从哈夫曼树构造出哈夫曼编码，字符作为独立结点参与哈夫曼树构造，成为叶结点。字符的编码就是从根到该字符的路径边标记序列（如向左孩子标记为0，向右孩子标记为1）
- 哈夫曼树的带权路径长度就是哈夫曼编码的平均二进制编码长度
- 哈夫曼树不一定唯一，编码也不一定唯一，但WPL一定是相同且最优的
- 推广的哈夫曼树
- 如果是多叉树（n叉树），需要保证每个结点的孩子数都是n，做法是补若干权值为0的结点
