树、二叉树、完全二叉树、哈夫曼树和Trie树详解

树、二叉树、完全二叉树、哈夫曼树和Trie树详解

引用

CSDN

1.

https://m.blog.csdn.net/Samuel777999111/article/details/141276606

本文详细介绍了树、二叉树、完全二叉树、哈夫曼树和Trie树等数据结构的概念、定义、性质和应用。文章内容详尽，涵盖了各种树结构的基本定义、存储方式、遍历方法以及具体应用场景，如哈夫曼编码和字符串检索等。

树的定义

一个没有固定根节点的树称为无根树。
无根树有几种等价的形式化定义：

• 有n个结点，n - 1条边的联通无向图。
• 无向无环的连通图。
• 任意两个结点之间有且只有一条简单路径的无向图。
• 任何边均为桥的连通图。
  在无根树的基础上，指定一个结点称为根，则形成一颗有根树。
• 有根树在很多时候依然以无向图表示，只是规定了结点之间的上下级关系。
• 树的存储：一般以链式前向星的方法存储树结构。
  
  适用于有根树和无根树：
• 森林：每个连通分量（连通块）都是树的图。按照定义：一棵树也是森林。
• 生成树：一个连通无向图的生成子图，同时要求是树。即是在图的边集中选择n − 1条边，将所有顶点连通。
  只适用于有根树：
• 父结点：该节点到根节点路径上的第二个结点。根节点没有父结点。
• 祖先结点：一个结点到根节点路径上，除了它本身外的所有结点。
• 子结点：如果 u 是 v 的父节点，则 v 是 u 的子结点。
• 兄弟结点：同一个父节点的多个子结点互为兄弟结点。
• 后代：子结点和子结点的后代。
• 子树：删掉与父节点相连的边后，该结点所在的子图。

二叉树定义

二叉树是一种树形结构，其特点是每个结点最多只有两个子树，二叉树递归定义如下：

1. 它或者是一棵空树不包含任何结点，或者有且仅有一个结点称为根节点。
2. 根结点至多有两个互不相交的子树，并且每个子树也是一个二叉树。
   二叉树的性质：
3. 非空二叉树第 i 层至多有2i-1个结点。
4. 高为 h 的二叉树至多有2h+1− 1个结点。
5. 对任何非空二叉树，若其叶结点个数为 n0，有两个孩子的结点个数为 n2，则n0 = n2 + 1。
   二叉树的存储：
6. 只记录父结点（父结点唯一），可获得信息较少，不适合自顶向下遍历，常用于自底向上的递推。
7. 记录左右儿子，结构体 + 指针表示。
8. 邻接表、链式前向星。
   

二叉树遍历

二叉树的遍历是指从二叉树的根结点开始，按照某种次序依次访问二叉树中所有节点，每个结点被访问且仅被访问一次。二叉树有三种常用遍历顺序，分别是前序、中序、后序遍历。

1. 前序遍历：先访问根结点，再递归前序访问左子树，最后递归前序访问右子树。
2. 中序遍历：先递归中序访问左子树，再访问根结点，最后递归中序访问右子树。
3. 后序遍历：先递归后序访问左子树，再递归后续访问右子树，最后访问根结点。
   
   层序遍历：树上 BFS，严格按照层次访问结点，可求出各个结点深度和父结点。
   已知中序遍历序列和另外一个序列可求第三个序列：
   1. 前序的第一个是 root，后序的最后一个是 root。
   2. 先确定根结点，根据中序遍历，在根左边的是左子树，在根右边的是右子树。
   3. 每一个子树都可以看作一棵新树，仍遵循上述规律，递归操作即可。

完全二叉树

完全二叉树：指一棵二叉树只有最下面两层的结点的度数可以小于 2，且最下面一层的结点都处于该层左边连续位置上。

1. 具有 n 个结点的完全二叉树深度为log2n；
2. 对于具有 n 个结点的完全二叉树，若按层次从上到下，从左到右，从 1 开始依次对每个结点编号，则编号为 x 的结点具有如下性质：
3. 如果 x = 1，则结点 x 为该完全二叉树的根结点。
4. 如果 x > 1，则结点 x 的父结点编号为**[x/2] (x ≫ 1)**。
5. 如果2x > n，则 x 无左子结点，否则 x 左子结点编号为2x。
6. 如果2x + 1 > n，则 x 无右子结点，否则 x 右子结点编号为2x + 1。

• 除最下面一层没有子结点外，其余每一层上所有结点有且都有两个子结点，即满二叉树，又称完美二叉树。

完全二叉树的数组表示法

对于 n 个结点的完全二叉树，若按层次从上到下，从左到右，从 1 开始（根结点为 1）依次对每个结点编号，并以编号作为数组下标，依次存放在一维数组中。
根据结点存储在数组中下标数值，可以获得结点在完全二叉树上的父子逻辑关系：

1. 非根结点（编号 x > 1）的父结点编号为【x/2】；
2. 结点 x 的左子编号是2x (2x ≤ n)，右子编号为2x + 1 (2x + 1 ≤ n)。

Huffman tree（最优二叉树）

树的带权路径长度：设二叉树具有 n 个带权叶结点，从根结点到各叶结点的路径长度与相应叶结点权值的乘积之和称为树的带权路径长度（WPL）。

• 设 wi 为二叉树第 i 个叶结点的权值，li 为从根结点到第 i 个叶结点的路径长度，则 WPL 计算公式如下：
  W P L = ∑ i = 1 n w i l i WPL =\sum_{i=1}^{n} wi liWPL=∑i=1n wili，其中 i 从 1 到 n。
• 右图 WPL = 2 × 2 + 3 × 2 + 4 × 2 + 7 × 2 = 32
  对于给定一组具有确定权值的叶结点，可以构造出不同的二叉树，其中 WPL 最小的二叉树称为哈夫曼树。
• 构造思想：其叶结点权值越小，离根越远，叶结点 权值越大，离根越近，此外其仅有叶结点的度为 0， 其他结点度均为 2。
  构造思想：其叶结点权值越小，离根越远；叶结点权值越大，离根越近。此外，其仅有叶结点的度为 0，其他结点度均为 2。

1. 初始化：根据给定的 n 个权值 {w1, w2, …, wn}，构造一个森林——森林内含 n 棵只有一个根节点的二叉树，记为 F = {t1, t2, …, tn}，其中二叉树 ti 只有权值为 wi 的根结点，其左右子树均为空。
2. 选取与合并：在森林 F 中选取两棵根结点权值最小的树作为左、右子树构造一棵新的二叉树，并且这棵新二叉树根结点的权值为左、右子树根结点权值之和。
3. 删除与加入：在森林 F 中删除这两棵二叉树，同时将新得到的二叉树加入森林 F 中。
4. 重复步骤 2、3，直至森林 F 只包含一棵树为止，最后所剩下的这棵二叉树便是建立的哈夫曼树。
   给每一个字符标记一个单独的代码来表示一组字符，即编码。

• 在进行二进制编码时，假设所有的代码都等长，那么表示 n 个不同的字符需要[log2n]位，称为等长编码。
• 如果每个字符的使用频率相等，那么等长编码无疑是空间效率最高的编码方法；如果字符出现的频率不同，则可以让频率高的字符采用尽可能短的编码，频率低的字符采用尽可能长的编码，来构造出一种不等长编码，从而获得更好的空间效率。
• 在设计不等长编码时，要考虑解码的唯一性，如果一组编码中任一编码都不是其他任何一个编码的前缀，那么称这组编码为前缀编码，其保证了编码被解码时的唯一性。
  设定哈夫曼树左子路径编码为 0，右子路径编码为 1，从根结点递归访问每个叶子结点，记录每个根结点到叶子结点路径上的编码，即哈夫曼编码。

1. 初始化：根据给定的 n 个权值 {w1, w2, …, wn}，构造一个森林——森林内含 n 棵只有一个根节点的二叉树，记为 F = {t1, t2, …, tn}，其中二叉树 ti 只有权值为 wi 的根结点，其左右子树均为空。
2. 选取与合并：在森林 F 中选取两棵根结点权值最小的树作为左、右子树构造一棵新的二叉树，并且这棵新二叉树根结点的权值为左、右子树根结点权值之和。
3. 删除与加入：在森林 F 中删除这两棵二叉树，同时将新得到的二叉树加入森林 F 中。
4. 重复步骤 2、3，直至森林 F 只包含一棵树为止，最后所剩下的这棵二叉树便是建立的哈夫曼树。

Trie 树（字典树、前缀树、单词查找树）

Trie 树是一种用于实现字符串快速检索的多叉树结构，用于统计，排序，和保存大量的字符串（包括但不限于字符串）。

• 核心：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较。
• Trie 的每个结点都拥有若干字符指针，指向下一位字符位置。【边是具体字符、单词就是根结点出发的路径】
  • 根结点为 1
  trie[i][c] 表示第 i 号结点，沿边 c 能走到的位置，如：
• trie[1][c] = 2
  trie[1][h] = 4
  trie[5][t] = 8
  trie[1][a] = NULL

Trie 树（字典树、前（后）缀树、单词查找树）

初始化：一棵空 Trie 仅包含一个根结点(1)，该结点字符指针均指向空 (0)。
插入：当需要插入一个字符串 S 时，令一个指针 P 起初指向根结点(p = root)，依次扫描 S 中每个字符 c：

1. 若 P 的 c 字符指针指向一个已存在的结点 Q，令 P = Q。
2. 若 P 的 c 字符指针指向空，则新建一个结点 Q，令 P 的 c 字符指针指向 Q，然后令 P = Q。

• 当 S 中字符扫描完毕时，在当前结点 P 上标记它是一个字符串的末尾。

检索：当需要检索一个字符串 S 在 Trie 中是否存在时，令一个指针起初指向根结点，然后依次扫描 S 中的每个字符 c：

1. 若 P 的 c 字符指针指向空，则说明 S 没有被插入过 Trie，结束检索。
2. 若 P 的 c 字符指针指向一个已经存在的结点 Q，令 P = Q。

• 若 S 中字符扫描完毕时，结点 P 未被标记为一个字符串末尾，则不存在。