二叉树

二叉树（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，

树

• 树的基本概念
  • 定义
    • 形式化定义
      • T={D，R}，D为包含n个节点的有穷集合，R为关系。n等于0时为空树
      • 根节点：没有前驱节点。其余节点：仅有一个前驱节点
      • 每个节点都可有0个或多个后继节点
    • 递归定义
      • 树是由n个节点组成的有限集合
      • n等于0为空树，>0时存在一个根节点（root），余节点可分为互不相交的有限集T1.2.....每一颗子树都是符合本定义的树
  • 结点
    • 根节点：树只有一个根结点
    • 结点的度：结点拥有的子树的数量
      • 度为0：叶子结点或者终端结点
      • 度不为0：分支结点或者非终端结点
    • 分支结点除去根结点也称为内部结点
  • 树的度：树中所有结点的度数的最大值
  • 结点关系
    • 祖先结点
      • 根结点到该结点的唯一路径的任意结点
    • 子孙结点
    • 双亲（父）结点
      • 根结点到该结点的唯一路径上最接近该结点的结点
    • 孩子结点
    • 兄弟结点
      • 有相同双亲结点的结点
    • 结点之间的路径--只能从上往下
    • 路径长度--路径上经过多少条边
  • 有序树与无序树
    • 有序树——逻辑上看，树中结点的各子树从左至右是有次序的，不能互换
    • 无序树——逻辑上看，树中结点的各子树从左至右是无次序的，可以互换
  • 树与森林
    • 森林是m（m≥0）棵互不相交的树的集合
      • m可为0，空森林
  • 层次，高度，深度，树的高度
    • 层次：根为第一层，它的孩子为第二层，以此类推
    • 结点的深度：根结点开始自顶向下累加
    • 结点的高度：叶节点开始自底向上累加
    • 树的高度（深度）：树中结点的最大层数
• 树的性质
  • 1.树中的结点数等于所有结点的总度数加1
  • 2.度为m的树、m叉树 的区别
  • 3.
  • 4.
  • 5.
  • 6.
• 树的存储结构
  • 顺序存储结构
    • 双亲表示法
      • 用一组连续的存储空间存储树的结点，同时在每个结点中，用一个变量存储该结点的双亲结点在数组中的位置
      • 代码
      • 例子
      • 分析
        • 优点
          • 找父节点方便
        • 缺点
          • 找孩子不方便
  • 顺序+链式存储
    • 孩子表示法
      • 把每个结点的孩子结点排列起来存储成一个单链表。所以n个结点就有n个链表；如果是叶子结点，那这个结点的孩子单链表就是空的；然后n个单链表的的头指针又存储在一个顺序表（数组）中
      • 代码
      • 例子
      • 分析
        • 顺序存储结点数据，结点中保存孩子链表头指针
        • 优点
          • 找孩子方便
        • 缺点
          • 找父节点不方便
  • 链式存储结构
    • 孩子兄弟表示法
      • 顾名思义就是要存储孩子和孩子结点的兄弟，具体来说，就是设置两个指针，分别指向该结点的第一个孩子结点和这个孩子结点的右兄弟结点
      • 代码
      • 例子
      • 分析
        • 孩子兄弟表示法存储的树，从存储视角来看形态上和二叉树类似
        • 树与二叉树的相互转换。本质就是用孩子兄弟表示法存储树
  • 二叉树与树转换
  • 二叉树与森林转换
    • 本质上用二叉链表存储森林——左孩子右兄弟
      • 森林中各个树的根节点之间视为兄弟关系
• 树和森林的遍历
  • 树的遍历
    • 每个节点只能被访问一次
    • 三种遍历方法
      • 前序遍历（先根遍历，自左而右）
        • 与这棵树相应的二叉树（孩子兄弟表示法）的先序序列相同
      • 后序遍历（后根遍历，自左而右）
        • 与这棵树相应的二叉树（孩子兄弟表示法）的中序序列相同
      • 可称为树的深度优先遍历
      • 层次遍历（自上而下，自左而右），用队列实现，可称为树的广度优先遍历
        • ①若树非空，则根节点入队②若队列非空，队头元素出队并访问，同时将该元素的孩子依次入队③重复②直到队列为空
  • 森林的遍历
    • 先序遍历
      • 遍历结果等同于依次对各个树进行先根遍历
      • 把森林转化成相应的二叉树，遍历结果等同于依次对二叉树进行先根遍历
    • 中序遍历
      • 遍历结果等同于依次对各个树进行后根遍历
      • 把森林转化成相应的二叉树，遍历结果等同于依次对二叉树进行中根遍历
• 二叉树
  • 定义
    • 二叉树是n（n≥0）个结点的有限集合：① 或者为空二叉树，即n=0。② 或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别是一棵二叉树。
      • 1.每个结点最多有两棵子树。
      • 2.左右子树不能颠倒，二叉树是有序树
  • 二叉树的五种基本形态：
    • 1.空树
    • 2.只有一个根结点
    • 3.根结点只有左子树
    • 4.根结点只有右子树
    • 5.根结点既有左子树又有右子树
  • 特殊二叉树
    • • • 如果某个结点只有一个孩子，那一定是左孩子
    • • 二叉排序树可用于元素的排序、搜索
    • • 有更高的搜索效率
  • 二叉树的性质
    • 完全二叉树
• 二叉树的存储结构
  • 顺序存储
    • 二叉树的顺序存储结构就是用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素，节点编号与完全二叉树对应
    • 代码
    • 基本操作
    • 分析
      • 二叉树的顺序存储中，一定要把二叉树的结点编号与完全二叉树对应起来
      • 最坏情况：高度为 h 且只有 h 个结点的单支树（所有结点只有右孩子），也至少需要 2h-1 个存储单元
      • 只适合存储完全二叉树
  • 链式存储（二叉链表）
    • 代码
    • 操作
    • 分析
      • 找到指定结点的左/右孩子很简单，找到指定结点的父结点只能从根开始遍历寻找
      • 如果要频繁地查找父节点，可以增加父节点指针形成三叉链表
      • n个结点的二叉链表共有 n+1 个空链域
        • 可以用于构造线索二叉树
• 二叉树的遍历
  • 先序遍历：1）访问根结点；2）先序遍历左子树；3）先序遍历右子树。
    • • 递归
    • • 非递归
  • 中序遍历：1）中序遍历左子树；2）访问根结点；3）中序遍历右子树。
    • • 递归
    • • 非递归
  • 后序遍历：1）后序遍历左子树；2）后序遍历右子树；3）访问根结点。
    • • 递归
    • • 非递归
  • 层次遍历：
    • 算法思想
      • ①初始化一个辅助队列
      • ②根结点入队
      • ③若队列非空，则队头结点出队，访问该结点，并将其左、右孩子插入队尾（如果有的话）
      • ④重复③直至队列为空
    • 代码
  • 由遍历序列构造二叉树
    • 若只给出一棵二叉树的 前/中/后/层 序遍历序列中的一种，不能唯一确定一棵二叉树
    • 唯一确定
      • 前序+中序
      • 后序+中序
      • 层序+中序
    • 关键
      • 找到树的根节点，并根据中序序列划分左右子树，再找到左右子树根节点
  • 扩展
    • 二叉树的遍历本质上是将一个复杂的非线性结构转换为线性结构
    • 算数表达式的“分析树”
      • 总结
        • 先序遍历 --> 前缀表达式
        • 中序遍历 --> 中缀表达式（需要加界限符）
        • 后序遍历 --> 后缀表达式
    • 求树的深度
• 线索二叉树
  • N个结点的二叉链表，每个结点都有指向左右孩子的结点指针，所以一共有2N个指针，而N个结点的二叉树一共有N-1条分支，也就是说存在2N-(N-1)=N+1个空指针。左图二叉树中有6个结点，那么就有7个空指针。
  • 大量的空余指针能否利用起来？
    • 指向前驱和后继的指针称为线索，加上线索的二叉链表就称为线索链表，相应的二叉树就称为线索二叉树
    • 对二叉树以某种次序遍历使其变为线索二叉树的过程就叫做线索化
  • 存储结构
    • 在普通二叉树结点的基础上，增加两个标志位Itag和rtag
    • • ltag==1时，表示Ichild指向前驱；ltag==0时，表示Ichild指向左孩子
      • rtag==1时，表示rchild指向后继；rtag==0时，表示rchild指向右孩子
  • 优点
    • 解决了无法直接找到该结点在某种遍历序列中的前驱和后继结点
      • 方便遍历
    • 方便从一个指定结点出发，找到其前驱、后继
    • 解决了二叉链表找左右孩子困难的问题
  • 分类
    • 前序线索二叉树
      • 以先序遍历序列为依据进行“线索化"
      • 线索化代码
    • 中序线索二叉树
      • 以中序遍历序列为依据进行“线索化”
      • 线索化代码
    • 后序线索二叉树
      • 以后序遍历序列为依据进行“线索化”
      • 线索化代码
  • 手算画出线索二叉树
    • • 确定线索二又树类型——中序、先序、or后序
      • 按照对应遍历规则，确定各个结点的访问顺序，并写上编号
      • 将n+1个空链域连上前驱、后继
  • 找前驱/后继
    • 中序线索二叉树
      • 后继
        • 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没有右孩子，则后序前驱为左孩子
    • 总结
• 二叉排序树
  • 分析
    • 二叉排序树(Binary Search Tree 也叫二叉搜索树)或者是一棵空树，或者是具有以下性质的二叉树①若左子树不空，则左子树上所有结点的值均小于它的根结点的值。②若右子树不空，则右子树上所有结点的值均大于它的根结点的值。③它的左右子树也是一棵二叉排序树。
      • 左子树结点值 < 根结点值 < 右子树结点值
      • 进行中序遍历，可以得到一个递增的有序序列
    • 查找效率
      • 查找时间复杂度是O(n)
    • 查找长度
      • 查找成功
      • 查找失败
        • 需补充失败结点
  • 构造
  • 查找
    • 由于二叉排序树的特点(左子树<根结点<右子树),所以每次查找一个关键字，需要先和根结点进行比较：如果这个关键字小于根结点的值，则再到这个根结点的左子树进行同样的比较操作一直进行下去直到找到该关键字，表示查找成功，或者是空指针，表示查找失败。如果这个关键字大于根结点的值，则再到这个根结点的右子树进行同样的比较操作一直进行下去直到找到该关键字，表示查找成功，或者是空指针，表示查找失败。
  • 插入
    • 1)空树：直接插入新结点返回成功2)树不空：检查是否存在关键字重复的结点：①存在：返回插入失败②不存在：检查根结点的值和待插入关键字值的大小关系递归插入左右子树
  • 删除结点
    • ①删除的是叶子结点
      • 方法：直接删去该结点即可
    • ②删除的是仅有左子树或者右子树的结点
      • 方法：“子承父业”
    • ③删除的是左右子树都有的结点
      • 可用其后继结点顶替，再删除后继结点
        • 后继：右子树中最左下的结点
      • 或用其前驱结点顶替，再删除前驱结点
        • 前驱：左子树中最右下的结点
• 平衡二叉树(AVL树)
  • 分析
    • 平衡二叉树(AVL树)是特殊的二叉排序树，特殊的地方在于左右子树的高度之差绝对值不超过1，而且左右子树又是一棵平衡二叉树。
    • 平衡因子
      • 定义结点左子树与右子树的高度差为该结点的平衡因子，则平衡二叉树结点的平衡因子的值只可能是−1、0或1。
      • 平衡因子=左子树高-右子树高
    • 含有n个结点平衡二叉树的最大深度为O(logn)，因此，平衡二叉树的平均查找长度/时间复杂度为O(logn)
  • 平衡调整
    • 概念
      • 平衡二叉树的建立过程和二叉排序树的建立过程是相似的，都是从一棵空树开始陆续插入结点。不同的地方在于对于平衡二叉树的建立过程中，由于插入结点可能会破坏结点的平衡性，所以需要进行平衡调整。
      • 找到最小不平衡子树进行调整，记最小不平衡子树的根为A
    • 分类
      • LL调整(A的左孩子的左子树上插入结点导致)
        • 由于在结点A的左孩子（L）的左子树（L）上插入了新结点，A的平衡因子由1增至2，导致以A为根的子树失去平衡，需要一次向右的旋转操作。将A的左孩子B向右上旋转代替A成为根结点，将A结点向右下旋转成为B的右子树的根结点，而B的原右子树则作为A结点的左子树
        • • “正则右旋”
          • 只有左孩子才能右上旋
        • 代码思路
      • RR调整(A的右孩子的右子树上插入结点导致)
        • 由于在结点A的右孩子（R）的右子树（R）上插入了新结点，A的平衡因子由-1减至-2，导致以A为根的子树失去平衡，需要一次向左的旋转操作。将A的右孩子B向左上旋转代替A成为根结点，将A结点向左下旋转成为B的左子树的根结点，而B的原左子树则作为A结点的右子树
        • • “负则左旋”
          • 只有右孩子才能左上旋
        • 代码思路
      • LR调整(A的左孩子的右子树上插入结点导致)
        • 由于在A的左孩子（L）的右子树（R）上插入新结点，A的平衡因子由1增至2，导致以A为根的子树失去平衡，需要进行两次旋转操作，先左旋转后右旋转。先将A结点的左孩子B的右子树的根结点C向左上旋转提升到B结点的位置，然后再把该C结点向右上旋转提升到A结点的位置
        • • 左旋右旋
          • 变成LL再操作
      • RL调整(A的右孩子的左子树上插入结点导致)
        • 由于在A的右孩子（R）的左子树（L）上插入新结点，A的平衡因子由-1减至-2，导致以A为根的子树失去平衡，需要进行两次旋转操作，先右旋转后左旋转。先将A结点的右孩子B的左子树的根结点C向右上旋转提升到B结点的位置，然后再把该C结点向左上旋转提升到A结点的位置
        • • 右旋左旋
          • 变成RR再操作
  • 插入
    • 和二叉排序树一样，找合适的位置插入
    • 新插入的结点可能导致其祖先们平衡因子改变，导致失衡
    • 在插入操作中，只要将最小不平衡子树调整平衡，则其他祖先结点都会恢复平衡
• 哈夫曼树和哈夫曼编码
  • 概念
    • 结点的权：某种特定含义的数值
    • 结点的带权路径长度=根到结点路径长度 * 结点的权值
    • 树的带权路径长度（WPL）=树中所有叶子结点的带权路径长度之和
    • 哈夫曼树（最优二叉树）：在含有给定的n个带权叶结点的二又树中，WPL最小的二叉树
  • 构造算法
    • 1）将这N个结点分别作为N棵仅含一个结点的二叉树，构成森林F。2）构造一个新结点，并从F中选取两棵根结点权值最小的树作为新结点的左、右子树，并且将新结点的权值置为左、右子树上根结点的权值之和。3）从F中删除刚才选出的两棵树，同时将新得到的树加入F中。4）重复步骤2）和3），直至F中只剩下一棵树为止。
    • 例子
    • 要点
      • 哈夫曼树不唯一，但WPL必然都是最小值
  • 特点
    • 每个初始结点最终都成为叶结点，且权值越小的结点到根结点的路径长度越大
    • 构造过程中共新建了n-1个结点(双分支结点)，因此哈夫曼树的结点总数为2n-1
    • 每次构造都选择2棵树作为新结点的孩子，因此哈夫曼树不存在度为1的结点
  • 哈夫曼编码
    • 概念
      • 将字符频次作为字符结点权值，构造哈夫曼树，即可得哈夫曼编码
      • 哈夫曼树不唯一，因此哈夫曼编码不唯一
      • 可用于数据压缩
    • 例子
    • 分类
      • 前缀编码
        • 没有一个编码是另一个编码的前缀
      • 固定长度编码
        • 每个字符用相等长度的二进制位表示
      • 可变长度编码
        • 允许对不同字符用不等长的二进制位表示