⑤树与二叉树

24自用408数据结构，树是n个结点的有限集(n≥0)，树的高度＝树的的层数＝树的深度，结点数＝边数+1＝度数之和+1。

树与二叉树

• 树的基本概念
  • 定义
    • n个结点的有限集(n≥0)
    • 特点
      • 递归性
      • 分层性
      • n个结点有n-1条边
  • 基本术语
    • 树的高度＝树的的层数＝树的深度
      • 结点的深度
        • 从根节点开始自顶向下逐层累加
      • 结点的高度
        • 从叶子结点自底向上逐层累加
    • 孩子个数为结点的度，最大度数称为树的度
    • 度为0的结点称为叶子结点(终端结点)
    • 有序树
      • 树中的各子树是从左到右有次序的，不能交换。否则称为无序树
    • 路径
      • 两结点之间经过的结点序列，路径长度为经过的边的数量(经过的结点树加1)
      • 路径是自顶向下的，同一双亲的孩子无路径
  • 树的性质
    • 结点数＝边数+1＝度数之和+1
    • 度为m和m叉树
      • 高度为h
        • 度为m
          • 至少有h+m-1个结点
          • 度为m的树第i层上至多有m'(i-1)个结点(i≥1)
          • 至少有一个结点的度为m
          • 非空
        • m叉树
          • 至少有h个结点
          • 
          • 允许所有结点的度都小于m
          • 可以为空树
    • 具有n个结点的m叉树的最小高度为
      • 
• 二叉树的概念
  • 定义
    • 每个结点至多只有两棵子树，左右顺序不能颠倒
  • 二叉树的性质
    • 非空二叉树的叶子结点数为
      • 度为2的结点数+1
        • n0＝n2+1
    • 非空二叉树第K层上至多有
      • 
    • 高为h的二叉树至多有
      • 
    • 具有n个结点的完全二叉树的高度为
      • 
    • 对于完全二叉树
      • 若有2k(偶数)个结点，则
        • n1＝1，n0＝k，n2＝k-1
      • 若有2k-1(奇数)个结点，则
        • n1＝0，n0＝k，n2＝k-1
  • 二叉树的存储结构
    • 顺序存储
      • 用一组连续的存储单元自上而下，自左至右存储完全二叉树
      • 适用于满二叉树和完全二叉树
      • 对于一般二叉树，需要添加空结点来对照完全二叉树，浪费空间
    • 链式存储
      • 左指针域lchild 数据域data 右指针域rchild
      • n个结点
        • 指针个数
          • 2n
        • 有效指针
          • n-1
        • 空链域
          • n+1
      • 如果经常搜索父结点，可以使用三叉链表
        • 左右孩子指针+父结点指针
  • 特殊的二叉树
    • 满二叉树
      • 一棵高度为h，且含有2'h-1个结点的二叉树称为满二叉树
      • 不存在度为1的结点
    • 完全二叉树
      • 高度为h、有n个结点的二叉树，当且仅当其每个结点都与高度为h的满二叉树中编号为1~n的结点一一对应时，称为完全二叉树
      • 特点
        • i≤(n/2向下取整)，则结点i为分支结点，否则为叶子结点
        • 叶子结点只可能在最大两层出现，且对于最大层来说，叶子结点依次排列在该层最左边的位置
        • 若有度为1的点，有且仅有一个，且只有左孩子
        • 按层编号，一旦出现i结点只有左孩子或者为叶子结点，则大于i的结点都为叶子结点
        • 若n为奇数，每个分支结点都有左右孩子；若n为偶数，则编号最大的分支结点(编号为n/2)只有左孩子，其余分支结点都有左右孩子
    • 二叉排序树
      • 左子树上所有结点的关键字均小于根结点的关键字；右子树所有的结点的关键字均大于根结点
      • 左子树和右子树又是一棵二叉排序树
    • 平衡二叉树
      • 树上任一结点的左子树和右子树的深度之差不超过1
  • 对于编号为i的结点 完全二叉树和满二叉树
    • 双亲
      • 
    • 左孩子
      • 2i
    • 右孩子
      • 2i+1
    • 结点i所在层次
      • 
• 二叉树的遍历和线索二叉树
  • 二叉树的遍历
    • 按某条搜索路径访问树中每个结点，使得每个结点都被访问一次，而且仅被访问一次
    • 先序遍历(先根遍历)
      • Preorder
      • 前缀表达式
      • 递归算法
        • visit(T) Preorder(T-＞lchild) Preorder(T-＞rchild)
      • 非递归算法
        • 1| 沿着根的左孩子，依次访问，直至左孩子为空
        • 2| 若右兄弟不空，将右兄弟转执行①；否则执行回溯至父结点执行②
    • 中序遍历(中根遍历)
      • Inorder
      • 中缀表达式
      • 递归算法
        • Inorder(T-＞lchild) visit(T) Inorder(T-＞rchild)
      • 非递归算法
    • 后序遍历(后根遍历)
      • Postorder
      • 后缀表达式
      • 递归算法
        • Postorder(T-＞lchild) Postorder(T-＞rchild) visit(T)
      • 非递归算法
      • 应用
        • 访问一个结点p时，栈中结点恰好是p结点的所有祖先，从栈底到栈顶结点再加上p结点，刚好构成从根结点到p结点的一条路径
        • 求根到某结点的路径，求两个结点的最近公共祖先
    • 层次遍历
      • 使用队列
      • 步骤
        • 1| 根结点入队，然后出队，并访问出队结点
        • 2| 若有左子树，左子树根结点入队；若有右子树，右子树根结点入队，重复①②
    • 遍历序列构造二叉树
      • 中序序列
        • +先序序列
        • +后序序列
        • +层序序列
  • 线索二叉树
    • 基本概念
      • 利用传统的二叉链表的n+1个空指针
      • 目的
        • 加快查找结点前驱和后继的速度
      • 标志域
        • ltag
          • ltag＝0
            • lchild指向左孩子
          • itag＝1
            • lchild指向前驱
        • rtag
          • rtag＝0
            • lchild指向右孩子
          • rtag＝1
            • lchild指向后继
    • 中序线索二叉树的构造
      • 使用中序遍历的顺序构造二叉树
      • 处理遍历的最后的一个结点需要将其rchild置空
      • 可增设一个头结点，形成一个双向链表
    • 中序线索二叉树的遍历
      • 若结点右标志为′1′，则右链为线索，指示其后继， 否则遍历右子树中第一个访问的结点(右子树中最左下的结点)为后继
      • 第一个结点为最左下结点，不一定为叶结点
      • 最后一个结点为最右下结点，为叶子结点
      • 先序和后序类似
        • 先序找后继
          • 若有左孩子，左孩子即为后继；若无左有有，则右孩子为；若为叶子结点，则右链域直接指示了后继
        • 后序找后继
          • 根结点无后继
          • 若结点为双亲的右孩子，或者是双亲的左孩子且双亲无右孩子，则后继为双亲
          • 若结点为双亲的左孩子，若有右兄弟，后继为右兄弟子树的第一个后序遍历出的结点
          • 后序有时无法找到后继，需采用三叉链表，先找到双亲
            • 后序线索二叉树仍需栈递归
• 树、森林
  • 树的存储结构
    • 画图
    • 双亲表示法
      • 采用一组连续空间来存储每个结点，同时在每个结点中增设一个伪指针，指示双亲结点在数组中的位置
      • 根结点下标为0，伪指针域为-1
      • 优缺点
        • 优：可以很快找到双亲结点
        • 缺：找孩子结点时需要遍历整个结构
    • 孩子表示法
      • 将每个结点的孩子结点都用单链表链接起来形成一个线性结构
      • n个结点，n个链表
      • 优缺点
        • 寻找子女简单
        • 寻找双亲的操作需要遍历n个结点中孩子链表指针域所指向的n个孩子链表
    • 孩子兄弟法(二叉树法) 左孩子右兄弟
      • 以二叉树链表作为树的存储结构。三个部分内容：结点值、指向结点第一个孩子结点的指针，及指向结点下一个兄弟结点的指针(沿此域可以找到结点的所有兄弟结点)
      • 优缺点
        • 实现树转换为二叉树的操作，易于找结点的孩子
        • 从当前结点查找其双亲结点比较麻烦
        • 若设置一个指针域指向双亲结点，那么查找双亲结点也很方便
  • 树、森林与二叉树的转换
    • 树转换为二叉树规则
      • 左孩子右兄弟法
        • 每个结点的左指针指向它的第一个孩子，右指针指向它在树中相邻的右兄弟
    • 森林转换为二叉树
      • 与树相似，先把每一个树转为为二叉树，再把每棵树的根结点当作兄弟连接
    • 二叉树转为森林
      • 二叉树的根及左子树为第一棵树，将其断开，二叉树的右子树又可以视为一个新的二叉树，继续重复断开，直至没有右子树为止
      • 二叉树转为森林是唯一的
    • 树和森林的遍历
      • 先根遍历
        • 与先序序列相同
      • 后根遍历
        • 与中序序列相同
• 树与二叉树的应用
  • 哈夫曼树和哈夫曼编码
    • 哈夫曼树定义
      • 带权路径长度(WPL)最小的二叉树称为哈夫曼树，也称最优二叉树
      • 带权路径长度：从树根到任意结点的路径长度(经过的边数)与该结点上权值的乘积。
    • 哈夫曼树的构造
      • 步骤
        • 
      • 特点
        • 1| 每个初始结点最后都是叶结点
        • 2| 权值越小的结点到根结点的路径长度越大
        • 3| 构造过程共新建立了n-1个结点，且新结点都是双分支结点，结点总数为2n-1
        • 4| 不存在度为1的结点
        • 5| 哈夫曼树不唯一
    • 哈夫曼编码
      • 一种被广泛应用而且非常有效的数据压缩编码
      • 数据编码方式
        • 固定长度编码
        • 可变长度编码
          • 可变长子网划分
          • 允许对不同字符用不等长的二进制为表示
          • 可以减少数据存储空间，起到数据压缩的作用
        • 可变比固定好
      • 前缀编码
        • 没有一个编码是另一个编码的前缀
      • 
        • 向左为0，还是向右为1，不固定
        • 哈夫曼树不唯一，但是WPL是唯一的
  • 并查集
    • 三要素
      • 逻辑结构
        • 元素之间为“集合”关系
      • 基本操作
        • 初始化
          • 初始化并查集
        • Find(S[]，x)：查，查找一个元素
        • Union(s[]，Root1，Root2)：并，将Root2并入Root1
      • 存储结构
        • 使用森林的双亲表示法存储，顺序存储，每个组织为一棵树
    • 优化
      • 优化并操作
        • 使用根的绝对值表示一棵的结点总数
        • 将小树合并至大树
          • 树高
            • 不超过(log2n向下取整)+1
          • 查操作时间复杂度
            • O(log2n)
      • 优化查操作
        • “压缩路径”策略，每次find操作先找到x所属根结点，再将查找路径上的所有结点都直接挂在根结点下面
        • 查并：时间复杂度O(α(n))
•