树的定义和基本术语

空树：

结点数为0的树

非空树的特性：

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

树的定义：

• 树是n（n≥0）个结点的有限集合，n = 0时，称为空树，这是一种特殊情况。
• 在任意一棵非空树中应满足：
  • 有且仅有一个特定的称为根的结点。
  • 当n > 1时，其余结点可分为m（m > 0）个互不相交的有限集合T1, T2,…, Tm，其中每个集合本身又是一棵树，并且称为根结点的子树。

结点之间的关系描述：

• 什么是祖先结点？比自己深度低的结点
• 什么是子孙结点？比自己深度高的结点
• 什么是双亲结点（父结点）？自己的根结点
• 什么是孩子结点？自己作为根结点的儿子
• 什么是兄弟结点？与自己拥有相同父结点结点
• 什么是堂兄弟结点？与自己同一层的结点
• 什么是两个结点之间的路径？能从上往下前往的两个结点被称为有路径
• 什么是路径长度？经过几条边

结点、树的属性描述：

• 结点的层次（深度）：从上往下数，默认从1开始
• 结点的高度：从下往上数
• 树的高度（深度）：总共多少层
• 结点的度：有几个孩子（分支）
• 树的度：各结点的度的最大值

有序数和无序树：

• 有序树：逻辑上看，树中结点的各子树从左至右是有次序的，不能互换
• 无序树：逻辑上看，树中结点的各子树从左至右是无次序的，可以互换
• 是否是什么，具体看你用树存什么，是否需要用结点的左右位置反映某些逻辑关系

树和森林：

• 森林是m（m≥0）棵互不相交的树的集合
• 考点：树和森林的相互转换

树的性质

• 树的总结点数=树的总度数+1
• 度数为m的树和m叉树的区别
  
• 度为m的树第i 层至多有m^i-1 个结点（i≥1）
• m叉树第i 层至多有m^i-1 个结点（i≥1）
• 高度为h的m叉树至多有((m^h)-1)/m-1个结点
• 高度为h的m叉树至少有h 个结点
• 高度为h、度为m的树至少有h+m-1 个结点
• 具有n个结点的m叉树的最小高度为logm(n(m - 1) + 1)
• 高度最小的情况：所有结点都有m个孩子

二叉树的定义和基本术语

定义：

• 二叉树是n（n≥0）个结点的有限集合
  • 或者为空二叉树，即n = 0。
  • 或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别是一棵二叉树。
• 特点：
  • 每个结点至多只有两棵子树
  • 左右子树不能颠倒（二叉树是有序树）

二叉树的五种状态：

• 空二叉树
• 只有左子树
• 只有右子树
• 只有根结点
• 左右子树都有

几个特殊的二叉树：

• 满二叉树：一棵高度为h，且含有2^h - 1个结点的二叉树
  • 特点：
    • 只有最后一层有叶子结点
    • 不存在度为1 的结点
    • 按层序从1 开始编号，结点i 的左孩子为2i，右孩子为2i+1；结点i 的父结点为𝑖/2 （如果有的话）
• 完全二叉树：当且仅当其每个结点都与高度为h的满二叉树中编号为1～n的结点一一对应时，称为完全二叉树
  • 特点：
    • 只有最后两层可能有叶子结点
    • 最多只有一个度为1的结点
    • 按层序从1 开始编号，结点i 的左孩子为2i，右孩子为2i+1；结点i 的父结点为𝑖/2 （如果有的话）
    • i≤ n/2 为分支结点， i> n/2 为叶子结点
    • 如果某结点只有一个孩子，那么一定是左孩子
• 是满二叉树一定是完全二叉树，是完全二叉树不一定是满二叉树
• 二叉排序树：一棵二叉树或者是空二叉树，或者是具有如下性质的二叉树：
  • 左子树上所有结点的关键字均小于根结点的关键字
  • 右子树上所有结点的关键字均大于根结点的关键字
  • 左子树和右子树又各是一棵二叉排序树
• 二叉排序树可用于元素的排序、搜索
• 平衡二叉树：树上任一结点的左子树和右子树的深度之差不超过1。
  • 平衡二叉树能有更高的搜索效率
  • 又宽又胖的树

各种二叉树的性质

二叉树的性质：

• 设非空二叉树中度为0、1和2的结点个数分别为n0、n1和n2，则n0 = n2 + 1（叶子结点比二分支结点多一个）
• 二叉树第i 层至多有2^(i-1)个结点（i≥1）
• 高度为h的2叉树至多有(2^h)-1个结点（满二叉树）

完全二叉树的性质：

• 具有n个（n>0）结点的完全二叉树的高度h为log2(n + 1) 或[log2n] + 1
• 对于完全二叉树，可以由的结点数n 推出度为0、1和2的结点个数为n0、n1和n2（突破点：完全二叉树最多只会有一个度为1的结点）

二叉树的储存结构

顺序存储：

常用的基本操作：

• i的左孩子：2i
• i的右孩子：2i+1
• i的父结点：⌊i/2⌋
• i所在的层次：⌈log2(n+1)⌉或者⌊log2n⌋+1

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

• 判断i是否有左孩子：2i ≤ n ?
• 判断i是否有右孩子：2i+1 ≤ n ?
• 判断i是否是叶子/分支结点：i > ⌊n/2⌋ ?

储存非完全二叉树：

二叉树的链式存储：

定义和初始化：

• 这样的方法可以很简单的找到p结点的左右孩子，但是只能通过从根开始遍历查找找到结点p的父结点
• 可以通过多定一个父结点的指针来方便的查找父结点（三叉链表）

• n个结点的二叉链表共有n+1 个空链域（可以用来构建线索二叉树）

二叉树的先中后序遍历

遍历：

• 遍历：按照某种次序把所有结点都访问一遍
• 层序遍历：基于树的层次特性确定的次序规则
• 先/中/后序遍历：基于树的递归特性确定的次序规则

二叉树的遍历：

• 二叉树的递归特性：
  • 要么是个空二叉树
  • 要么就是由“根结点+左子树+右子树”组成的二叉树
• 先序遍历：根左右（NLR）
• 中序遍历：左根右（LNR）
• 后序遍历：左右根（LRN）

先序遍历（代码）：

中序遍历（代码）：

后序遍历（代码）：

二叉树遍历总结：

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

求树的深度：

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

二叉树的层序遍历

层序遍历：

基于树的层次特性确定的次序规则

算法思想：

• 初始化一个辅助队列
• 根结点入队
• 若队列非空，则队头结点出队，访问该结点，并将其左、右孩子插入队尾（如果有的话）
• 重复第三步直至队列为空

代码实现：

由遍历序列构造二叉树

结论：

• 一个前/中/后/层序遍历序列可能对应多种二叉树形态
• 只有至少同时拥有两种遍历序列才能确定二叉树的形态
• 结论：前序、后序、层序序列的两两组合无法唯一确定一科二叉树

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

前序+中序：

中序+后序：

层序+中序：

线索二叉树的概念

中序遍历的问题：

• 如何找到指定结点p在q 中序遍历序列中的前驱？
• 如何找到p的中序后继？
• 能否从一个指定结点开始中序遍历？
• 完成上述需求的思路：
  • 从根结点出发，重新进行一次中序遍历，指针q记录当前访问的结点，指针pre记录上一个被访问的结点
  • 当q == p时，pre为前驱
  • 当pre == p时，q为后继
• 缺点：找前驱、后继很不方便； 操作必须从根开始

中序线索二叉树：

线索二叉树的存储结构：

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

三种线索二叉树的对比：

二叉树的线索化

通过头结点找到中序前驱：

中序二叉树线索化：

先序二叉树线索化：

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

后序二叉树线索化：

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

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

• 在中序线索二叉树中找到指定结点*p的中序后继next
  • 若p->rtag == 1，则next = p->rchild
  • 若p->rtag == 0，说明p必定有右孩子，next = （p的右子树中最左下的结点）

• 在中序线索二叉树中找到指定结点*p的中序前驱pre
  • 若p->ltag == 1，则pre = p->lchild
  • 若p->ltag == 0，说明p必定有左孩子，pre = （p的左子树中最右下的结点）

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

• 在先序线索二叉树中找到指定结点*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：可以改用三叉链表以找到父结点

  

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

• 在后序线索二叉树中找到指定结点*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：可以改用三叉链表以找到父结点

树的储存结构

双亲表示法（顺序存储）：

• 每个结点中保存指向双亲的“指针”，data，parrent
• 根结点固定存储在0，-1表示没有双亲

• 新增数据元素，无需按逻辑上的次序存储，只需说明新增元素的data，parrent即可
• 删除数据元素
  • 方案1：把要删除的数据元素data设为空，parent设为-1
  • 方案2：将数组尾部的数据元素覆盖要删除的数据元素
• 查询数据元素
  • 优点：查指定结点的双亲很方便
  • 缺点：查指定结点的孩子只能从头遍历

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

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

规则：

• 左指针指向第一个孩子
• 右指针指向自己的第一个兄弟

森林和二叉树的转换：

• 本质：用二叉链表存储森林
• 规则：
  • 各个树的根结点视为兄弟关系
  • 左指针指向第一个孩子
  • 右指针指向自己的第一个兄弟

树和森林的遍历

树的先根遍历：

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

树的后根遍历：

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

树的层次遍历：

• 用队列实现，又被称为广度优先遍历
• 步骤
  • 若树非空，则根结点入队
  • 若队列非空，队头元素出队并访问，同时将该元素的孩子依次入队
  • 重复第二步直到队列为空

森林的先序遍历：

• 若森林为非空，则按如下规则进行遍历：
  • 访问森林中第一棵树的根结点。
  • 先序遍历第一棵树中根结点的子树森林。
  • 先序遍历除去第一棵树之后剩余的树构成的森林。
• 效果等同于依次对各个树进行先根遍历
• 用孩子兄弟表示法转换为二叉树，效果等同于依次对二叉树的先序遍历

森林的中序遍历：

• 若森林为非空，则按如下规则进行遍历：
  • 中序遍历森林中第一棵树的根结点的子树森林。
  • 访问第一棵树的根结点。
  • 中序遍历除去第一棵树之后剩余的树构成的森林。
• 效果等同于依次对各个树进行后根遍历
• 用孩子兄弟表示法转换为二叉树，效果等同于依次对二叉树的中序遍历

二叉排序树（BST）

定义：

• 二叉排序树，又称二叉查找树（BST，Binary Search Tree）
• 一棵二叉树或者是空二叉树，或者是具有如下性质的二叉树：
  • 左子树上所有结点的关键字均小于根结点的关键字
  • 右子树上所有结点的关键字均大于根结点的关键字
  • 左子树和右子树又各是一棵二叉排序树
• 即左子树结点值< 根结点值< 右子树结点值
• 进行中序遍历，可以得到一个递增的有序序列
• 二叉排序树可用于元素的有序组织、搜索

BST的查找：

• 若树非空，目标值与根结点的值比较：
  • 若相等，则查找成功
  • 若小于根结点，则在左子树上查找，否则在右子树上查找。
  • 查找成功，返回结点指针；
  • 查找失败返回NULL
• 递归实现的最坏空间复杂度为O(h),普通实现的最坏空间复杂度为O(1)

BST的插入：

• 若原二叉排序树为空，则直接插入结点；
• 否则，若关键字k小于根结点值，则插入到左子树，若关键字k大于根结点值，则插入到右子树
• 递归实现的最坏空间复杂度为O(h)

二叉排序树的构造：

注意：不同的关键字序列可能得到同款二叉排序树，也可能得到不同款二叉排序树

二叉排序树的删除：

• 先搜索找到目标结点：
  • 若被删除结点z是叶结点，则直接删除，不会破坏二叉排序树的性质。
  • 若结点z只有一棵左子树或右子树，则让z的子树成为z父结点的子树，替代z的位置。
  • 若结点z有左、右两棵子树，则令z的直接后继（或直接前驱）替代z，然后从二叉排序树中删去这个直接后继（或直接前驱），这样就转换成了第一或第二种情况。
    • z的后继：z的右子树中最左下结点，是右子树最小的结点（该结点一定没有左子树）
    • z的前驱：z的左子树中最右下结点，是左子树中最大的结点（该结点一定没有右子树）

查找效率分析：

• 查找长度：在查找运算中，需要对比关键字的次数称为查找长度，反映了查找操作时间复杂度
• 查找成功的平均查找长度ASL（Average Search Length）：（各层（层数*层结点个数）相加）/总结点个数
• 最坏情况：每个结点只有一个分支，树高h=结点数n。平均查找长度=O(n)
• 最好情况：n个结点的二叉树最小高度为(log2n)+ 1。平均查找长度= O(log2n)

平衡二叉树（AVL）

定义：

• 平衡二叉树（Balanced Binary Tree），简称平衡树（AVL树）——树上任一结点的左子树和右子树的高度之差不超过1
• 结点的平衡因子=左子树高-右子树高
• 平衡二叉树结点的平衡因子的值只可能是−1、0或1
• 只要有任一结点的平衡因子绝对值大于1，就不是平衡二叉树

平衡二叉树的插入：

• 在二叉排序树中插入新结点后，如何保持平衡？
  • 查找路径上的所有结点都有可能受到影响
  • 从插入点往回找到第一个不平衡结点，调整以该结点为根的子树
  • 每次调整的对象都是“最小不平衡子树”
  • 在插入操作中，只要将最小不平衡子树调整平衡，则其他祖先结点都会恢复平衡
  • 插入操作导致“最小不平衡子树”高度+1，经过调整后高度恢复
• 调整最小不平衡子树

调整最小不平衡子树：

• 只有假设所有子树的高度都是H才能保证出现最小不平衡子树恒定
• 目标：
  • 恢复平衡
  • 保持二叉排序树特性
• 二叉排序树的特性：左子树结点值< 根结点值< 右子树结点值
• LL平衡旋转（右单旋转）
  • 由于在结点A的左孩子（L）的左子树（L）上插入了新结点，A的平衡因子由1增至2，导致以A为根的子树失去平衡，需要一次向右的旋转操作
  • 将A的左孩子B向右上旋转代替A成为根结点，将A结点向右下旋转成为B的右子树的根结点，而B的原右子树则作为A结点的左子树

• RR平衡旋转（左单旋转）
  • 由于在结点A的右孩子（R）的右子树（R）上插入了新结点，A的平衡因子由-1减至-2，导致以A为根的子树失去平衡，需要一次向左的旋转操作
  • 将A的右孩子B向左上旋转代替A成为根结点，将A结点向左下旋转成为B的左子树的根结点，而B的原左子树则作为A结点的右子树

• 右旋和左旋的代码实现思路

• LR平衡旋转（先左后右双旋转）
  • 由于在A的左孩子（L）的右子树（R）上插入新结点，A的平衡因子由1增至2，导致以A为根的子树失去平衡，需要进行两次旋转操作，先左旋转后右旋转
  • 先将A结点的左孩子B的右子树的根结点C向左上旋转提升到B结点的位置，然后再把该C结点向右上旋转提升到A结点的位置

• RL平衡旋转（先右后左双旋转）
  • 由于在A的右孩子（R）的左子树（L）上插入新结点，A的平衡因子由-1减至-2，导致以A为根的子树失去平衡，需要进行两次旋转操作，先右旋转后左旋转
  • 先将A结点的右孩子B的左子树的根结点C向右上旋转提升到B结点的位置，然后再把该C结点向左上旋转提升到A结点的位置

查找效率分析：

• 若树高为h，则最坏情况下，查找一个关键字最多需要对比h次，即查找操作的时间复杂度不可能超过O(h)
• 平衡二叉树——树上任一结点的左子树和右子树的高度之差不超过1
• 假设以nh表示深度为h的平衡树中含有的最少结点数。
• 则有n0 = 0, n1 = 1, n2 = 2，并且有nh = n(h−1) + n(h−2) + 1
• 可以证明含有n个结点的平衡二叉树的最大深度为O(log2n) ，平衡二叉树的平均查找长度为O(log2n)

哈夫曼树

带权路径长度：

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

哈夫曼树的定义：

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

哈夫曼树的构造：

• 给定n个权值分别为w1, w2,…, wn的结点，构造哈夫曼树的算法描述如下：
  • 将这n个结点分别作为n棵仅含一个结点的二叉树，构成森林F。
  • 构造一个新结点，从F中选取两棵根结点权值最小的树作为新结点的左、右子树，并且将新结点的权值置为左、右子树上根结点的权值之和。
  • 从F中删除刚才选出的两棵树，同时将新得到的树加入F中。
  • 重复步骤2和3，直至F中只剩下一棵树为止。
• 每个初始结点最终都成为叶结点，且权值越小的结点到根结点的路径长度越大
• 哈夫曼树的结点总数为2n − 1
• 哈夫曼树中不存在度为1的结点。
• 哈夫曼树并不唯一，但WPL必然相同且为最优

哈夫曼编码：

• 固定长度编码：每个字符用相等长度的二进制位表示
• 可变长度编码：允许对不同字符用不等长的二进制位表示
• 若没有一个编码是另一个编码的前缀，则称这样的编码为前缀编码，如果没有前缀编码容易出现歧义
• 由哈夫曼树得到哈夫曼编码：字符集中的每个字符作为一个叶子结点，各个字符出现的频度作为结点的权值，根据之前介绍的方法构造哈夫曼树

并查集

定义：

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

并查集的基本操作：

• Find：查操作，确定一个指定元素所属集合
• Union：并操作，将两个不相交的集合合并为一个

初始化：

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

并、查：

时间复杂度分析：

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

Union操作的优化：

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

并查集的压缩路径

• 核心想法就是让树越来越“矮”
• Find操作先找到根结点，再将查找路径上所有结点都挂到根结点下

• 这样的操纵可以让树的告诉不超过O(α(n))
• O(α(n))是一个增长很缓慢的函数，对于常见的n值，O(α(n))通常<=4
• 因此优化后的并查集Find、Union操作时间开销都很低

笔记完整PDF

百度网盘提取码：l3ja