离散数学及其应用-10 树

10.1无向树10.2有向树与根树第十章

树树是一大类特殊的图,其结构与衍生算法在电路电网、计算科学、网络技术、人工智能、软件工程、知识工程等领域有重要而广泛的应用。本章主要介绍树的基础知识,如:相关概念、重要结论、基础算法与应用。树（Tree）与相关概念

连通无回路的无向图称为无向树,简称为树（tree）,记作T。平凡图称为平凡树。无回路的无向图称为森林（forest）,森林的各连通分支为树。树中的悬挂顶点称为树叶,其他顶点称为分支点。10.1.1树的相关定义判断如下各图是否为树。解左上图为树,中上图为平凡树,均连通无回路;右上图为非连通图,无回路,为森林。它的每个连通分支均为树:连通分支G[{v1,v2,v3,v4}]、连通分支G[{v5,v6,v7,v8}]、孤立顶点（平凡树）组成连通分支G[{v9}]。10.1.1树的相关定义（d）（f）（e）（a）（c）（b）判断如下各图是否为树。解（续）左下图连通有回路v1v2v7v3v1,不是树;中下图为一条初级通路,符合树的定义;右下图是树。10.1.1树的相关定义（d）（f）（e）（a）（c）（b）定理

树T=<V,E>,n=|V|,m=|E|,有如下等价定义:

（1）无回路的连通图。

（2）无回路而且m=n-1。

（3）连通而且m=n-1。

（4）T无回路,如果增加1条边则得到一条且只有一条初级回路。

（5）T连通而且每条边均是割边（桥）。

（6）T为简单图而且每对顶点之间有唯一一条初级通路。证明（略；参考《离散数学及其应用》,183-184页）

10.1.1树的相关定义

10.1.1树的相关定义

10.1.1树的相关定义定理

非平凡树T的顶点总可以被列举为某序列v1,v2,…,vn使得对任意2≤i≤n,vi在子序列v1,v2,…,vi-1中有唯一邻接顶点。证明

先证明存在：由连通图定理知,T连通,其顶点总可以被列举为一序列v1,v2,…,vn,对任意2≤i≤n,T[v1,v2,…,vi-1]连通,无回路,是树。而顶点v∈T-T[v1,v2,…,vi-1]与顶点vi-1在T中连通,则T中存在唯一初级通路Pvi-1,v,沿着顶点vi-1到v的第1个不属于子序列v1,v2,…,vi-1的顶点定义为vi,易知vi在子序列v1,v2,…,vi-1中有邻接点。10.1.1树的相关定义定理

非平凡树T的顶点总可以被列举为某序列v1,v2,…,vn使得对任意2≤i≤n,vi在子序列v1,v2,…,vi-1中有唯一邻接顶点。证明

再证明唯一：反证vi在子序列v1,v2,…,vi-1中有2个相异的邻接顶点vs≠vt,1≤s,t≤i-1,而在T[v1,v2,…,vi-1]中vs,vt连通,有初级通路Ps,t⊆T[v1,v2,…,vi-1],则T中有初级回路L:Ps,t∪{es,i=(vs,vi),ei,t=(vi,vt)},es,i,ei,t∉T[v1,v2,…,vi-1],与T无回路矛盾。10.1.1树的相关定义

10.1.2图与生成树定理

任意连通无向图G至少有一个生成树T。证明

如果连通图G无回路,则G为树,是G的生成树。如果连通图G有回路（包括重边和环）,每逢回路,则删除回路中任意一条边,直至所得连通子图无回路,得G的一个生成树T。10.1.2图与生成树定理

任意无向图G有生成树的充分必要条件是图G连通。证明

如由前一结论知,充分条件成立。由生成树T连通和V(T)=V(G)知,图G的任意两点均连通,必要条件成立。10.1.2图与生成树

由连通图得到生成树有众多应用,如网络通信中IP组播路由技术为高效传输数据,需在连通网络中设计无回路的方案,即构造生成树。

构造生成树以及优化算法不一而足,本章将陆续介绍Kruskal算法、广度优先搜索和深度优先搜索算法。10.1.2图与生成树举例说明如下两图中均有生成树。解

两图均连通,均存在生成树。左图如果删除边(u2,u3),(u3,u4),(u4,u5),(u2,u0),(u4,u0),得生成子图为树;如果删除边(u1,u4),(u3,u4),(u4,u0),(u3,u0),(u1,u0),又得一生成树。右图同理,有多种删除边的方法而得到不同生成树;例如,删除边(u1,u4),(u4,v4),(u1,v1),(u3,v3),(v1,v4),得到生成子图为树。10.1.2图与生成树

10.1.2图与生成树

10.1.2图与生成树定理

连通无向图G=<V,E>任意边割集E'与G的生成树T之交集至少有一公共边。证明

反证⇔E(T)∩E'=⌀,有~E'∪(E(T)∩E')=~E'=E-E'=(~E'∪E(T))∩(~E'∪E')=(~E'∪E(T))∩E=~E'∪E(T)=(E-E')∪E(T)⇔E(T)⊆E-E'⇒T⊆G-E':删除边割集得到图G'=G-E'包含树T。而V(G')=V(T),T连通,G'不连通,矛盾。10.1.2图与生成树定理

如果T=<V,E>是树,简单无向图G有δ(G)≥|V|-1,则T⊆G,即图G包含一个同构于T的子图。证明

在T的顶点数|V|上做数学归纳,|V|=1⇒T为平凡图,而图G顶点集非空,显然有顶点令T⊆G。|V|=2⇒T为二顶点均为树叶的无分支点树,G有δ(G)≥|V|-1=1⇒G所有顶点度不小于1,而G无环无重边,则顶点v有非v邻接点u⇒T0=<V={u,v},E={(u,v)}>⊆G,与T同构。

|V|=n(n≥2)时,G有δ(G)≥|V|-1⇒T⊆G,即G包含一个同构于T的子图。10.1.2图与生成树

10.1.2图与生成树

10.1.2图与生成树

10.1.2图与生成树定理

连通图G各边的权均不相同,则回路中权最大的边不在G的最小生成树中。证明

反证,令图G=<V,E>回路L:v1e1,2v2…vn0en0,1v1,V(L)=n0。如果L为一顶点的环,则边非割边,不在最小生成树T中。否则,不妨令L权最大的边emax=(v1,v2)∈L在图G的最小生成树T中emax∈T。则回路L中其他边有e∈L,e≠emax⇒ω(e)<ω(emax)。T是G的生成树,则T-{emax}为2个树连通分支T1,T2⇒v1∈T1,v2∈T2,则回路L各顶点在T-{emax}中不连通。10.1.2图与生成树定理

连通图G各边的权均不相同,则回路中权最大的边不在G的最小生成树中。证明（续）

而回路L中各顶点在L-{emax}中连通,则有经过各顶点通路P:v2e2,3v3…vn0en0,1v1,所以P中有边ei,j=(vi,vj),ei,j≠emax,vi∈T1,vj∈T2,ei,j∉T-{emax}可以将T'=T-{emax}两连通分支各一点vi∈T1,vj∈T2连通,则T'=(T-{emax})∪{ei,j}连通。而|V(T')|=|V(T)|=|V|=n,|E(T')|=|E(T)|-1+1=|E(T)|=n-1⇒T'是图G的生成树,有ω(T')=∑e∈T'ω(e)=(∑e∈Tω(e))-ω(emax)+ω(ei,j)=(∑e∈Tω(e))-(ω(emax)-ω(ei,j))<∑e∈Tω(e)=ω(T),与T是图G最小生成树矛盾。10.1.2图与生成树

一类图与树的最优化应用问题要求找到已知赋权连通图的最小生成树,此生成树可以被认为是令图连通成本最小的子图;另外,局部角度的应用问题有求图中指定点到其他点的距离或最短路径等。

在此讨论的Kruskal（克鲁斯卡尔）和Dijkstra（迪克斯特拉）算法的核心思想均为贪心策略,即在每一步都寻求当前最优解,称为“局部最优”。10.1.3图与树的最优化求赋权连通图最小生成树Kruskal算法初始化:赋权连通图G=<V,E,ω>,树T=<VT,ET>,ET=⌀,VT=V,n=|V|,m=|E|,i=1,令有序集为边集E中元素按权升序排列:H={e1,e2,…,em},ω(e1)≤ω(e2)≤…≤ω(em)Whilei<ndo令e为有序集H中第一个元素IfG[ET∪{e}]中无回路then1.更新ET=ET∪{e}2.更新i=i+1EndIf更新H=H-{e}EndWhile10.1.3图与树的最优化

如下赋权图G=<V,E,ω>,用Kruskal算法求其最小生成树。10.1.3图与树的最优化如下赋权图G=<V,E,ω>,用Kruskal算法求其最小生成树。解

初始化边集S,有序集H,顶点数n,变量i:S=⌀,H=E={(u1,v1),(u4,v4),(u3,u4),(u1,u4),(u2,u3),(v3,v4),(v1,v4),(v2,v3),(v1,v2),(u1,u2),(u2,v2),(u3,v3)},n=8,i=1。minω(H)=ω((u1,v1))=0.5,S={(u1,v1)},i=2,H=H-{(u1,v1)}minω(H)=ω((u4,v4))=0.75,S={(u1,v1),(u4,v4)},i=3,H=H-{(u4,v4)}minω(H)=ω((u3,u4))=1,S={(u1,v1),(u4,v4),(u3,u4)},i=4,H=H-{(u3,u4)}10.1.3图与树的最优化如下赋权图G=<V,E,ω>,用Kruskal算法求其最小生成树。解（续）minω(H)=ω((u1,u4))=1.5,S={(u1,v1),(u4,v4),(u3,u4),(u1,u4)},i=5,H=H-{(u1,u4)}minω(H)=ω((u2,u3))=2,S={(u1,v1),(u4,v4),(u3,u4),(u1,u4),(u2,u3)},i=6,H=H-{(u2,u3)}minω(H)=ω((v3,v4))=2.5,S={(u1,v1),(u4,v4),(u3,u4),(u1,u4),(u2,u3),(v3,v4)},i=7,H=H-{(v3,v4)}minω(H)=ω((v1,v4))=3,G[S∪{(v1,v4)}]有回路,不更新i,H10.1.3图与树的最优化如下赋权图G=<V,E,ω>,用Kruskal算法求其最小生成树。解（续）

minω(H)=ω((v2,v3))=4,S={(u1,v1),(u4,v4),(u3,u4),(u1,u4),(u2,u3),(v3,v4),(v2,v3)},i=8,H=H-{(v2,v3)}i=8=n,算法终止。

最小生成树为G的生成树,同时为边集S的导出子图G[S],权为0.5+0.75+1+1.5+2+2.5+4=12.25,最小生成树构造过程如图所示。10.1.3图与树的最优化如下赋权图G=<V,E,ω>,用Kruskal算法求其最小生成树。10.1.3图与树的最优化广度优先搜索算法初始化:(有向)图G=<V,E>,顶点集VT=⌀,G中任意顶点v∈V,d(v)=+∞,指定G中顶点u,d(u)=0WhileVT≠Vdo1.d(s)=minv∉VTd(v)2.更新VT=VT∪{s}3.Fors邻接到顶点tdo(注意:G为无向图e=(s,t),G为有向图e=<s,t>)Ift∉VTthen更新d(t)=min{1+d(s),d(t)}EndIfEndForEndWhile10.1.3图与树的最优化Dijkstra算法初始化:赋权(有向)图G=<V,E,ω>,顶点集VT=⌀,G中任意顶点v∈V,d(v)=+∞,指定G中顶点u,d(u)=0WhileVT≠Vdo1.d(s)=minv∉VTd(v)2.更新VT=VT∪{s}3.Fors邻接到顶点tdo(注意:G为无向图e=(s,t),G为有向图e=<s,t>)Ift∉VTthen更新d(t)=min{ωe+d(s),d(t)}

(注意:边e的权ωe=ω(e))EndIfEndForEndWhile10.1.3图与树的最优化如下赋权图G=<V,E,ω>,用Dijkstra算法求顶点v1到各顶点最短路径。10.1.3图与树的最优化如下赋权图G=<V,E,ω>,用Dijkstra算法求顶点v1到各顶点最短路径。解

初始化:顶点集VT=⌀,赋权图G=<V,E,ω>任意顶点v∈V,d(v)=+∞,令v1,d(v1)=0。1.VT=VT∪{v1}={v1},d(v1)=0,v1的邻接点u1,v2,v4d(u1)=min{ω(v1u1)+d(v1),d(u1)}=0.5d(v2)=min{ω(v1v2)+d(v1),d(v2)}=4.5d(v4)=min{ω(v1v4)+d(v1),d(v4)}=32.VT=VT∪{u1}={v1,u1},d(u1)=0.5,u1的邻接点u2,u4d(u2)=min{ω(u1u2)+d(u1),d(u2)}=5.5d(u4)=min{ω(u1u4)+d(u1),d(u4)}=210.1.3图与树的最优化如下赋权图G=<V,E,ω>,用Dijkstra算法求顶点v1到各顶点最短路径。解（续）

3.VT=VT∪{u4}={v1,u1,u4},d(u4)=2,u4的邻接点u3,v4d(u3)=min{ω(u4u3)+d(u4),d(u3)}=3d(v4)=min{ω(u4v4)+d(u4),d(v4)}=2.754.VT=VT∪{v4}={v1,u1,u4,v4},d(v4)=2.75,v4的邻接点v3有d(v3)=min{ω(v4v3)+d(v4),d(v3)}=5.255.VT=VT∪{u3}={v1,u1,u4,v4,u3},d(u3)=3,u3的邻接点u2,v3有d(u2)=min{ω(u3u2)+d(u3),d(u2)}=5d(v3)=min{ω(u3v3)+d(u3),d(v3)}=5.2510.1.3图与树的最优化如下赋权图G=<V,E,ω>,用Dijkstra算法求顶点v1到各顶点最短路径。解（续）

6.VT=VT∪{v2}={v1,u1,u4,v4,u3,v2},d(v2)=4.5,邻接点u2,v3d(u2)=min{ω(v2u2)+d(v2),d(u2)}=5d(v3)=min{ω(v2v3)+d(v2),d(v3)}=5.257.VT=VT∪{u2}={v1,u1,u4,v4,u3,v2,u2},d(u2)=58.VT=VT∪{v3}={v1,u1,u4,v4,u3,v2,u2,v3},d(v3)=5.25,终止。图中各顶点到顶点v1最短路径分别为d(v1,v1)=0,d(v1,u1)=0.5,d(v1,u4)=2,d(v1,v4)=2.75,d(v1,u3)=3,d(v1,v2)=4.5,d(v1,u2)=5,d(v1,v3)=5.2510.1.3图与树的最优化例子中赋权图运用Dijkstra算法求最短路径,非赋权情况G=<V,E>只需令Dijkstra算法中所有边的权为1。10.1.3图与树的最优化10.1无向树10.2有向树与根树第十章

树根树的两种定义与相关概念（1）如果有向图G=<V,E>忽略方向是树,则有向图G是有向树。有向树如果恰有一顶点入度为0,其他顶点入度均为1,则为根树（rootedtree）。入度为0的顶点称为（树）根,出度为0的顶点称为树叶,出度不为0的顶点称为分支点或内点。（2）根树的递归定义：1、根树T为一孤立顶点v0,则v0为T的根。2、T1,T2,…,Tk是以顶点v1,v2,…,vk为根的根树,则根树T由T1,T2,…,Tk和邻接到v1,v2,…,vk的顶点v0为根所组成。10.2.1根

树由偏序关系相关知识判断,（有向树）根树T=<V,E>顶点集V上各顶点可达关系自反:规定所有顶点可达自己;可达关系反对称:如果顶点u可达v(u≠v),则v不可达u,否则T中有回路,另外,可达关系显然传递。所以根树顶点间的可达关系,即不同顶点之间是否有通路,为偏序关系R。根树任意两不同顶点uRv⇔u到v有通路,根v0到其他任意顶点都有通路,v0同时为极小元和最小元,任一叶s的出度为0,则V中不存在元素t令s到t有通路,叶是极大元,不一定是最大元。根到其他任意顶点有唯一一条初级通路,易证组成此初级通路的顶点集为链,其顶点两两可比。非平凡根树如果以除根外任一点v为根,所有顶点u,vRu的导出子图仍为根树。10.2.1根

树根树的相关定义

根树T的根v0到其他任意顶点vi有唯一一条初级通路,通路长度称为顶点vi的层数,记作l(vi)。根树T的最大层数称为树高,记作h(T)=maxv∈Tl(v)。

由家族树这一概念,定义根树若干术语。如果顶点u邻接到顶点v,则称顶点u为顶点v的父亲,v为u的儿子;如果u邻接到顶点v1,v2,…,vk,顶点v1,v2,…,vk共有一个父亲,称顶点v1,v2,…,vk为兄弟;u可达v,则称u为v的祖先,v为u的后代。

以根树T一顶点u和u的所有后代组成的导出子图T'称为根树T的以u为根的子（根）树,顶点u不是根树T的根时得到真子树。10.2.1根

树根树的分类

按照根树T顶点排列与否、兄弟顶点数量、叶层数等,根树有如下细分:

（1）每一层顶点都按一定次序排列的根树T称为有序树。

（2）每个顶点最多有m个儿子的根树T称为m元树。

（3）每个顶点都有m个或0个儿子的根树T称为m元正则树。

（4）m元树而且是有序树的根树T称为m元有序树。

（5）m元正则树而且是有序树的根树T称为m元有序正则树。10.2.1根

树根树的分类（续）

按照根树T顶点排列与否、兄弟顶点数量、叶层数等,根树有如下细分:

（6）m元正则树而且所有叶层数都等于树高的根树T称为m元完全正则树。

（7）m元完全正则树而且是有序树的根树T称为m元有序完全正则树。

（8）m元树而且为每个顶点的儿子规定了确定的位置的根树T称为m元位置树。10.2.1根

树简要讲述如下图所示各例。图中均为有向树,亦为根树,（a）为方向省略的根树,约定顶点u0为根,分支点和叶子分层排列。（b）恰有一顶点1入度为0,其他顶点入度为1,为以顶点1为根的根树;根树的任意顶点及其后代的导出子图为根树,例如以分支点10为根,顶点10-17的导出子图为根树。（c）恰有一顶点a入度为0,其他顶点入度为1,为根树;还是二元完全正则树,树高为2。10.2.1根

树（a）（c）（b）遍历相关定义

图有序根树（位置树）结构数据有利于计算机系统访问,访问根树所有顶点均恰好一次的过程称为遍历（traversal）。

常用的遍历算法有前序遍历（pre-ordertraversal）,中序遍历（in-ordertraversal）和后序遍历（post-ordertraversal）。

遍历访问有序根树需定义顶点的m个子顶点T1,T2,…,Tm的顺序1,2,…,m。计算机相关应用常考虑二元树（binarytree）,即m=2。10.2.2有序根树的遍历前序遍历与后序遍历的递归定义（1）根树T的根为r。1、如果T只包含r,则r是T的前序遍历。2、如果T1,T2,…,Tm是T以r为根自左向右的子树,先前序遍历访问r,再前序遍历访问T1,前序遍历访问T2,…,直至前序遍历访问Tm为止。（2）根树T的根为r。1、如果T只包含r,则r是T的后序遍历。2、如果T1,T2,…,Tm是T以r为根自左向右的子树,先后序遍历访问T1,后序遍历访问T2,…,后序遍历访问Tm,直至后序遍历访问根r为止。10.2.2有序根树的遍历XML格式文档结构为顶点带标签的有序有向(根)树G=<V,E,r,A>,V、E、r、A为顶点集、边集、根、标签集。检索指定内容等于检索有序树顶点标签。画出XML例子的根树。<book><authors><author>authorA</author><author>authorB</author></authors><title>Novel</title><publisher>PressXYZ</publisher><contents><edition>2019</edition><chapters><chapter>one</chapter><chapter>two</chapter><chapter>three</chapter><chapter>four</chapter></chapters></contents></book>

10.2.2有序根树的遍历XML格式文档结构为顶点带标签的有序有向(根)树G=<V,E,r,A>,V、E、r、A为顶点集、边集、根、标签集。检索指定内容等于检索有序树顶点标签。画出XML例子的根树。<book><authors><author>authorA</author><author>authorB</author></authors><title>Novel</title><publisher>PressXYZ</publisher><contents><edition>2019</edition><chapters><chapter>one</chapter><chapter>two</chapter><chapter>three</chapter><chapter>four</chapter></chapters></contents></book>

10.2.2有序根树的遍历解

一种对XML数据的有序有向(根)树G=<V,E,r,A>中任意顶点的Dewey编码规则如下:1、根r的Dewey编码为0。2、G中顶点v为u的第i个儿子,则v的Dewey编码:D(u).i-1,D(u)为顶点u的Dewey编码。在前一题XML数据树结构中画出Dewey编码。解

10.2.2有序根树的遍历

10.2.2有序根树的遍历

10.2.2有序根树的遍历连通图G=<V,E>有生成树,在G中指定一点u,运用深度和广度优先搜索可得以顶点u为根的根树,此根树忽略方向为连通图G的生成树,T=<VT,ET>,VT=V。如果G非连通,深度和广度优先搜索可得G指定顶点u所在连通分支的生成树T=<VT,ET>。深度优先搜索核心思想为递归策略。对有序根树T的遍历是连通图G=T时深度优先搜索一特例。10.2.2有序根树的遍历深度优先搜索算法初始化:G=<V,E>,指定顶点u∈G,树T=<VT,ET>,VT={u},ET=⌀VISIT(u)FunctionVISIT(nodeu)For顶点u邻接到顶点vdoIfv∉VTthen1.令u,v一关联边e=(u,v),G为有向图则e=<u,v>2.更新VT=VT∪{v}3.更新ET=ET∪{e}4.VISIT(v)EndIfEndForEndFunction10.2.2有序根树的遍历广度优先搜索算法初始化:G=<V,E>,指定顶点u∈G,树T=<VT,ET>,VT={u},ET=⌀,有序集S={u}WhileS≠⌀do令S中第一个顶点为s,更新S=S-{s}For顶点s邻接到顶点tdoIft∉VTthen1.令s,t一关联边e=(s,t),G为有向图则e=<s,t>2.更新S=S∪{t}:将顶点t置于有序集S之尾3.更新VT=VT∪{t}4.更新ET=ET∪{e}EndIfEndForEndWhile10.2.2有序根树的遍历如下图所示,用广度和深度优先搜索算法分别由指定顶点c访问连通图G=<V,E>（搜索过程如需顺序可以按照顶点的字母顺序）。10.2.2有序根树的遍历如下图所示,用广度和深度优先搜索算法分别由指定顶点c访问连通图G=<V,E>（搜索过程如需顺序可以按照顶点的字母顺序）。解广度优先搜索算法10.2.2有序根树的遍历如下图所示,用广度和深度优先搜索算法分别由指定顶点c访问连通图G=<V,E>（搜索过程如需顺序可以按照顶点的字母顺序）。解（续）深度优先搜索算法10.2.2有序根树的遍历如下图所示,用广度和深度优先搜索算法分别由指定顶点c访问连通图G=<V,E>（搜索过程如需顺序可以按照顶点的字母顺序）。解（续）二者访问连通图结果对比10.2.2有序根树的遍历由指定顶点u开始访问图,深度优先搜索而得的根树称作根为u的DFS树(DepthFirstSearchTree),广度优先搜索而得的根树称作根为u的BFS树(BreadthFirstSearchTree)。需注意,例题中广度与深度优先搜索算法在访问一顶点邻接到的不同顶点时,默认按照顶点字母顺序;如果按照其他指定顺序访问,可以得到不同结果。10.2.2有序根树的遍历前文介绍赋权图与优化问题基于对已知图中所有边赋予非负权的一类图,而本节介绍的基于根树的优化问题将在求解过程中构造二元正则树,优化思想在于逐步指定根树中叶的权,直至求解结束得到全局最优,即求最优二元树问题。这一问题在通信与数据压缩领域是基本问题之一,奠定了数字通信的基础。传递信息需要将其内容的载体转换成通信工具通用的语言,也就是字符的编码问题。通常可以将字符转换成只由0和1构成的二进制位序列。以英文字符为例,最简单直观的二进制编码是将字母表中的每个字符转换成固定长度一一对应的二进制序列,然后将通信内容文本的字符逐一转换成对应的二进制编码,再连接成串用于通信传输。10.2.3基于根树的最优化问题是编码的固定长度与需转换的字母表中字符数量有关,如4位二进制码最多可以表示24=16个不同字符,如果考虑转换实际应用的所有字符,则需更多位二进制码。而自然语言中各字符使用频率截然不同,如英文字母e,t,a使用频率较j,x,z可能高一个数量级。用相同位数二进制码来传输使用频率相差悬殊的字符易造成资源浪费。最直观的优化策略是采用不等长度二进制编码,用少位数的二进制编码传输使用最频繁的字符,而用多位数编码传输使用最不频繁的字符,前提是要求传输内容在接收端能被正确地翻译。可变长编码模式需解决的问题是少位数二进制编码如何不被翻译为多位数二进制编码的前缀,例如用01编码字符e而用011编码字符c,在翻译时为避免造成字符c前两位被译成字符e的混淆,为此定义前缀码。10.2.3基于根树的最优化前缀码

问题令a1a2…an是长度为n的符号串,称其子串a1,a1a2,…,a1a2…an-1分别为此符号串的长度为1,2,…,n-1的前缀(prefix)。令A={β1,β2,…,βn}为一符号串集合,如果A中任意两不同符号串βi,βj互不为前缀,则称A为一组前缀码(prefix-freecode)。如果符号串集A由两个符号组成其所有符号串,则称A为二元前缀码。

如此一来,前缀码编译的文本传输到接收端后对不同长度编码的译码不再因前缀问题而混淆。10.2.3基于根树的最优化

字符a,b,c,d,e编码γ:γ(a)=00,γ(b)=110,γ(c)=111,γ(d)=01,γ(e)=10,验证能否作为一组二元前缀码。解可以验证γ为一组二元前缀码:用到二位编码00,01,10无重复,三位编码均无以00,01或10作为前缀的。

例如,接收端得到011011100110,可准确无误译码为decab,而不会有任何前缀带来的不确定。10.2.3基于根树的最优化Huffman树（最优树）

根树T的叶数量为t,分别为v1,v2,…,vt,所赋权分别为ω1,ω2,…,ωt,则称T为(叶)赋权树或(叶)带权树,称T的权为Ω(T)=∑ti=1ωi·l(vi),l(vi)为叶vi的层数。叶赋权为ω1,ω2,…,ωt的二元树中权最小的二元树称为最优二元树,简称最优树(HuffmanTree)。10.2.3基于根树的最优化引理

根树T为赋权ω1≤ω2≤…≤ωt的最优树,则权最小ω1,ω2的两叶子v1,v2是T层数最大分支点的儿子,二者为兄弟。证明（略；参考《离散数学及其应用》,203页）

由引理知,最优前