离散数学讲义郑版watched08图论有向树

主要内容有向树最优树图

论有且仅有一个结点称为树根，其引入次数是0；除树根外每一结点的引入次数是1；树的每一结点a，都有从树根到a的一条有向路径。有向树也称为根树。通常表示为树根在上，所有弧向下，弧的箭头略去的图。图

论有向树是结点集合非空的，符合以下三条要求的有向图：有向树最优树图

论设a和b是有向树T的结点，如果有一弧从a到b，则称a是b的父亲，而b是a的儿子。如果从结点a到结点b有一有向路径，则称a是b的祖先，而b是a的后裔。如果a≠b，则a是b的一个真祖先，而b是a的一个真后裔。由结点a和它的所有后裔导出的子有向图称为T的子树，a称为子树的树根。如果a不是T的树根，则该子树是T的真子树。引出次数是0的结点称为树的叶；一个结点若不是叶，则称为内部结点（或分枝点）。从树根r到一结点a的路径长度（边的条数）称为a的路径长度，也称为a的层次。树T中层次的最大值称为树T的高度。树根是a；有三个儿子

b,c,d；c没有儿子。e的父亲是b，真祖先是

a和b。树的叶是c,e,f,g,i,ja,b,d,h是内部结点。树的高度是3。具有结点集{b,e,f,g}的子有向图是树根为b的子树。abcedf

g

hij图

论有向树最优树设T是一棵有向树，根是r，并设a是T的任一结点，则从r到a有唯一的有向路径。有向树中的每一有向路径是基本路径。有向树没有非零长度的任何回路。有向树中，m=n-1，m是边数，n是结点数。有向树的子树是有向树。图

论有向树最优树（递归定义）有向树包含一个或多个结点，这些结点中某一个称为树根，其它所有结点被分成有限个子有向树。把n个结点的有向树用结点数少于n的有向树来定义，最后得到每一棵都是仅有一个结点的有向树，它们就是原来那棵树的叶。（括号表示）设有向树T：如果T只有一个结点，则此结点就是它的括号表示。如果T由根r和子树T1，T2，…，Tn组成，则T的括号表示为：根r，左括号，T1，T2，…，Tn的括号表示（两子树之间用逗号分开），右括号。图

论有向树最优树abcd

e

f括号表示为a括号表示为a[b[d,e,f],c]括号表示为a[b,c[e,f[g,h]],d]acdegfbha图

论有向树最优树三元树，但不是完全三元树完全三元树图

论在树T中，如果每一结点的儿子个数是n个或少于

n个，则称此树为n元树。如果每一结点或有n个儿子或没有儿子，则称此树为完全n元树（或称为正则n元树）。图

论设有完全n元树G，其树叶数为t，分枝点数为i，则(n-1)i=t-1证明：设图G有v个结点，e条边，则e＝v－1，而v＝t＋i，e＝n·i，则n·i＝t＋i－1，所以(n－1)i＝t－1。例：设有28盏电灯，拟公用一个电源插座，问需要多少块具有四插座的接线板。解：将四元树的每个分枝点看作是具有四插座的接线板，树叶看作电灯，则有(4-1)i=28-1，i=9，所以9块具有四插座的接线板。例：M和E两人进行网球比赛，如果一人连胜两盘或共胜三盘就获胜，比赛结束。则可用二元树表示比赛可能进行的所有情况。从树根到树叶的每一条路径对应比赛中可能发生的一种情况。EMEMEMEM

EMEMEMEM

EM图

论图

论如果从每一结点引出的边都给定一个次序，或者等价的给结点的每一儿子编序，称它们为某结点的第一、第二、…、第n个儿子。树中每一结点引出的边都规定次序的树，称为有序树。一般自左至右的排列，左兄右弟。如果树中每一结点的儿子不仅给出次序，还明确它们的位置，则此树称为位置树。二元位置树每个结点的儿子，都被指明左儿子或右儿子。一个有向图，如果它的每个连通分图是有向树，则称该有向图为（有向）森林；在森林中，如果所有树都是有序树且给树指定了次序，则称此森林是有序森林。不是相等的有序树b

cbccc不是相等的位置树，上图c是左儿子，下图c是右儿子，是相等的有序树。图

论图

论有序树转化成二元位置树：方法一：除了最左边的分枝点外，删去所有从每一个结点长出的分枝。在同一层次中，兄弟结点之间用从左到右的有向边连接。方法二：选定二元树的左儿子和右儿子如下：直接处于给定结点下面的结点，作为左儿子，对于同一水平线上与给定结点右邻的结点，作为右儿子，以此类推/p>

1113245798610

11图

论d/c+f/e-ab图

论常用树来表示离散结构的层次关系，如可表示算术表达式。例：a-b+(c/d+e/f)+tw(T

)

=

wi

L(wi)i=1称为该带权二元树的权。在所有带权w1,w2,…,wt的二元树中，w(T)最小的那棵树，称为最优树。图

论给定一组权w1,w2,…,wt，不妨设w1≤w2≤…≤wt，设有一棵完全二元树，共有t片树叶，分别带权w1,w2,…,wt，该二元树称为带权二元树。在带权二元树中，若带权为wi的树叶，其通路长度为L(wi)，把图

论设T为带权w1≤w2≤…≤wt的最优树，则带权w1，w2的树叶vw1，vw2是兄弟；以树叶vw1，vw2为儿子的分枝点是通路长度最长（层次最大）的分枝点。证明：设在带权w1,w2,…,wt的最优树中，v是通路长度最长的分枝点，

v的儿子分别带权wx和wy，故有L(wx)=L(wy)，L(wx)≥L(w1)，L(wy)≥L(w2)。若L(wx)>L(w1)，将wx和w1对调，得到新树T’，则w(T’)-w(T)=(L(wx)

·w1+L(w1)·wx)-

(L(wx)

·wx+L(w1)·w1)=

L(wx)(w1-wx)+L(w1)(wx-w1)=(wx-w1)(L(w1)-L(wx))<0即w(T’)<w(T)，与T是最优树的假设矛盾。故L(wx)=L(w1)。图

论设T为带权w1≤w2≤…≤wt的最优树，则带权w1，w2的树叶vw1，vw2是兄弟；以树叶vw1，vw2为儿子的分枝点是通路长度最长（层次最大）的分枝点。证明：同理可证，L(wy)=L(w2)。因此L(w1)=L(w2)=L(wx)=L(wy)，分别将w1，w2与wx，wy对调得到一棵最优树，其中带权w1和w2的树叶是兄弟，且以树叶vw1，vw2为儿子的分枝点是通路长度最长的分枝

点。图

论设T为带权w1≤w2≤…≤wt的最优树，若将以带权w1和w2的树叶为儿子的分枝点改为带权w1+w2的树叶，得到一棵新树T’，则T’也是最优树。证明：由已知条件有w(T)=w(T’)+w1+w2，若T’不是最优树，则必有另一棵带权w1+w2,w3,…,wt的最优树T’’。对T’’中带权w1+w2的树叶vw1+w2生成两个儿子，得到新树T’’’，则w(T’’’)=w(T’’)+w1+w2，因为T’’是带权w1+w2,w3,…,wt的最优树，故w(T’’)≤w(T’)。如果w(T’’)<w(T’)，则

w(T’’’)<w(T)，与T是带权w1,w2,…,wt的最优树的假设矛盾，因此w(T’’)＝w(T’)，所以T’是带权w1+w2,w3,…,wt的最优

树。w1+w2w1w2图

论于是，要画一棵带有t个权的最优树，可简化为画一棵带有t-1个权的最优树，而这又可简化为画一棵带有t-2个权的最优树，依此类推。具体做法：首先找出两个最小的w值，设为w1和w2，然后对t-1个权w1+w2，w3，…，wt，作一棵最优树，并将这棵最优树中的结点代之以

，依此类推。34561271118图

论例：设有一组权3,4,5,6,12,求相应的最优树。30图

论给定一个序列的集合，若没有一个序列是另一个序列的前缀，该序列集合称为前缀码。例：{000,001,01,10,110}是前缀码，{1,0001,000}不是。任意一棵二元树的树叶可对应一个前缀码。证明：给定一棵二元树，从每一个分枝点引出两条边，对左侧边标以0，对右侧边标以1，则每片树叶将可标定一个0和1的序列，它是由树根到这片树叶的通路上各边标号所组成的序列，显然，没有一片树叶的标定序列是另一片树叶标定序列的前缀，所以，任何一棵二元树的树叶可对应一个前缀码。图

论任何一个前缀码都对应一棵二元树。证明：设给定一个前缀码，h表示前缀码中最长序列的长度。可以画出一棵高度为h的完全二元树，并给每一分枝点射出的两条边标以0和1，这样，每个结点可以标定一个二进制序列，它是由树根到该结点通路上各边的标号所确定，因此，对于长度不超过h的每一二进制序列必对应一个结点。对应于前缀码中的每一序列的结点，给予一个标记，并将标记结点的所有后裔和射出的边全部删去，这样得到一棵二元树，再删去其中未加标记的树叶，得到一棵新的二元树，它的树叶就对应给定的前缀码。00001

0

1

0

1

0111001例：前缀码{000,001,01,1}对应的完全二元树。1

011对二进制序列00010011011101001，译码为000，1，001，1，01，1，1，01，001图

论于是，26个英文字母的变长编码问题，可以根据各字母的使用几率p1,p2,…p26，构造一棵具有权值p1,p2,…p26的最优树，按前述方法即可获得其前缀码。图

论图

论二元搜索树：每一结点代表一个记录，假定每一记录的键值都不相同。每一结点的键值大于其左子树中的所有结点的键值，而小于其右子树中所有结点的键值。搜索过程：如果要找的记录的键值是A，则把A和根结点的键值K比较，如果相等，则表示已找到；如果A<K，则转到左子树，若左子树不存在，说明没有该记录；如果A>K，则转到右子树，若右子树不存在，说明没有该记录；转到左(右)子树后，对其重复上述过程。二元搜索树的遍历(周游)：按照根结点被处理的先后不同，分别称为前序、中序、后序遍历算法。假设二元树的根为r，左子树为T1，右子树为T2，前序：a处理T的根结点r；如果T1存在，前序遍历T1；如果T2存在，前序遍历T2。bdcefghjika

b

d

e

h

i

c

f

j

k

g图

论假设二元树的根为r，左子树为T1，右子树为T2，中序：a如果T1存在，中序遍历T1；处理T的根结点r；如果T2存在，中序遍历T2。bdcefghjikd

b

h

e

i

a

f

k

j

c

g图

论假设二元树的根为r，左子树为T1，右子树为T2，后序：如果T1存在，后序遍历T1；如果T2存在，后序遍历T2。处理T的根结点r；adbcefghjikd

h

i

e

b

k

j

f

g

c

a图

论图

论三元树做搜索树时，记录通常只存储在叶结点上，而内部结点只存储两个用作比较的值d1和d2，称为鉴别子。如果要找的记录键值为A，从根结点开始，如果A<d1，转根的左子树，如果d1≤A<d2，转根的中子树，如果d2