数据结构_5树

参考王道计算机考研《数据结构》，自主进行知识点归纳总结，必备复习资料分享，方便大家备考时翻阅查看，提高复习效率，希望对大家备考有所帮助。

树

• 树、森林的遍历
  • 注意
    • 访问子树顺序都是自左向右
    • 普通的树和森林中的分支结点不一定只有两个子树 理解树的遍历和森林的遍历不能再局限于根左右
  • 树的遍历
    • 深度优先遍历
      • 先根遍历
        • 含义
          • 
          • 1. 若树非空，先访问根结点，再依次遍历根结点的每棵子树（左→右）
          • 2. 遍历子树时仍遵循先根后子树的原则
        • 与这棵树相应二叉树（孩子兄弟表示法）的先序序列相同
      • 后根遍历
        • 含义
          • 1. 若树非空，先依次对每棵子树进行后根遍历，最后再访问根结点
          • 2. 遍历子树时仍遵循先子树(左右子树)根后根的原则
        • 与这棵树相应二叉树（孩子兄弟表示法）的中序序列相同
    • 广度优先遍历
      • 层序遍历（用队列实现）
        • 若树非空，则根结点入队
        • 若队列非空，队头元素出队并访问， 同时将该元素的孩子依次入队(先左右后)
  • 森林的遍历
    • 先序遍历
      • 
      • 核心
        • 先访问根结点，再访问其对应的子树；对其子树仍使用同样规则
      • 访问森林中第一棵树的根结点
      • 先序遍历第一棵树中根结点的子树森林
      • 先序遍历除去第一棵树之后剩余的树构成的森林
      • 等同于依次对各个树进行先根遍历
      • 等同于依次对二叉树(孩子兄弟法)进行先序遍历
    • 中序遍历
      • 核心
        • 先访问其对应的子树，再访问根结点；对其子树仍使用同样规则
      • 中序遍历第一棵树中根结点的子树森林
      • 访问森林中第一棵树的根结点
      • 中序遍历除去第一棵树之后剩余的树构成的森林
      • 等同于依次对各个树进行后根遍历
      • 等同于依次对二叉树(孩子兄弟法)进行中序遍历
  • 树、森林与二叉树遍历关系
    •  一般只考选择题，若考到森林遍历的算法题，代码题——则先将森林用孩子兄弟法存储，然后再利用二叉树的先/中序遍历实现对应操作
    • 先序遍历（森林）——先根遍历（树）——二叉树先序遍历
    • 中序遍历（森林）——后根遍历（树）——二叉树中序遍历
      • 注意树的后根遍历为什么对应二叉树的中序遍历（后根遍历可理解为先访问完其左子树，然后再访问根）
    • 一棵树和森林
      • 森林是m棵互不相交的树的集合
      • 树是n个结点的有限集合，且满足注释条件
        • 
      • 一棵树去掉根结点后，其各个子树又组成森林
• 树的存储结构
  • 双亲表示法
    • 顺序存储
      • 顺序存储结点数据(数组)
      • 结点中保存父结点在数组中的下标
    • 优点：找父节点方便；缺点：找孩子不方便（从头遍历）
    • 基本操作
      • 增/删/查/补
        • 增：新增数据元素无需按逻辑上的次序存储，仅需插入到数组空缺位置即可 删： 删除结点为叶子结点：直接用其他结点的数据覆盖掉原有叶子结点的数据 删除结点不为叶子结点：删除以该结点为根结点的树（既要删除该叶子结点，也要删除以该叶子结点的所有子树）
  • 孩子表示法
    • 顺序+链式
      • 顺序存储结点数据(数组)
      • 结点中保存孩子链表头指针（该结点所有孩子组成的链表）
        • 
    • 优点：找孩子方便；缺点：找父结点不方便
  • 孩子兄弟表示法（常考）
    • 用二叉链表存储树——左孩子右兄弟
    • 孩子兄弟表示法存储的树，从存储视角来看形态上和二叉树类似
      • 
    • 树与二叉树的相互转换，本质就是用孩子兄弟表示法存储树
      • 
  • 森林与二叉树的转换
    • 用二叉链表存储深林——左孩子右兄弟
    • 森林中各个树的根结点之间视为兄弟关系
• 常考性质
  • 考点1
    • 结点数 = 总度数+1(根结点)
  • 考点2
    • 度为m的树
      • 至少有一个结点度为m
      • 结点数至少为m+1
    • m叉树
      • 所有结点的度都≤m（不存在度＞2的结点）
      • 可以是空树
    • 度为m的树、m叉树的区别
      • 
  • 考点3
    • 度为m的树第i层至多有多少个结点（每个结点都有m棵子树）
      • 
  • 考点4
    • 高度为h的m叉树至多有多少个结点（每个结点都有m棵子树）
      • 
  • 考点5
    • 高度为h、度为m至少有多少个结点
      • 保证至少有一个结点，它的子树为m个  
    • 高度为h的m叉树的树至少有多少个结点
      • 
  • 考点6
    • 具有n个结点的m叉树的最小高度为？（向上取整）
      • 解题思想：树尽量往宽度长，而不是往深度（高度）长 
• 基本术语
  • 结点之间的关系
    • 父结点（双亲结点）、孩子结点
    • 祖先结点、子孙结点
    • 兄弟节点、堂兄弟结点（同一层结点/父节点在同一层）
    • 结点之间的路径
      • 只能从上往下
    • 路径长度
      • 路径上经过多少条边
  • 结点、树的属性
    • 结点的层次（深度）——由上往下数
    • 结点的高度——由下往上数
    • 结点的度
      • 结点的分支数（树中一个结点的孩子个数）
    • 树的度
      • 树中各结点的度的最大值
  • 有序树V.S无序树
    • 树中结点的各子树是否有序，位置是否可换
      • 同一结点的各子树位置是否可换
  • 森林
    • 由m（m≥0）个互不相交的树组成森林
  • 树与森林
    • 树的根结点删去就成了森林
    • m棵独立的树加上一个结点，把这m棵树为该结点的子树（森林->树）
• 易错点
  • 向上/向下取整
    • 向上取整
    • 向下取整
  • 具有n个结点的m叉树的最小高度为？（向上取整）
    • 解题思想：树尽量往宽度长，而不是往深度（高度）长 
  • 具有n个(n>0)结点的完全二叉树的高度h <---->完全二叉树第i个结点所在层次为
    • 向上取整（由右闭≥决定）
      • 
      • 由高为h--高为h-1的满二叉树结点数范围所确定（左开右闭）
        •  
    • 向下取整（由左闭≥决定）
      •  小于等于--->即对该数向下取整
      • 高为h的完全二叉树结点数区间决定（左闭右开）
        •  
• 树的应用
  • 二叉排序树（BST，Binary Search Tree）
    • 定义
      • 左子树结点值<根结点值<右子树结点值
      • 默认不允许两个结点的关键字相同
      • 进行中序遍历，可以得到一个递增的有序序列
    • 查找操作
      • 从根结点开始，目标值更小往左找，目标值更大往右找
      • 算法思路
        • 若树非空，目标值与根结点值比较
          • 若相等，则查找成功
          • 若小于根结点，则在左子树上查找，否则在右子树上查找
        • 查找成功，返回结点指针；查找失败，返回NULL
      • 代码实现
        • 递归实现
          • 
        • 非递归实现
          • 
    • 插入操作
      • 若原二叉排序树为空，则直接插入结点
      • 循环
        • 若关键字k小于根结点，则插入到左子树
        • 若关键字k大于根结点，则插入到右子树
      • 插入结点
        • 遇到空指针，插入结点（一定是叶子结点的左/右孩子指针）
      • 注意
        • 树中存在相同关键字的结点，插入失败 （BST不允许存在两个相同的结点）
        • 传入指针为引用，需要修改指向插入位置的指针（其父结点指针）
    • BST的构造
      • BST的构造<--->BST插入操作
      • 不同的关键字序列可以得到同样BST，也可以得到不同BST
    • 删除操作（最难）
      • 先搜索找到目标结点
      • 目标结点
        • 叶子结点
          • 直接删除
        • 分支结点
          • 只有一棵左子树或右子树，则z的子树成为z父结点的子树
            • 代替z位置
          • 有左子树和右子树
            • 分析思路
              • 则令z的直接后继（或直接前驱）代替z
              • 从BST中删除这个直接后继（或直接前驱）（转为①或②）
            • z的直接后继
              • 
              • z的右子树中最左下结点（该结点一定没有左子树）
            • z的直接前驱
              • 
              • z的左子树中最右下结点（该结点一定没有右子树）
      • 删除结点后，仍需保持BST性质 （左子树结点值<根结点值<右子树结点值）
    • 查找效率分析
      • 在查找运算中，需要对比关键字的次数称为查找长度
      • ASL
        • Average Search Length
        • 查找成功
          • 总的查找长度/结点数
            • 
        • 查找失败
          • 总的查找长度/空结点数
            • 
          • 查找空结点不需要对比关键字 (查找函数遇到空指针就已经退出循环，返回空指针)
      • 取决于树的高度，最好为O(log n),最坏为O(n)
  • 平衡二叉树（AVL树）
    • 概念
      • 平衡因子
      • 最小不平衡子树
        • 从插入点往回找到第一个不平衡结点，调整以该结点为根的子树（最小不平衡树）
      • 实现f向右下旋转（其左孩子右上旋）
      • 实现f向左下旋转（其右孩子左上旋）
    • 定义
      • 树上任一结点的左子树和右子树高度之差(结点的平衡因子)不超过1
      • 注意
        • 平衡二叉树结点的平衡因子值只可能是-1，0，1
        • 只要有任一结点的平衡因子绝对值大于1-->该树不是平衡二叉树
    • 插入操作
      • 同二叉排序树一样，找合适的位置插入
      • 新插入的结点可能导致其祖先们平衡因子改变，导致失衡
    • 调整不平衡PPT5.5_2
      • 找到最小不平衡子树进行调整，即最小不平衡子树的根为A
      • LL
        • 在A的左孩子的左子树插入导致A不平衡
        • 将A的左孩子右上旋
      • RR
        • 在A的右孩子的右子树插入导致A不平衡
        • 将A的右孩子左上旋
      • LR
        • 在A的左孩子的右子树插入导致A不平衡
        • 将A的左孩子的右孩子先左上旋，再右上旋
      • RL
        • 在A的右孩子的左子树插入导致A不平衡
        • 将A的右孩子的左孩子先右上旋，再左上旋
    • 查找效率分析
      • 深度为h的平衡树中含有的最少结点数nh——递推求解
        • n0=0;n1=1;n2=2 并且有nh = nh-1 + nh-2 +1（递推公式）
      • 平衡二叉树最大深度为O(log n) 平均查找长度/查找的时间复杂度为O(log n)
  • 哈夫曼树
    • 概念
      • 结点的权
        • 某种特定含义的数值（如表示该结点的重要程度）
        • 带权的结点都是叶子结点
      • 结点的带权路径长度 = 根到结点路径长度*结点的权值
      • 树的带权路径长度（WPL）= 树中所有叶子结点的带权路径之和
      • 哈夫曼树（最优二叉树）
        • 在含有给定的n个带权叶结点的二叉树中，WPL最小的树
    • 构造哈夫曼树
    • 哈夫曼编码
• 二叉树
  • 存储结构
  • 基本概念、特点、性质
    • 基本概念
      • 定义
        • 或为空二叉树
        • 或由一个根结点和两个互不相交的被称为根的左子树和右子树组成
      • 特点
        • 左子树、右子树不可颠倒（有序树）
        • 任意结点的度≤2
      • 二叉树V.S度为2的有序树
        • 度为2的有序树
          • 结点次序
            • 结点次序是相对于另一结点而言，若有序树中的子树只有一个孩子，这个孩子结点就无须区分其左右次序
          • 至少有一个结点的度＝2
        • 二叉树
          • 结点次序
            • 无论其孩子树是否为2，均需确定其左右次序，也就是说而二叉树的结点次序不是相对于另一个结点而言而是确定的
          • 结点的度≤2（结点的度可以都<2）
    • 特殊二叉树
      • 满二叉树
        • 
        • 高度为h，含有2^h-1个结点的二叉树
        • 特点
          • 只有最后一层有叶子结点
          • 不存在度为1的结点（只有度为0/2的结点）
          • 按层序从1开始编号，结点i
            • 左孩子为2i
            • 右孩子为2i+1
            • 父节点为[i/2]（不大于i/2的最大整数——向下取整）
      • 完全二叉树
        • 
        • 在满二叉树的基础上可去掉若干个编号更大的结点
        • 特点
          • 只有最后两层有叶子结点
          • 最多只有一个度为1的结点
          • 按层序从1开始编号，结点i
            • 
            • 左孩子为2i
            • 右孩子为2i+1
            • 父节点为⌊i/2⌋ （不大于i/2的最大整数——向下取整）
          • n≤⌊n/2⌋为分支结点， i>⌊n/2⌋（≥⌊n/2⌋+1）为叶子结点
            • 第n个结点的父结点的下一结点开始都为叶子结点
      • 二叉排序树
        • 左子树关键字<根结点关键字<右子树关键字
        • 二叉排序树可用于元素的排序、搜索
      • 平衡二叉树
        • 左右子树深度差不超过1
        • 特性
          • 能有更高的搜索效率
    • 常考性质
      • 二叉树
        • 考点1
          • n0 = n2 + 1
            • 树的结点数 = 总度数(每个结点贡献的子节点数)+1（根结点） n = n1+2n2+1 树中总结点个数 n = n0 + n1 + n2
        • 考点2
          • 二叉树第i层至多只有2^(i-1)个结点
            • 
        • 考点3
          • 高度为h的二叉树至多有2^h-1个结点（满二叉树）
      • 完全二叉树
        • 考点1
          • 具有n个(n>0)结点的完全二叉树的高度h <---->完全二叉树第i个结点所在层次为
            • 由高为h--高为h-1的满二叉树结点数范围所确定（左开右闭）
              •  
            • 高为h的完全二叉树结点数区间决定（左闭右开）
              •  
        • 考点2
          • 结点数n--->n0,n1,n2（完全二叉树）
            • 突破点 完全二叉树最多只会有一个度为1的结点 n1 = 0或1 n0 = n2 + 1--->n0 + n2 一定是奇数(n0 + n2 = 2n2+1)
            • 2k个（偶数）个结点
              • n1 = 1；n0 = k；n2 = k-1
            • 2k-1个（奇数）个结点
              • n1 = 0；n0 = k；n2 = k-1
  • 二叉树的遍历
    • 先/中/后序遍历
      • 基于树的递归特性确定的次序规则
      • 三种方法
        • 空间复杂度 O(h+1(调用函数判定空树)) = O(h)
          • 应用:求解树的高度
        • 先序遍历（先根遍历）
          • 根、左、右
        • 中序遍历（中根遍历）
          • 左、根、右
        • 后序遍历（后根遍历）
          • 左、右、根
      • 遍历算数表达式树
        • 来源
          • 表达式的运算优先级AND左优先原则--->中缀表达式（e1）OP（e2） 令根结点值为OP（算术运算符） 左子树为e1，右子树e2，e1与e2递归（直到e1和e2只有操作数） 例子：1+2*（3-4）-5/6 = （1+(2*（3-4）)）-（5/6) 先序：分析步骤 - （1+(2*（3-4）)） （5/6) - + 1 (2*（3-4）/ 5 6 - + 1 * 2 (3-4) / 5 6 - + 1 * 2 - 3 4 / 5 6
        • 先序遍历得前缀表达式
        • 中序遍历得中缀表达式（没有括号-需要加界限符）
        • 后序遍历得后缀表达式
      • 考点：求遍历序列
        • 分支结点逐层展开（对子树采用同样方式递归遍历）
        • 遍历路线法
          • 脑补空结点(叶子结点左右孩子为空结点) 从根节点出发，画一条路：（以下实质为先序遍历的规则） 左边还有路，优先往左边走，走到路的尽头（空结点）就往回走 左边没路，就往右边走 左、右都没路，则往上面走 
          • 先序—第一次路过时访问即输出该结点
          • 中序—第二次路过时访问即输出该结点
          • 后序—第三次路过时访问即输出该结点
        • 叶子节点应理解为左右子树为空树
          • 先、中、后序所得遍历序列均是只有一个叶子结点
    • 层序遍历
      • 算法思想
        • 初始化一个辅助队列
          • 用于临时存放待访问的结点
        • 根结点入队
        • 重复循环
          • I. 若队列非空，则队头结点出队
            • 访问该结点
            • 并将其左、右孩子插入队尾（如果有的话）
          • II. 重复I直至队列为空
      • 注意
        • 存指针而不是结点
          • 比保存结点本身所需的空间少
    • 由遍历序列构造二叉树
      • 遍历序列的组合（必须有中序序列）
        • 前序+中序遍历序列
        • 后序+中序遍历序列
        • 层序+中序遍历序列
          • 
        • 前序、后序、层序序列的两两组合无法唯一确定一棵二叉树 (无中序序列不能划分左右子树)
          • 
      • 各种遍历序列所获知信息
        • 前序遍历序列
          • 根结点 左子树的前序遍历序列 右子树的前序遍历序列
        • 中序遍历序列
          • 左子树的前序遍历序列 根结点 右子树的前序遍历序列
        • 后序遍历序列
          • 左子树的前序遍历序列 右子树的前序遍历序列 根结点
        • 层序遍历序列
          • 根结点 左子树的根结点 右子树的根结点
      • 关键步骤（递归使用）
        • 1. 找到树的根节点，并根据中序序列划分左右子树
        • 2. 再找到左右子树根节点，并据左右子树中序序列划分左右孩子的子树
  • 线索二叉树
    • 问题引入
      • 能否从一个指定结点开始中序遍历（不能-只能从根结点出发）
        • 从指定结点开始，只能找到指定结点的孩子，不能找到双亲
      • 如何找到指定结点p在中序遍历序列中的前驱
        • 从根节点出发，重新进行一次中序遍历 指针q记录当前访问的结点，指针pre记录上一个被访问的结点 ①当q==p时，pre为前驱 ②当pre==p时，q为后继
    • 概念
      • 线索
        • 指向前驱/后继的指针成为线索
      • 中序前驱/中序后继
        • 指定结点在中序遍历序列的前驱/后继结点
      • 先序前驱/先序后继、后序前驱/后序后继
    • 存储结构
      • 利用二叉树n+1个空链域连上结点的前驱、后继
        • 若本来指向左右孩子，则不改变
      • 在普通二叉树结点的基础上，增加两个标志位ltag和rtag
      • ltag
        • ltag == 1
          • 表示lchlid指向前驱
        • ltag == 0
          • 表示lchlid指向左孩子
      • rtag
        • rtag == 1
          • 表示lchlid指向后继
        • rtag == 0
          • 表示lchlid指向右孩子
    • 三种线索二叉树
      • 中序线索二叉树
        • 以中序遍历序列为依据进行"线索化"
      • 先序线索二叉树
        • 以先序遍历序列为依据进行"线索化"
      • 后序线索二叉树
        • 以后序遍历序列为依据进行"线索化"
    • 作用
      • 方便从一个指定结点出发，找到其前驱、后继
      • 方便遍历先/中/后序遍历序列
    • 二叉树的线索化
      • 手算
        • 确定线索二叉树类型-中序、先序OR后序？
        • 按照对应遍历规则，确定各个结点的访问顺序，并写上编号
        • 将n+1个空链域连上前驱、后继
      • 代码实现
        • 算法思路
          • 中序/先序/后序遍历算法的改造
        • 核心
          • 用一个指针pre 记录当前访问结点的前驱结点
          • 当访问一个结点时，连接该结点与前驱结点的线索信息
            • 1. 前驱结点的右孩子指针是否为空？
            • 2. 当前结点的左孩子指针是否为空？
      • 易错点
        • 1. 最后一个结点的rchild，rtag的处理（完全利用所有结点的空链域）
        • 2. 先序线索化中，注意处理陷入死循环的问题； 当itag==0时，才能对左子树先序线索化
          •  只有先序线索化才有可能出现死循环的问题，因先序线索化是按照左根右访问各个结点 根结点首先被访问，如果根结点的左子树为空，则将会连接该节点与其前驱结点，然后又访问其左孩子指针，所以会陷入循环，所以需要判断左孩子指针是否真的指向左孩子，若指向的是前驱（前驱线索），则应该跳过对其左子树先序线索化
    • 在线索二叉树中找p前驱后继(X-二叉链表下无法实现)
      • 
      • 中序线索二叉树（左根(p)右(左根右)）
        • 后继
          • p的右子树中最左下结点
        • 前驱
          • p的左子树中最右下结点
      • 先序线索二叉树（根(p)左右）
        • 后继
          • 若p有左孩子，则先序后继为左孩子(根p左右-根p(根左右)右)
          • 若p没左孩子，则先序后继为右孩子(根p右-根p(根左右))
        • 前驱(若能找到p的父节点)
          • 且p是左孩子(根(根p左右)右)，则p的父结点即为其前驱结点
          • 且p是右孩子，其左兄弟为空，则p的父结点即为其前驱结点
          • 且p是右孩子，其左兄弟非空，则p的前驱为其左兄弟子树 最后一个被先序遍历的结点（p父左(根左右)(根p左右)）
            • 左兄弟子树找到靠右且最深一层的结点，搜索顺序的优先级如下： 左兄弟结点(根结点)的右子树 根结点无右子树，则转为根结点的左子树 若上面两步条件都不满足，则当前搜索到的结点即为结点p的前驱
          • 若p是根结点，则p没有先序前驱
      • 后序线索二叉树
        • 后继(若能找到p的父节点)
          • 且p是右孩子((左)(左右根p)p父)，则p的父结点为其后继
          • 且p是左孩子((左右根p)p父)，且右兄弟为空，则p的父结点为其后继
          • 且p是左孩子，其右兄弟非空，则p的后继为其右兄弟子树 第一个被后序遍历的结点（(左右根p)(左右根)p父）
            • 右兄弟子树找到靠左且最深一层的结点，搜索顺序的优先级如下： 左兄弟结点(根结点)的左子树 根结点无左子树，则转为根结点的右子树 若上面两步条件都不满足，则当前搜索到的结点即为结点p的前驱
          • 若p是根结点，则p没有先序后继
        • 前驱
          • 若p有右孩子，则先序后继为右孩子(左右根p-左右(左右根(p右))p)
          • 若p没右孩子，则先序后继为左孩子(左根p-左(左右根(p左))p)
      • 思路
        • 分支结点逐层展开（分析方法）
        • 特殊情况
          • 结点p是其父结点的左孩子，且右兄弟为空
          • 结点p是其父结点的左孩子，且有右兄弟
          • 结点p是其父结点的右孩子，且左兄弟为空
          • 结点p是其父结点的右孩子，且有左兄弟