7.3 根树及其应用

数学学习 · 爱知数学讲义

18
本章目录 · 2 节

本章导读

【定义7.3.1:有向树与根树】有向图的基图若为无向树,称有向树。其中恰有一个入度0的顶点,其余顶点入度都为1时,称根树,入度0点是树根;边从父亲指向儿子。从根到每个顶点都有唯一的有向路径。仅有“基图是树”不够:随意定向可能出现多个入度0点,不能都叫同一棵外向根树。

非平凡根树中,入度1、出度0的点称树叶;入度1、出度不为0的点称内点;内点与根统称分支点。从根到点 的路径边数为层数 ,根在第0层;所有层数的最大值是树高。图一般把根放最上、边向下,因方向已约定而省略箭头;省略箭头不表示父子方向可以颠倒。平凡根树用于编码边界情况时,另把唯一的根视为一片叶。

uv
图7.3.1:根在上,所有边向下,最深的两片叶为u与v

这棵树有15个顶点、14条边,其中8片树叶、6个内点,加根共7个分支点;高度为5,在 两点达到。根到叶所经过的顶点数为6,而层数、树高按边数为5,不能多算1。

【定义7.3.2:家族关系与有序树】沿正长度的有向路径从 到达 时,称 为 的严格祖先, 为 的后代;若直接有弧 ,则 为父亲、 为儿子;同父的不同顶点为兄弟。若用允许零长度的“可达”定义广义祖先,可包含自身,应与这里的严格祖先区别。

为每个分支点的儿子固定从左到右的次序,便得到有序树,相应同层顶点也有确定次序。交换左右儿子,对无序树可能仍同构,对有序树则可能改变结构;二叉树中的左、右位置不能只靠画图时临时猜测。

若每个分支点至多有 个儿子,称 叉树;恰有 个儿子,称 叉正则树;再要求全部树叶都在最大层数上,称 叉完全正则树。加上固定次序,分别称对应的有序树。这里的“二叉正则”即每个分支点恰有两个儿子;“完全正则”是所有叶都在末层,不能与数据结构中末层允许缺一部分的“完全二叉树”混用。

【定义7.3.3:根子树】顶点 及其全部后代的导出子图,以 为根,称根子树 。二叉有序树中,一个分支点的左、右儿子分别导出它的左子树、右子树;若讨论非正则二叉树,某一侧子树可以为空。

【定义7.3.4:带权二叉树与最优二叉树】给 片树叶非负权 ,定义 。具有这些叶权且 最小的二叉树称最优二叉树。权乘的是叶的层数,不是顶点编号、分支点数或边权;通常叶权为频数、概率或费用。

应明确非负权这一适用条件。若允许负叶权、又允许插入只有一个儿子的节点,可不断把负权叶放得更深,使 无下界,便谈不上最优树。对非负权,收缩单儿子分支不会增加权,因此可以在二叉正则树中寻找最优者。

22353
图7.3.2:T1,叶权2、2、3、5、3,树权38

。

35322
图7.3.2:T2,深链形状,树权47

。

33522
图7.3.2:T3,树权36

。三树都用同一个叶权多重集,但结构不同、加权路径长度不同;不能只根据树高判断最优。

【霍夫曼算法】输入为 个非负叶权;输出为一棵最优二叉树及其加权路径长度。先为每个权建立一片独立树叶;反复选当前所有树根中权最小的两个,新增一个父节点,以二者为儿子,父权为两权之和,再把这棵新树放回候选集合。直到只有一个树根,算法结束。候选不仅包括原始树叶,也包括此前合成的子树,不能始终只从原叶中取最小者。

每次合并使该对子树的全部叶深度增加1,增加的代价就是两根权之和。因此最终 等于各次合并权之和,也等于全部分支点权之和。用小根堆可在 时间构造;相同权的选择次序和左右位置可能不唯一,所得最优权相同。

最优性理由:在某棵最优的二叉正则树中,可把两个最小权叶安排到最深的一对兄弟位置而不增加总代价;将这对兄弟收缩为一个权为两者之和的叶,问题变成少一个叶的同类问题。对叶数归纳,就得到每次合并最小两权的规则。单一符号 时理论可用空码、层数0;实际通信若约定至少发一位,则可用码0,须另说明这一编码约定。

【例7.3.1:叶权2、2、3、3、5】合并顺序为 、、、。对应过程如下,尚未连接的各棵树都是当前候选。

22335
图7.3.3(a):五片独立树叶
422335
图7.3.3(b):合并两个2,得到4
4226335
图7.3.3(c):合并两个3,得到6
94225633
图7.3.3(d):合并4与5,得到9
1594225633
图7.3.3(e):合并9与6,完成最优树

最优权 ,也等于两片2权叶在第3层、其余三叶在第2层的 。所以图7.3.2的38、47、36三棵都不是最优。(例完)

【等长码与非等长码】四个符号 可用 表示,均长2,是等长码;频率近似相等时很自然。频率差别大时,让常见符号码字短、少见符号码字长,可能降低总位数,但还必须保证能够明确解码,不能只随意缩短码字。

【定义7.3.5:前缀码】字符串的前缀是从开头连续取出的部分,教材列出非空前缀并包括整个字符串自身。若码字集合中任意两个不同码字都互不为对方的前缀,称前缀码;全部由0、1构成,称二元前缀码。这里必须是“不同码字”,否则每串都是自身前缀。

例如 是前缀码;若再加入 ,它就是后两串的前缀,因而不再是前缀码。

【由树产生码字】在固定的二叉有序树上,两儿子时约定左边标0、右边标1;只有一个儿子时,可给该边另行选择0或1。根到某片树叶的边标号串就是该叶的码字。所有码字都在叶上,一个叶不可能是另一个叶的祖先,故所得码字互不为前缀;读比特时沿树向下,到叶就输出一个符号并回根,能即时分段解码。

只有固定有序结构、边标规则以及符号在叶上的对应后,产生的具体编码才确定。不能把“某棵无序二叉正则树”直接说成唯一编码,因为交换左右子树或交换叶的符号仍可改变码字。

例7.3.2:两棵二叉树的前缀码

图7.3.4(a):含一个单儿子节点的二叉树
图7.3.4(b):六片叶的二叉正则树

图(a)把根的右儿子引出的唯一边标1,得到 ,如下图。

000101111000001000110111
图7.3.5(a):五片叶对应五个码字

若只把这条单儿子边改标0,就只有经过它的码字由 变成 ;其余四码不变,正确集合为 。原书另列的 也是前缀码,但它由原集合全部逐位取反得到,不是只改这一条边的结果,不能混为同一操作。

图(b)固定左0右1后,得到 。

000101110100000100011011011
图7.3.5(b):六片叶对应六个码字

图(a)有5码,图(b)有6码,分别可给5或6个不同符号编码;实际选用哪些叶、哪个符号对应哪码还要指定,不能遗漏第六个码字。(例完)

【最佳前缀码】若符号 出现概率为 ,码长为 ,平均码长为 ;传输 个严格符合给定频率的符号,位数为 。以频率或频数为叶权构造最优二叉树,得到的二元前缀码使这项总长度最小,称最佳前缀码。若频率只是统计模型,公式给出期望长度,不能声称每一段实际文本都恰好等于期望值。

【例7.3.3:八进制数字的最优编码】数字0至7的频率依次为 ,取每100个符号的频数为叶权。

0000011111001110060352010500000500001100001150012501402010100101012011
图7.3.6(a):第一组最优码,内部数字为子树总频数

第一组码为 ,,,,,,,。每个码都应与图中根到该叶的0/1串一致。

其总权为 ,也等于内部合并权之和 。所以平均每符号2.85位。

若严格按给定比例传输 个数字,,需 位;固定3位编码需 位,节省 位,即5%。这里仅比较码流,不另计传送码表、帧头等额外开销。

000011110001111004020105000050001100012001603520101000101001151012511
图7.3.6(b):另一组同权最优码,说明最优解不唯一

第二组为 ,,,,,,,,总权仍285。相同频数导致可选的合并次序不同,左右摆放也可交换;最佳前缀码并不唯一,不能用“具体码字不同”判另一份正确解为错。(例完)

【二叉树的三种周游】周游或行遍指每个顶点访问一次且仅一次。对二叉有序树,三种顺序递归定义为:中序“左子树、根、右子树”;前序“根、左子树、右子树”;后序“左子树、右子树、根”。空子树不输出任何点。这些规则不只适用于正则树,缺少某侧儿子时仍可照用。

abdhiecfg
图7.3.7:用于比较三种周游的九顶点有序树

图中根为 ,左子树根 、右子树根 ; 的左儿子 又有 。中序结果为 ;前序为 ;后序为 。每种结果都含9点、无遗漏或重复,括号只用于展示递归分组,不另算被访问的顶点。

【表达式树】操作数放树叶,二元运算符放分支点,左、右子树分别表示左、右操作数。减法、除法尤其要保留顺序:被减数、被除数在左,减数、除数在右。仅交换子树通常会改变值;不能因加法、乘法某些情况下可交换就把所有运算混作无序树。

【例7.3.4:表达式及三种遍历】原式为 。按原书树形,把连乘明确括成 ,得到下图;对通常实数乘法与原式数值相同。若要记录程序中严格从左到右的连乘求值顺序,则应采用另一棵左结合树,不能把两棵树的遍历串混用。

÷+×a+bc×d×ef+g×−hij
图7.3.8:按原书结合顺序重绘的表达式树

加括号的中序表达式为 。

前序即波兰式,按空格分隔每个记号:。

后序即逆波兰式:。分隔记号是为了让多字符变量和数字也能明确读取,不应把所有字符无间隔粘连后再猜操作数边界。

前缀式从右往左读,可用栈:遇操作数压栈,遇二元运算符先弹出左操作数、再弹出右操作数,计算后压回。后缀式从左往右读时,先弹出的却是右操作数,再弹左操作数,然后算“左运算右”。两种扫描方向的弹栈顺序不能混淆,否则 或最外层除法会被倒置。最后栈应恰留一个结果,并且原分母不能为0。(例完)