《数据结构》第五章-树与二叉树

《数据结构》第五章-树与二叉树知识梳理，包括树的基本概念、二叉树的概念、二叉树的遍历和线索二叉树等等。

数与二叉树

• 
• 树的基本概念
  • 定义
    • 树是n个结点的有限集，非空树应满足：
      • 有且仅有一个根节点
      • n>1时，其余结点可以分为m个互不相交的有限集Ti，每个集合都是根的子树
  • 基本术语
    • 祖先、子孙、双亲、孩子、兄弟
    • 度：结点的孩子个数
      • 结点的最大度数称为树的度
    • 叶子结点（终端结点）、分支节点（非终端结点）
      • 树的结点度数之和=分支数之和=结点数-1
    • 深度：从根结点开始自顶向下逐层累加
    • 高度：从叶结点开始自底向上逐层累加
    • 有序树、无序树
    • 路径、路径长度
    • 森林：m棵互不相交的树的集合
  • 性质
    •  
    • 树的结点数=所有结点的度数和+1
    • 度为m的树中第i层上至多有m^(i-1)个结点
    • 高度为h的m叉树至多有(m^h-1)/(m-1)个结点
    • 具有n个结点的m叉树的最小高度为：
• 二叉树的概念
  • 定义及特性
    • 定义：每个结点至多只有两棵子树，且子树有左右之分
    • 特殊的二叉树
      • 满二叉树
        • 高度为h，结点数为2^h-1
        • 对于编号为i的结点
          • 双亲：
          • 左孩子：2i
          • 右孩子：2i+1
      • 完全二叉树
        • 每个结点的编号都与满二叉树对应（即只有右侧的叶子结点为空）
        • 性质
          • ①若i≤Ln/2」,则结点i为分支结点，否则为叶子结点。
          • ②叶子结点只可能在层次最大的两层上出现。对于最大层次中的叶子结点，都依次排列在该层最左边的位置上。
          • ③若有度为1的结点，则只可能有一个，且该结点只有左孩子而无右孩子。
            • 若完全二叉树的结点总数为偶数，则有一个度=1的结点；否则没有
          • ④按层序编号后，一旦出现某结点(编号为i)为叶子结点或只有左孩子，则编号大于i 的结点均为叶子结点。
          • ⑤若n为奇数，则每个分支结点都有左孩子和右孩子；若r为偶数，则编号最大的分支结点(编号为n/2)只有左孩子，没有右孩子，其余分支结点左、右孩子都有。
          • ⑥具有n个结点的完全二叉树的高度为：
            • 
      • 二叉排序树
        • 左子树关键词<根节点<右子树
        • 左右子树又各是一棵二叉排序树
      • 平衡二叉树
        • 树上任一结点的左子树和右子树的深度之差不超过1
    • 二叉树的性质
      • 非空二叉树上的叶子结点数=度为2的结点数+1，即n0=n2+1
        • 
      • 非空二叉树上第k层上至多有2^(k-1)个结点
      • 高度为h的二叉树至多有2^h-1个结点
  • 二叉树的存储结构
    • 顺序存储结构
      •  
      • • 
    • 链式存储结构
      • • n个结点的二叉链表中，含有n+1个空链域
• 二叉树的遍历和线索二叉树
  • 二叉树的遍历
    • 先序遍历（NLR）
      • “序”指的是根节点在何时被访问
    • 中序遍历（LNR）
    • 后序遍历（LRN）
    • 递归算法→非递归（借助栈）
      • • 中序遍历的非递归算法
          • 先序和中序我们都用深度优先的方式实现， 所以对一棵树或者子树进行先序或者中序遍历时入栈顺序相同， 都是根节点、左子树、右子树，（注意是入栈） 先序访问后入栈，中序出栈后访问， 故先序序列就是入栈顺序，中序序列就是出栈顺序。
    • 层次遍历（借助队列）
    • 由遍历序列构造二叉树
      • 由二叉树的先序（or后序）序列和中序序列可以唯一确定一棵二叉树
        • 先序序列的首结点必为根节点，根节点将中序序列分成左右子树两个序列
        • 根据中序的左右子树找到先序中的左右子树，分别递归地重复上述步骤
      • 由二叉树的层序序列和中序序列可以唯一确定一棵二叉树
      • 根据二叉树的先序和后序序列，可以确定部分节点的祖先关系：若先序为aX，后序Xa，则集合X中的节点均为a的后代（X内部的顺序可不同，但两节点若为兄弟，则前后顺序应一致，即左兄弟在前）
  • 线索二叉树
    • 传统的二叉链表存储进能体现一种父子关系，不能直接得到结点在遍历中的前驱或后继；且在含n个结点的二叉树中，有n+1空指针，故利用这些空指针引入线索二叉树，以加快查找结点前驱和后继的速度
    • 概念
    • 构造中序线索二叉树
      • 二叉树的线索化是将二叉链表中的空指针改为指向前驱或后继的线索。而前驱或后继的信息只有在遍历时才能得到，因此线索化的实质就是遍历一次二叉树。
      • • 带头结点的线索二叉树
    • 中序线索二叉树的遍历
      • 求中序线索二叉树中中序序列下的第一个结点
      • 求中序线索二叉树中结点p在中序序列下的后继
      • 不含头结点的中序线索二叉树的中序遍历算法
    • 先序线索二叉树和后序线索二叉树
      • 先序线索二叉树中找结点后继
        • 若有左孩子，即为其后继
        • 若无左孩子但有右孩子，则后孩子为后继
        • 否则，右链域指向后继
      • 后序线索二叉树中找结点后继
        • 若x为二叉树的根，则后继为空
        • 若x是双亲的右孩子，或是双亲的左孩子且双亲无后孩子，则后继为其双亲
        • 若x是双亲的左孩子，且双亲有右孩子，则后继为双亲右子树上按后序遍历列出的第一个结点
• 树与二叉树的应用
  • 哈夫曼树和哈夫曼编码
    • 定义
      • 带权路径长度：从树的根到任意结点的路径长度（经过的边数）与该结点上权值的乘积
      • 树的带权路径长度：树中所有叶结点的带权路径长度之和
      • 哈夫曼树：在含有n个带权叶结点的二叉树中，其中带权路径长度（WPL）最小的二叉树，也称最优二叉树
    • 哈夫曼树的构造
      •  
      • 构造过程
        • 给定n个权值分别为w1,w2,……,wn的结点，构造哈夫曼树的算法描述如下：
        • 1)将这n个结点分别作为n棵仅含一个结点的二叉树，构成森林F。
        • 2)构造一个新结点，从F中选取两棵根结点权值最小的树作为新结点的左、右子树，并且将新结点的权值置为左、右子树上根结点的权值之和。
        • 3)从F中删除刚才选出的两棵树，同时将新得到的树加入F中。
        • 4)重复步骤2)和3)，直至F中只剩下一棵树为止。
      • 特点
        • 1)每个初始结点最终都成为叶结点，且权值越小的结点到根结点的路径长度越大。
        • 2)构造过程中共新建了n-1个结点(双分支结点)，因此哈夫曼树的结点总数为2n-1.
        • 3)每次构造都选择2棵树作为新结点的孩子，因此哈夫曼树中不存在度为1的结点。
      • 哈夫曼编码
        • 可变长度编码
          • 对不同字符用不等长的二进制位表示；对低频字符赋以较长编码，对高频字符赋以较短编码
        • 前缀编码
          • 没有一个编码是另一个编码的前缀，因此解码非常简单
        • 哈夫曼编码就是利用可变长度和前缀编码设计的数据压缩编码
        • 哈夫曼树→哈夫曼编码
          • 1)将每个出现的字符当作一个独立的结点，其权值等于出现频度（次数），构造对应的哈夫曼树
          • 2)将字符的编码解释为从根至该字符的路径上边标记的序列；其中边标记为0表示”转向左孩子“，标记为1表示”转向右孩子“
  • 并查集
    • 基本思想
      • 通常用树(森林)的双亲表示作为并查集的存储结构，每个子集合以一棵树表示。所有表示子集合的树，构成表示全集合的森林，存放在双亲表示数组内。通常用数组元素的下标代表元素名，用根结点的下标代表子集合名，根结点的双亲结点为负数。
    • 操作
      • 1) Initial(S): 将集合s中的每个元素都初始化为只有-个单元素的子集合。
      • 2) Union(S, Root1, Root2): 把集合S中的子集合Root2并入子集合Root1。要求 Root1和Root2互不相交，否则不执行合并。
      • 3) Find(S,x): 查找集合s中单元素x所在的子集合，并返回该子集合的根结点。
• 树、森林
  • 树的存储结构
    • 双亲表示法
      • 采用一组连续空间来存储结点；同时在每个结点增设指示双亲位置的伪指针
      • 可以很快得到结点的双亲结点，但求结点的孩子时需遍历数组
    • 孩子表示法
      • 将每个结点的孩子节点用单链表连接起来，n个结点对应n个链表
      • 寻找子女简单，但寻找双亲需遍历n个链表
    • 孩子兄弟表示法（二叉树表示法）
      • 以二叉链表作为树的存储结构
        • 结点
          • 结点值
          • 指向结点第一个孩子的指针
          • 指向结点下一个兄弟结点的指针
      • 便于查找孩子，但查找双亲结点较为麻烦（可增设parent指针）
  • 树、森林与二叉树的转换
    • 树↔二叉树
      • 以二叉链表为媒介，对每一棵树有唯一的二叉树与之对应（反之亦然）
      • 转换规则：“左孩子右兄弟”
      • • 先根遍历序列：ABEFCDG
        • 后根遍历序列：EFBCGDA
    • 森林↔二叉树
      • 类似上述转换，先将每棵树转换为二叉树，再将第n+1棵树的根视为第n棵树根的右兄弟
      • • 先序遍历序列：ABCDEFGHI
        • 中序遍历序列：BCDAFEHIG
  • 树和森林的遍历
    • 
    • 树的遍历
      • 先根遍历
        • 先访问根节点，再依次访问每颗子树
        • 遍历序列与对应二叉树的先序序列相同
      • 后根遍历
        • 先依次访问每颗子树，再访问根节点
        • 遍历序列与对应二叉树的中序序列相同
      • 层次遍历
    • 森林的遍历
      • 先序遍历
        • 访问森林中第一棵树的根结点
        • 先序遍历第一棵树中根节点的子树森林
        • 先序遍历除去第一棵树之后剩余数的森林
      • 中序遍历
        • 中序遍历遍历森林中第一棵树的根节点的子树森林
        • 访问第一棵树的根结点
        • 中序遍历除去第一棵树之后剩余树构成的森林