6.9 根树及其应用

第六章图论6.9根树及其应用RootedTreesandTheirApplications目录CONTENTS016.9.1根树的概念•根树的定义与基本结构

•树中的家族关系（父/子/祖先/后代）

•m叉树的定义及其重要性质026.9.2最优树•带权二叉树的定义

•树的权与带权路径长度

•哈夫曼算法（HuffmanAlgorithm）详解036.9.3前缀码•前缀码的定义与判定条件

•前缀码与二叉树的一一对应关系

•前缀码在通信与数据压缩中的应用6.9.1根树的概念定义6.40：有向树(DirectedTree)如果一个有向图在不考虑边的方向时是一棵树，称该有向图为有向树。注：这是一个基础定义，根树是在此基础上进一步约束的特殊有向树。定义6.41：根树(RootedTree)一棵有向树如果恰有一个结点的入度为0，其余所有结点的入度都为1，称它为根树。●根(Root)：唯一的、入度为0的结点。●叶(Leaf)：出度为0的结点，即树的“末梢”。●分枝点(BranchPoint)：出度不为0的结点（根也属于分枝点）。●层数与树高：从根到某结点的通路长度为该点层数；所有结点层数的最大值为树高。根树的图示与家族关系01/图示习惯习惯上使用“倒置法”来画根树，即把根(Root)画在最上方，叶(Leaf)画在下方，所有有向边的方向均隐含指向下方，形成一种自上而下的层级结构。02/家族关系术语父子关系(Parent&Child)若存在有向边<a,b>，则称节点a是b的“父亲”，节点b是a的“儿子”。兄弟关系(Siblings)若两个节点拥有同一个“父亲”节点，则它们互为“兄弟”。祖先与后裔(Ancestor&Descendant)若从节点a到节点d存在通路，则a是d的“祖先”，d是a的“后裔”。子树与m叉树定义6.43：子树(Subtree)设a是根树T的分枝点，由结点a及其所有后裔（后代）构成的子图，被称为根树T的以a为根的子树。子树本质上也是一棵根树。定义6.45：m叉树(m-aryTree)m叉树：若根树中每个结点的出度（儿子数量）的最大值为m，则称该树为m叉树。完全m叉树：每个结点的出度均为m或0。即所有内部节点都有m个儿子，或为叶节点。正则m叉树

所有树叶（叶节点）都位于同一层，树的高度是一致的。二叉树(BinaryTree)

当m=2时的特例。计算机科学中最基础、最常用的数据结构。定理6.33：完全m叉树的关系定理内容设有一棵完全m叉树，其中：•树叶数=t•分枝点数=i(m-1)i=t-1证明思路1.计算边数：每个分枝点发出m条边，总边数为m×i。2.计算总节点数：所有节点=树叶+分枝点=t+i。3.利用树的基本性质：边数=总节点数-1。m·i=(t+i)-1⇒

(m-1)i=t-1推论(完全二叉树)当m=2时，代入公式可得：i=t-1在完全二叉树中，分枝点的数量比树叶的数量少1例题6.31：电源插座问题问题描述设有28盏电灯，拟公用一个电源插座，问至少需要多少个具有四孔的电源插座？解题思路：利用完全m叉树性质•设定：把灯看作树的树叶(t)，插座看作分枝点(i)，每个插座有4个插孔即出度(m=4)。•定理公式：分枝点的出度和等于总边数，即(m-1)×i=t-1•代入计算：(4-1)i=28-1→3i=27→i=9结论：共需要9个四孔插座提示：物理模型与完全4叉树的对应关系

一个插座的4个孔对应树的一个节点延伸出的4条边例题6.32：计算机加法指令问题问题描述设有一台计算机，它有一条加法指令，每次可计算3个数的和。如果要计算9个数的和，请问至少要执行几次加法指令？解题思路(完全3叉树)•9个数字作为树的树叶(t=9)，每次加法运算作为树的分枝点(m=3)。

•依据定理公式：(m-1)i=t-1，代入得：2i=8

•计算结果：i=4。结论：至少需要执行4次加法指令。图：计算机CPU芯片的算术逻辑单元(ALU)是执行加法运算的核心部件6.9.2最优树带权二叉树定义6.47：一棵二叉树T，每一片树叶都带权，称该树为带权二叉树。它是计算“树的权”和寻找“最优树”的基础结构。树的权(W(T))定义6.48：在带权w1，w2，w3，…，wt的二叉树中，若带权为wi的树叶，其通路长度为L(wi)，则树的权定义为所有叶子节点“权值”与“路径长度”乘积之和。

W(T)=∑wᵢ·L(wᵢ)（i从1到t）最优树(Huffman树)在所有带权二叉树中，W(T)最小的那棵树，称为最优树。它是一种带权路径长度最短的树，在数据压缩、编码优化等领域有重要应用。哈夫曼算法(Huffman'sAlgorithm)核心思想：贪心策略下的全局最优一种基于“贪心”策略的算法。通过在每一步骤中，始终选择并合并当前权值最小的两棵子树，最终能够确保构建出的树在整体上拥有最小的带权路径长度，即得到全局最优的哈夫曼树。01找出并合并最小值在当前的所有权值节点中，找出两个权值最小的节点，将它们合并，生成一个新的父节点，其权值等于这两个子节点权值之和。02重复合并过程将合并后的新节点放回权值集合中，重复第一步操作，持续合并新的最小权值节点对。这一过程一直持续到集合中只剩下一个权值为止。03回溯构建最优树利用整个合并过程中记录的父子关系进行回溯，即可还原出一棵完整的二叉树，这就是满足最小带权路径长度要求的哈夫曼树。例题6.33：构造最优树▍问题描述给定一组叶权：5,2,4,7,5,3,4。请利用哈夫曼算法构造一棵最优二叉树，并计算该树的带权路径长度WPL(W(T))。▍哈夫曼算法合并步骤1.排序：将叶权从小到大排列→2,3,4,4,5,5,72.迭代合并：①2+3=5|②4+4=8|③5+5=10|④5+7=12|⑤8+10=18|⑥18+12=30每次选取当前权值最小的两棵树进行合并，直至形成一棵完整的树。树权计算结果(WPL):W(T)=2×3+3×3+4×3+4×3+5×3+5×2+7×2=83图6.33：构造完成的哈夫曼最优树（注：图中节点上方数字为合并生成的新权值）6.9.3前缀码核心问题：高效且无歧义的编码▌背景Context计算机中信息通常由0和1的二进制序列表示。若采用固定长度的等长编码，在字符出现频率差异较大的场景下，编码的整体效率往往较低，浪费传输与存储资源。▌挑战Challenge若简单使用不等长编码，极易导致解码时的二义性。例如：若00表示A，001表示B，当接收端收到“001”时，无法判断是“A(00)+1”还是直接是“B(001)”。▌解决方案Solution引入一种特殊的编码规则——前缀码(PrefixCodes)，从根本上解决歧义问题。定义6.49：前缀码给定一个序列的集合，若没有一个序列是另一个序列的前缀，该序列集合称为前缀码(PrefixCodes)。例如，{000,001,01,10,11}是前缀码，{1,11,0001,000}不是前缀码，因为000是0001的前缀，1是11的前缀。💡核心特征：解码无歧义

无需向前查看后续代码即可确定当前字符，保证了唯一可译性。定理6.37&6.38：二叉树与前缀码定理6.37任意一棵二叉树的树叶可对应一个前缀码。构造方法：从根到叶的路径，左子树标0，右子树标1，路径上的01序列即为该叶的编码。定理6.38任意一个前缀码都对应一棵二叉树。构造方法：根据编码长度和前缀关系，逐层构建二叉树。▌定理6.37证明给定一棵二叉树，从每个分枝点引出两条边，对左侧边标以权0，对右侧边标以权1，则每片树叶可对应一个0和1的序列，它是由树根到这片树叶的通路上所有权组成的序列，故没有一片树叶标定的序列是另一个的前缀。因此，任意一棵二叉树的树叶可对应一个前缀码。例题6.35：最优前缀码（哈夫曼编码）问题描述已知字母出现频率:A(30%),B(25%),C(20%),D(10%),E(10%),F(5%)。请构造一个前缀码，使传输的二进制位数总和最少。解题核心思路1.构建哈夫曼树：将字母频率作为权值，构造带权(30,25,20,10,10,5)的最优二叉树。

2.生成前缀码：左分支标记“0”，右分支标记“1”。从根节点到叶节点的路径序列即为该字母的哈夫曼编码A:11|B:10|C:01

D:001|E:0001|F:0000高频字母使用短编码，有效降低总传输位数。图示：基于频率构建的哈夫曼树结构例题6.36：决策问题▌问题描述用机器分辨三种硬币：1分(出现概率0.5)、2分(0.4)、5分(0.1)。请设计一个分辨算法，使得机器分辨所需的期望时间最少。▌求解思路与流程1.构建模型：将硬币出现的概率作为权值，构造一棵哈夫曼树（最优二叉树），以此确定判断逻辑。2.决策流程：概率高的硬币分配更短的判断路径。

•第一步：先判断是否为“1分”？(是则结束，路径长度1)

•第二步：若不是，继续判断是否为“2分”？(是则结束，否则必为“5分”，路径长度均为2)期望判断时间计算1×0.5+2×0.4+2×0.1=1.5(时间单位)本节总结根树的概念●定义：带有根节点和明确方向的树结构，是图论中最重要的模型之一。●m叉树：树中每个节点最多有m个儿子。其中二叉树是应用最广泛的特例。●核心性质：完全m叉树满足重要公式：(m-1)i=t-1，其中i为内点数，t为叶点数。最优树(哈夫曼树)●定义：在一组带权叶节点构成的所有二叉树中，带权路径长度(WPL)最短的二叉树。●构建算法：哈夫曼算法(HuffmanAlgorithm)。遵循“贪心策略”：每次从森林中选取两棵权值最小的树合并，直到只剩一棵树为止。前缀码与应用●定义：一种编码方式，任意一个字符的编码都不是另一个字符编码的前缀，可消除解码歧义。●树码对应