跳至正文
wyaaaattwhoAI RESEARCH & ENGINEERING
← 返回首页

树和二叉树

树和森林的概念基本术语二叉树 (Binary Tree)概念性质二叉树的遍历线索化二叉树 树与森林树的遍历堆Huffman树

树和森林的概念

基本术语

  • 有根树：一棵有根树 T，简称为树，它是n (n≥0) 个结点的有限集合。当n = 0时，T 称为空树；否则，T 是非空树，记作
  • r是一个特定的称为根(root)的结点，它只有直接后继，但没有直接前驱；
  • 根以外的其他结点划分为 n 个互不相交的有限集合，每个集合又是一棵树，并且称之为根的子树。
  • 子女结点：若结点的子树非空，结点子树的根即为该结点的子女。
  • 父结点：若结点有子女，该结点是子女双亲。
  • 兄弟结点：同一结点的子女互称为兄弟。
  • （出）度：结点的子女个数即为该结点的度；树中各个结点的度的最大值称为树的度。
  • 叶结点：度为0的结点即为叶结点，亦称为终端结点。
  • 分支结点：度不为0的结点即为分支结点，亦称为非叶结点。
  • 祖先结点：某结点到根结点的路径上的各个结点都是该结点的祖先。
  • 子孙结点：某结点的所有下属结点，都是该结点的子孙。
  • 结点的层次：规定根结点在第一层，其子女结点的层次等于它的层次加一。以下类推。
  • 深度：结点的深度即为结点的层次；离根最远结点的层次即为树的深度。
  • 高度：规定叶结点的高度为1，其父结点的高度等于它的高度加一。
  • 树的高度：等于根结点的高度，即根结点所有子女高度的最大值加一。
  • 有序树：树中结点的各棵子树 T0, T1, …是有次序的，即为有序树。
  • 无序树：树中结点的各棵子树之间的次序是不重要的，可以互相交换位置。
  • 森林：森林是m棵树的集合。
代码

二叉树 (Binary Tree)

概念

一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。——一个递归的定义。

性质

  1. 若二叉树结点的层次从 1 开始, 则在二叉树的第 i 层最多有 个结点。( i≥1)
  1. 深度为 k 的二叉树最少有 k 个结点，最多有 个结点。（ k≥1 )
  1. 对任何一棵二叉树，如果其叶结点有 个, （出）度为 2 的非叶结点有 个, 则有
      2. 接下来先引入定义：
      • 满二叉树 (Full Binary Tree) 若有k层，刚好有个节点。
      • 完全二叉树 (Complete Binary Tree)
          • 若设二叉树的深度为 k，则共有 k 层。除第k 层外，其它各层 () 的结点数都达到最大个数，第k层从右向左连续缺若干结点，这就是完全二叉树。
  1. 具有 n (n≥0) 个结点的完全二叉树的深度为（向上取整）
  1. 如将一棵有n个结点的完全二叉树自顶向下，同一层自左向右连续给结点编号1,2, …, n，则有以下关系：
    1. i = 1，没有父节点
    2. 如果 i > 1，则父节点为（向下取整）
    3. 如果2i或者2i+1的节点存在，则分别为i节点的左子女和右子女
    4. 如果 i 是基奇数，则 i -1 是他的左兄弟；如果 i 是偶数，则 i+1 （存在的话）是他的右兄弟
  1. 对于完全二叉树，其节点数 n 和叶子节点数 满足
代码（抽象数据结构）
  • 二叉树的表示
    • 顺序储存表示
        • 按照前面的说法，可以通过纯粹的数学关系得到谁是谁的子女和兄弟和父母以及所在层数，所以可以用数组。
    • 链表表示
      • 二叉树结点定义：每个结点有3个数据成员，data域存储结点数据，leftChild和rightChild分别存放指向左子女和右子女的指针
      • 每个结点增加一个指向双亲的指针parent，使得查找双亲也很方便。
      • 类似的，也可以用数组静态的模拟链表的实现
        • 代码

二叉树的遍历

  • 二叉树的遍历就是按某种次序访问树中的结点，要求每个结点访问一次且仅访问一次。
  • 设访问根结点记作V，遍历根的左子树记作 L，遍历根的右子树记作 R
  • 可能的顺序有
      1. 前序 VLR；镜像VRL
      1. 中序 LVR；镜像RVL
      1. 后序 LRV；镜像RLV
  • 中序遍历
    • 若二叉树为空，则空操作；
    • 否则中序遍历左子树 (L)；访问根结点 (V)；中序遍历右子树 (R)
  • 前序遍历
    • 若二叉树为空，则空操作；
    • 否则访问根结点 (V)；前序遍历左子树 (L)；前序遍历右子树(R)
  • 后序遍历
    • 若二叉树为空，则空操作；
    • 否则后序遍历左子树 (L)；后序遍历右子树(R)；访问根结点 (V)
📌
每种遍历分别对应了中缀前缀后缀表达式，把操作符作为父节点，左操作数当左子女，右操作数当右子女。
  • 利用二叉树前序遍历建立二叉树
    • 以递归方式建立二叉树。
    • 输入结点值的顺序必须对应二叉树结点前序遍历的顺序。并约定以输入序列中不可能出现的值作为空结点的值以结束递归, 此值在RefValue中。例如用“@”或用“1”表示字符序列或正整数序列空结点。
      • notion image
  • 除了递归的遍历之外，类似之前，我们可以用栈来实现
     
    • 层次序遍历二叉树的算法
      • 层次序遍历二叉树就是从根结点开始，按层次逐层遍历.
      • 这种遍历需要使用一个先进先出的队列

    线索化二叉树

    • 线索化二叉树
      • 通过二叉树的遍历，可将二叉树中所有结点的数据排列在一个线性序列中，可以找到某数据在这种排列下它的前驱和后继。
      • 希望不必每次都通过遍历找出这样的线性序列。只要事先做预处理，将某种遍历顺序下的前驱、后继关系记在树的存储结构中，以后就可以高效地找出某结点的前驱、后继。
    • 实现
      • 增加 Pred 指针和 Succ 指针的二叉树
        • 加上两个指针，一个指向前序节点，一个指向后序，等于是一个树加上二叉树。
        • 问题
            • 空间开销大
            对于原来的二叉链表结构，一棵n个结点的二叉树共有2n个指针域，而非空的指针域（边的个数）为n-1个，因此，仍有n+1个指针域没有利用起来。
      • 增加左右线索标志的二叉树
        • 改造树结点，将 pred 指针和 succ 指针压缩到 leftChild 和 rightChild 的空闲指针中，并增设两个标志 ltag 和 rtag，指明指针是指示子女还是前驱／后继。后者称为线索。
        • ltag (或rtag) =0，表示相应指针指示左子女（或右子女结点）；当ltag (或rtag) = 1, 表示相应指针为前驱（或后继）线索。
          • notion image
    • 线索树里有一些特别的实现
      • 通过中序遍历建立中序线索化二叉树
        • 如果要在中序线索树中寻找前驱和后继：
          • 寻找当前结点在中序下的后继
              • if (current->rtag ==1)
              后继为current->rightChild
              else //current->rtag == 0
              后继为当前结点右子树的中序下的第一个结点
          • 寻找当前结点在中序下的前驱
              • if (current->ltag == 1)
              前驱为current->leftChild
              else //current->ltag == 0
              前驱为当前结点左子树中序下的最后一个结点
        • 如果要在前序线索化里面找
            • notion image
        • 如果要在后序线索化里面找
            • notion image
      📌
      线索树应用：已知在中序线索树中的某个结点q，找树中q的父亲结点。（不知道根结点指针）
      1. 检查左前驱：首先判断 q 是否有中序前驱（即 q->leftThread 为真），如果有前驱，令 p = q->left。
      • 如果 p->right 为 q，则说明 p 是 q 的父节点（因为 p->right 指向 q 表示 q 是 p 的右孩子）。
      • 否则，q 是其前驱的右子树，继续寻找。
      2. 检查右后继：若 q 没有前驱或无法通过前驱找到父节点，则检查 q 的后继线索（即 q->rightThread 为真），找到 p = q->right。
      • 如果 p->left 为 q，则说明 p 是 q 的父节点（因为 p->left 指向 q 表示 q 是 p 的左孩子）。
      • 否则继续搜索。
      3. 终止条件：如果经过前驱和后继的检查都没有找到父节点，则 q 为根节点。

      树与森林

      树的存储表示
      • 广义表表示
          • notion image
      • 双亲表示
          • 树中结点的存放顺序一般不做特殊要求，但为了操作实现的方便，有时也会规定结点的存放顺序。例如，可以规定按树的前序次序存放树中的各个结点，或规定按树的层次次序安排所有结点。
      • 子女链表表示
          • 无序树情形链表中各结点顺序任意，有序树必须自左向右链接各个子女结点。
          notion image
      • 子女指针表示
        • 一个合理的想法是在结点中存放指向每一个子女结点的指针。但由于各个结点的子女数不同，每个结点设置数目不等的指针，将很难管理。
        • 为此，设置等长的结点，每个结点包含的指针个数相等，等于树的度（degree）。
        • 这保证结点有足够的指针指向它的所有子女结点。但可能产生很多空闲指针，造成存储浪费。
      • 子女-兄弟表示
        • 构造节点为
          • firstChild 指向该结点的第一个子女结点。无序树时，可任意指定一个结点为第一个子女。
          • nextSibling指向该结点的下一个兄弟。任一结点在存储时总是有顺序的。
          • 若想找某结点的所有子女，可先找firstChild,再反复用 nextSibling 沿链扫描。
            • 代码

        树的遍历

        • 深度优先遍历
          • 先根次序遍历
          • 后根次序遍历
        • 广度优先遍历
         
        • 先根次序遍历
          • 当树非空时
            • 访问根结点
            • 依次先根遍历根的各棵子树
          • 树先根遍历ABEFCDG
          • 对应二叉树前序遍历ABEFCDG
          • 树的先根遍历结果与其对应二叉树表示的前序遍历结果相同
          • 树的先根遍历可以借助对应二叉树的前序遍历算法实现
            •  
        notion image
        • 树的后根次序遍历
          • 当树非空时
            • 依次后根遍历根的各棵子树
            • 访问根结点
          • 树后根遍历EFBCGDA
          • 对应二叉树中序遍历EFBCGDA
          • 树的后根遍历结果与其对应二叉树表示的中序遍历结果相同
          • 树的后根遍历可以借助对应二叉树的中序遍历算法实现
            •  
        notion image
        • 广度优先（层次次序）遍历
          • 按广度优先次序遍历树的结果ABCDEFG
          • 遍历算法用到一个队列。
          • 森林和二叉树可以相互转化
            • 将一般树化为二叉树表示就是用树的子女兄弟表示来存储树的结构。
            • 森林与二叉树表示的转换可以借助树的二叉树表示来实现。
                • notion image
            • 森林转化成二叉树的规则
              • 若 为空，即 ，则对应的二叉树 为空树。
              • 若 不空，则
                • 二叉树 B 的根是 F 第一棵树 T1 的根；
                • 其左子树为，其中， 是 的根的子树；
                • 其右子树为 ，其中， 是除 外其它树构成的森林。
            • 二叉树转换为森林的规则
              • F 中第一棵树 的根为 B 的根；
              • 的根的子树森林 是由 B 的根的左子树 LB 转换而来；
              • F 中除了 之外其余的树组成的森林 是由 B 的根的右子树 RB转换而成的森林。

          堆

          • 堆的定义：有序的二叉树，注意，只能保证根结点是最大的或者最小的。
          notion image
          • 由于堆存储在下标从 0 开始计数的一维数组中，因此在堆中给定下标为 i 的结点时
            • 如果 i = 0，结点 i 是根结点，无双亲；否则结点 i 的父结点为结点 (i-1)/2；
            • 如果 2i+1＞n-1，则结点 i 无左子女；否则结点 i 的左子女为结点 2i+1；
            • 如果 2i+2＞n-1，则结点 i 无右子女；否则结点 i 的右子女为结点 2i+2。
              • 最小堆代码

          Huffman树

          • Path Length：两个结点之间的路径长度 PL 是连接两结点的路径上的分支数。
            • 树的外部路径长度EPL是各叶结点（外结点）到根结点的路径长度之和 。
            • 树的内部路径长度IPL是各非叶结点（内结点）到根结点的路径长度之和 。
            • 树的路径长度 PL = EPL + IPL。
              • notion image
            • 显然，n 个结点的二叉树的路径长度不小于下述数列前 n 项的和，即
                • 完全二叉树满足这个要求。
          • 带权路径长度 (Weighted Path Length, WPL)
            • 在很多应用问题中为树的叶结点赋予一个权值，用于表示出现频度、概率值等。因此，在问题处理中把叶结点定义得不同于非叶结点，把叶结点看成“外结点”，非叶结点看成“内结点”。这样的二叉树称为相应权值的扩充二叉树。
            • 扩充二叉树中只有度为 2 的内结点和度为 0 的外结点。根据二叉树的性质，有 n 个外结点就有 n-1 个内结点，总结点数为2n-1。
            • 若一棵扩充二叉树有 n 个外结点，第 i 个外结点的权值为，它到根的路径长度为，则该外结点到根的带权路径长度为。
            • 扩充二叉树的带权路径长度定义为树的各外结点到根的带权路径长度之和。
            • 对于同样一组权值，如果放在外结点上，组织方式不同，带权路径长度也不同。
          • 带权路径长度达到最小的扩充二叉树即为Huffman树。在Huffman树中，权值大的结点离根最近。
          • Huffman树的构造算法
              1. 给定 n 个权值，构造 具有 n 棵扩充二叉树的森林 ，其中每棵扩充二叉树 只有一个带权值 的根结点, 其左、右子树均为空
              1. 重复以下步骤, 直到 F 中仅剩一棵树为止：
                1. 在 F 中选取两棵根结点的权值最小的扩充二叉树, 做为左、右子树构造一棵新的二叉树。
                2. 置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。
                3. 在 F 中删去这两棵二叉树。把新的二叉树加入 F。
              notion image
              Huffman代码
          • Huffman编码
            • 主要用途是实现数据压缩。设给出一段报文：
                • CAST CAST SAT AT A TASA，字符集合是 { C, A, S, T }，各个字符出现的频度（次数）是 W＝{ 2, 7, 4, 5 }。 若给每个字符以等长编码（2位二进制足够），A : 00 T : 10 C : 01 S : 11，则总编码长度为 ( 2+7+4+5 ) * 2 = 36。 能否减少总编码长度，使得发出同样报文，可以用最少的二进制代码？
            • 若按各个字符出现的概率不同而给予不等长编码，可望减少总编码长度。
            • 各字符出现概率为{ 2/18, 7/18, 4/18, 5/18 },化整为 { 2, 7, 4, 5 }。以它们为各叶结点上的权值, 建立Huffman树。左分支赋 0，右分支赋 1，得Huffman编码(变长编码)。 A : 0 T : 10 C : 110 S : 111
            • 它的总编码长度：71+52+( 2+4 )*3 = 35。比等长编码的情形要短。总编码长度正好等于Huffman树的带权路径长度WPL。
            • Huffman编码是一种前缀编码，即任一个二进制编码不是其他二进制编码的前缀。解码时不会混淆。