6.1 树的定义

6.1.1 树的定义

树 (Tree) 是 n (n >= 0) 个结点的有限集。n = 0 时称为空树。
在任意一颗非空树中：

  1. 有且仅有一个称为根 (root) 的结点。

  2. 当 n > 1 时，其余结点可分为 m (m > 0) 个互不相交的有限集 T1、T2、……、Tm，其中每一个集合本身又是一棵树，并且称为根的子树 (SubTree)。

    6.1.2 树的特点

  3. n > 0 时根结点是唯一的，不可能存在多个根结点。

  4. m > 0 时，子树的个数没有限制，但它们一定是互不相交的。

    6.1.3 结点的分类

  • 结点：树的结点包含一个数据元素及若干指向其子树的分支。
  • 结点的度：结点拥有的子树的数量称为结点的度 (Degree)。
  • 叶结点：度为 0 的结点称为叶结点 (Leaf) 或终端结点。
  • 分支结点/非终端结点： 度不为 0 。
  • 内部节点：除了根结点外的分支结点。
  • 树的度：树内各节点的度中的最大值。

下图树的度为 3 。因为 D 结点的度为 3，是所有结点中度最大的。
image.png

6.1.4 结点间关系

  • Child (孩子)：结点的子树的根。
  • Parent (双亲)：A 结点的子树的根称 A 结点为双亲。
  • Sibling (兄弟)：同 Parent 的结点。
  • 祖先：从根结点到 A 结点的所经过分支上的所有结点，称为 A 结点的祖先。
  • 子孙：以 A 结点为根，其子树的所有结点均为 A 结点的子孙。

    6.1.5 其他概念

  1. 深度/高度：树中结点的最大层次。
  2. Forest (森林)：树中每棵子树的集合。

6.2 树的存储结构

6.2.1 双亲表示法

image.png

6.2.2 孩子表示法

每个节点的孩子节点都用单链表连接起来形成一个线性结构，n个节点具有n个孩子链表
image.png

6.2.3 孩子兄弟表示法

又称为二叉树表示法，本质是将树转二叉树结构。
image.png
转换前如下：
image.png
转换后如下：
image.png

6.3 二叉树的定义

6.3.1 二叉树的定义

二叉树（BinaryTree）是 n（n≥0）个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。

6.3.2 二叉树的特点

特点：

  1. 每个结点最多有两棵子树。
  2. 左右子树有顺序之分，不可任意颠倒。
  3. 仅有一棵子树也要区分左右。

二叉树五种基本形态：

  1. 空二叉树。
  2. 只有一个根结点。
  3. 根结点仅有左树。
  4. 根结点仅有右树。

  5. 根结点拥有左右树。

    6.3.3 特殊二叉树 ❗❓

  6. 斜树

定义：所有结点仅有左子树或者仅有右子树，称为左斜树、右斜树。

  1. 满二叉树
    定义：所有分支节点都存在左右子树，且叶子均在同一层。

image.png
特点：

  1. 叶子仅出现再最下层。
  2. 非叶子结点的度一定为 2 。
  3. 同深度的二叉树中，满二叉树的结点最多，椰子树也最多。
    1. 完全二叉树 ❗❓定义：对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应**时称之为完全二叉树。

image.pngimage.png
特点：

  1. 叶子节点仅出现在最下两层。
  2. 最下层的叶子一定集中在左部连续位置。
  3. 倒数第二层，如果有叶子，一定都在右部连续位置。
  4. 如果结点度为 1 ，该节点只有左孩子。
  5. 同样结点数的二叉树，完全二叉树深度最小。

    6.4 二叉树的性质

    6.4.1 二叉树性质1

    在二叉树的第 i 层上至多有 第六章 树 - 图10 个结点（i ≥ 1）。

    6.4.2 二叉树性质2

    深度为 k 的二叉树至多有 第六章 树 - 图11 个结点（k ≥ 1）。

    6.4.3 二叉树性质3

    对任何一棵二叉树 T，如果叶子结点数定义为 第六章 树 - 图12，度为 2 的结点数为 第六章 树 - 图13，则有 第六章 树 - 图14。
    image.png
    证明：
    设叶子节点为 第六章 树 - 图16，度为 1 的结点数为 第六章 树 - 图17，度为 2 的结点数为 第六章 树 - 图18。
    如上图：第六章 树 - 图19（F、G、H、I、J） 第六章 树 - 图20（E） 第六章 树 - 图21（A、B、C、D）
    已知 T 树的总结点 第六章 树 - 图22，即 第六章 树 - 图23
    已知 T 树连接线数为结点总数减去 1。 A、B、C、D 各有两条分支线，E有一条分支线。
    所以总分支线为 第六章 树 - 图24，代数表示为第六章 树 - 图25。

结合 第六章 树 - 图26 和 第六章 树 - 图27 得出：
第六章 树 - 图28
推导得出：第六章 树 - 图29

6.4.4 二叉树性质4

具有 n 个结点的完全二叉树的深度为 第六章 树 - 图30 （这里的[x]表示取整数部分）

6.4.5 二叉树性质5

如果对一棵有n个结点的完全二叉树的结点按层序编号（从第1层到最后一层，每层从左到右），则对任一结点i（1<=i<=n)，有：

  1. i = 1，i 为根结点；i > 1，则其双亲是结点 第六章 树 - 图31。
  2. 2i > n，则结点 i 无左孩子；否则其左孩子是结点 2i。
  3. 2i + 1 > n，则结点 i 无右孩子；否则其右孩子是结点 2i + 1。

image.png

6.5 二叉树的存储结构

6.5.1 顺序存储

完全二叉树：
image.png
由于二叉树的定义严格，所以顺序存储可以表现出二叉树结构
image.png
非完全二叉树将不存在的结点设置为”空”即可
为了避免空间浪费，顺序存储通常用在完全二叉树

6.5.2 链表

二叉树结点最多有两个孩子，所以设置一个数据域和两个指针域即可，称为二叉链表
image.png

6.6 遍历二叉树

6.6.1 前序遍历

leetcode 144. 二叉树的前序遍历
规则是若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树。（根左右）

  1. /**
  2.  * @method 前序遍历-二叉树
  3.  * @param {object} Tree
  4.  */
  5. function preOrderTraverse (T) {
  6.   if (T === null || T === undefined) return
  7.   console.log(T.data)
  8.   preOrderTraverse(T.leftNode)
  9.   preOrderTraverse(T.rightNode)
  10. }

6.6.2 中序遍历

leetcode 94. 二叉树的中序遍历
规则是若树为空，则空操作返回，否则从根结点开始（注意并不是先访问根结点)，中序遍历根结点的左子树，然后是访问根结点，最后中序遍历右子树。（左根右）

/**
 * @method 中遍历-二叉树
 * @param {object} Tree
 */
function inOrderTraverse(T) {
  if (T === null || T === undefined) return;
  inOrderTraverse(T.leftNode);
  console.log(T.data)
  inOrderTraverse(T.rightNode);
}

6.6.3 后序遍历

规则是若树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后是访问根结点。（左右根）

/**
 * @method 后序遍历-二叉树
 * @param {object} Tree
 */
function postOrderTraverse(T) {
  if (T === null || T === undefined) return;
  postOrderTraverse(T.leftNode);
  postOrderTraverse(T.rightNode);
  console.log(T.data)
}

6.6.4 二叉树遍历性质

  • 已知前序遍历序列和中序遍历序列，可以唯一确定一棵二叉树
  • 已知后序遍历序列和中序遍历序列，可以唯一确定一棵二叉树

leetcode 105. 从前序与中序遍历序列构造二叉树
leetcode 106. 从中序与后序遍历序列构造二叉树

6.7 二叉树的建立

image.png
现有扩展二叉树前序序列为 ["A", "B", "#", "D", "#", "#", "C", "#", "#"] ，根据该序列生成二叉树。

    let preStr = ["A", "B", "#", "D", "#", "#", "C", "#", "#"]

    function TreeNode(val, left, right) {
      this.val = (val === undefined ? 0 : val)
      this.left = (left === undefined ? null : left)
      this.right = (right === undefined ? null : right)
    }

    const newTree = new TreeNode('#') // * 建立空树

    function createBiTree(biTree) {
      if (preStr.length === 0) return // 完成前序遍历
      let val = preStr.shift() // 截取当前树根结点
      if (val === '#') return // 当前为#时，无需赋值 默认节点为null
      biTree.val = val
      if (preStr[0] !== '#') {
        biTree.left = new TreeNode('#')
      }
      createBiTree(biTree.left)

      if (preStr[0] !== '#') {
        biTree.right = new TreeNode('#')
      }
      createBiTree(biTree.right)
    }

    createBiTree(newTree)
    console.log('newTree', newTree)

leetcode 331. 验证二叉树的前序序列化

6.8 线索二叉树

定义：在二叉树的结点上加上线索的二叉树称为线索二叉树，对二叉树以某种遍历方式（如先序、中序、后序或层次等）进行遍历，使其变为线索二叉树的过程称为对二叉树进行线索化。（Threaded Binary Tree）。

为什么需要线索二叉树？
知道了“前驱”和“后继”信息，就可以把二叉树看作一个链表结构，从而可以像遍历链表那样来遍历二叉树，进而提高效率。
image.png

6.8.1 二叉树线索化

线索化的过程就是在遍历的过程

/**
 * LTag/RTag: 0 表示指向孩子, 1 表示指向 前驱/后继
 */
/**
 * @method 二叉树线索化-中序遍历
 * @param {object} root
 */

let pre = null;

function inOrderThread(root) {
  // * root == null 无法线索化
  if (root === null) return;
  // * 1.左子树线索化
  inOrderThread(root.left);
  // * 2.当前结点线索化
  if (root.left === null) {
    // * 若当前左子树为空
    // * 设置类型为1
    root.LTag = 1;
    // * 左指针指向前驱结点
    root.left = pre;
  }
  if (pre && pre.right === null) {
    // * 若前驱右子树为空
    // * 设置类型为1
    pre.RTag = 1;
    // * 前驱结点右指针指向当前结点
    pre.right = root;
  }

  // * 设置当前结点为下次的前驱结点
  pre = root;

  inOrderThread(root.right);
}

6.9 树、森林与二叉树的转换

6.9.1 树转二叉树

  1. 加线。在所有兄弟结点之间加一条连线。
  2. 去线。树中每个结点，只保留长子的连线，删除其他孩子与结点的连线。
  3. 层级调整。整个树顺时针旋转一定角度。结点第一个孩子是二叉树的左孩子，兄弟转换的孩子为结点右孩子。

image.png

6.9.2 森林转二叉树

  1. 每棵树转二叉树。
  2. 第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子，用线连接起来。当所有的二叉树连接起来后就得到了由森林转换来的二叉树。

image.png

6.9.3 二叉树转树

  1. 加线。若某结点的左孩子结点存在，则将这个左孩子的 n 个右孩子都作为此结点的孩子。该结点与 n 个右孩子连线。
  2. 去线。删除原二叉树中所有结点与右孩子结点的连线。
  3. 层次调整。

image.png

6.9.4 二叉树转森林

二叉树根结点有右孩子时能转为森林，无右孩子转为树。

  1. 从根结点开始，若右孩子存在，则把与右孩子结点的连线删除，再查看分离后的二叉树，若右孩子存在，则连线删除……，直到所有右孩子连线都删除为止，得到分离的二叉树。
  2. 每棵分离后的二叉树转树即可。

image.png

6.9.5 树与森林的遍历

当以二叉链表作树的存储结构时，树的先根遍历和后根遍历完全可以借用二叉树的前序遍历和中序遍历的算法来实现。

6.10 赫夫曼树及其应用

6.10.1 赫夫曼树

术语定义：

  • 权值：是数学领域中的词，指加权平均数中的每个数的频数。（哈夫曼树中的权值可以理解为：权值大表明出现概率大！）
  • 路径长度：从树中一个结点到另一个结点之间的分支构成两个结点之间的路径，路径上的分支数目称做路径长度。
  • 树的路径长度：从树根到每一结点的路径长度之和。

赫夫曼树定义：
给定 N 个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为赫夫曼树(Huffman Tree)。

赫夫曼树算法描述：
image.png

6.10.2 赫夫曼编码

定义：
image.png
例子：
现有 “BADCADFEED” 字符串需要传输，该段字符串有六个字母 ABCDEF，我们采用二进制数据来表示他们，如下
image.png
通过上表的二进制字符编码后的数据为 “001000011010000011101100100011”，服务端可通过 3 位字符切割来译码。
现在假设六个字母的频率为 A 27, B 8，C 15，D 15，E 30，F 5，可根据赫夫曼树进行规划。
image.png
根据权值构建出赫夫曼树，再将左分支权值改为 0 ，右分支改为 1 ，从根到叶子结点的路径来编码，得到如下：
image.png

  • 原二进制编码： 001000011010000011101100100011（30个字符）
  • 赫夫曼规划的二进制编码：1001010010101001000111100（25个字符）