数据结构_5_1二叉树

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

二叉树

• 存储结构
• 基本概念、特点、性质
  • 基本概念
    • 定义
      • 或为空二叉树
      • 或由一个根结点和两个互不相交的被称为根的左子树和右子树组成
    • 特点
      • 左子树、右子树不可颠倒（有序树）
      • 任意结点的度≤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
          • 树的结点数 = B+1（分支总数+1(根结点)） 除根结点外，其余结点都有一个分支进入（一个分支——一个结点），而B=n1+2n2（度为1的结点射出一个分支，度为2的结点射出两个分支） 树中总结点个数 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是其父结点的右孩子，且有左兄弟