第18讲 无向树与有向树 重点内容: 1.无向树. 2.有向树.

8.3 无向树 树是图论中的重要内容之一(研究独立) (1) 1847年Kirchhoff电路网络; (2) A. Cayley 1857同分异构体. 树分为无向树和有向树. 本节仅讨论无向树. 树在各个领域都有重要应用, 特别是在计算机科学中.

1.无向树的定义 Def 8-3 (1)不含有圈的(2)连通无向图称为无向树(tree = undirected tree). 每个连通分支均是无向树的无向图称为森林(forest).

无向树在图论中称为树,也可以称为自由树. 含n(n  1)个节点的树称为n阶树. 不含任意节点的空图称为空树. 不同构的1阶无向树、2阶无向树、3阶无向树见图8-18(a)(b)(c), 4阶无向树见例8-7? 课堂: P233, 1.

2.无向树的性质 (1)无向树的基本性质 性质1 n(n  1)阶无向树恰有n - 1条边. Proof 对n使用数学归纳法. n = 1? v  V, deg(v) = 1: G – v? 例8-6(P230) 设G是一棵无向树且有3个3度节点,1个2度节点,其余均为1度节点. (1)求出该无向树共有多少个节点. (2)画出两棵不同构的满足上述要求的无向树.

Solution (1)设G有x个节点度数为1,则G的节点数为x + 3 + 1 = x + 4. 由无向树的性质1知, G恰有x + 3条边. 由握手定理,有3∙3 + 1∙2 + x ∙ 1 = 2(x + 3),于是x = 5. 所以G有9个节点. (2)两棵不同构的满足上述要求的无向树见图8-19.

性质2 n(n  2)阶无向树至少两片树叶. 例8-7 证明: 不同构的4阶无向树仅为如图8.20(a)(b). Proof 根据性质1, 4阶无向树恰有3条边,由握手定理知,其所有节点度数之和为6. 根据性质2, 4阶无向树至少2片叶. 若恰有2片叶,则其度数序列为2,2,1,1, 此时为图8-20(a)中的图. 若恰有3片叶,则其度数序列为3,1,1,1,为图8-20(b)中图.

(2)无向树的6个等价命题. Theorem 8-8 以下关于(n, m)无向图G的6个命题等价. (a) G是一棵无向树. (b) G不含有圈且m = n - 1. (c) G连通且m = n - 1. (d) G不含有圈但增加一条新边后得到一个且仅一个圈. (e) G连通但删除任意一条边后便不连通. (f) G的每一对节点有且仅有一条路径.

Proof (a)  (b) (b)  (c)(反证)设G有k(k  2)个连通分支, 它们都是无向树, 其节点数分别为 (c)  (d): 先证G不含圈, 对n归纳. 再证,添加一条边必有圈? (d)  (e): (e)  (f): (f)  (a):

3.生成树 左图中的无向图不是无向树,但可以得出其生成子图,它是无向树.

Def 8-4 设G = (V, E)是无向图,是无向树的生成子图T称为G的生成树(spanning tree), T中的边称为树枝(branch),其余边称为关于生成树T的弦(chord). Remark 一个无向图的生成树不一定唯一,但不是任意无向图都存在生成树. Theorem 8-9 设G是无向图,则G存在生成树的充要条件是G是连通图. Corollary n(n  1)阶连通图至少n – 1条边. 基本回路; 基本割集 线性空间.

4.最小生成树 设G是边赋权的连通无向图,在有些问题讨论中,不但要得出G的一棵生成树,而且要求生成树的权最小. Definition 8-5 设G是一个边赋权的连通无向图, G中权最小的生成树称为最小生成树(minimal spanning tree). 下面分别介绍求边赋权的连通无向图的最小生成树的几种算法.

算法1 克鲁斯卡尔(Kruskal, 1956)的避圈法 先将图G的m条边,按权从小到大的顺序排列:e1, e2, …, em. 按从左至右顺序 Step 1 选取第一条边 ,只要 不构成圈,令j ←1. Step 2 若 j = n – 1,则算法结束,否则转向Step 3. Step 3 假定已经选取了 ,再选取 ,只要 不构成圈. 令j ← j + 1, 转向Step 2.

Kruskal的避圈法的基本思想是: 以边的权从小到大的顺序,逐步选边,但必须去掉产生圈的边,即避开圈的产生,直至得到n - 1条边为止

算法2 普里姆(Prim, 1957)的割集法. 算法3 管梅谷(1975)的破圈法.

8.4 有向树 在8.3节讨论的是无向树, 本节讨论有向树, 特别是根树的有关内容, 它们在计算机算法设计及程序设计研究中都起着重要作用. 8.4 有向树 在8.3节讨论的是无向树, 本节讨论有向树, 特别是根树的有关内容, 它们在计算机算法设计及程序设计研究中都起着重要作用. 1.有向树的定义 Def 一个有向图, 在不考虑边的方向时是一棵无向树,则该有向图称为有向树(directed tree). 例子见书(P234).

2.根树 在有向树中,更常用的是根树,它能清楚地表示层次结构. 在编译程序中,用于表示源程序的语法结构,在数据库系统中用于表示信息的组织形式. Def 8-7 一个有向树,若恰有一个节点入度为0,而其余节点入度均为1,则该有向树称为根树(rooted tree). See Figure 8-27(a)(b).

(a)在根树中,入度为0的节点称为树根(root),出度为0的节点称为树叶(leaf),出度不为0的节点称为分枝节点,将不是根的分枝节点称为内点. 根树的一般画法: 根画在上方或下方(see Figure 8-27(a)(b)).

A B D C E G H I J F K L M

(a)为了方便,可以借助于家族树称呼根树中的节点 (a)为了方便,可以借助于家族树称呼根树中的节点. 若有向边(u, v)  E,则称u是v的父节点(parent), v是u的子节点(child). 同一个父节点的子节点称为兄弟节点(sibling). 节点的祖先(ancestor)是从根节点到该节点的路径上所经过的所有分枝节点. 从一个节点可以到达的任意节点都称为该节点的后代(offspring, descendants).

(c)从根节点到任意节点有且仅有一条路径. 从根节点到某个节点的路径的长度称为该节点的层或级(level). 其父节点在同一层的节点互为堂兄弟. 根树中节点的最大层次,称为根树的高度(height)或深度(depth). 在根树中, 所有树叶的层数之和称为该根树的外部路径长度,记为E; 所有内点的层数之和称为该根树的内部路径长度, 记为I.

Remark 关于根树中节点的层(level)的含义在有些数据结构中有所不同,它们将根节点称为第1层节点,其子节点称为第2层节点,依次类推. (d) Def 8-8 设G = (V, E)是一棵根树, v  V,由节点v及其所有后代导出的子图称为G的子根树(rooted subtree),可以简称为子树(subtree).

A B D C E G H I J F K L M

3.m叉树 在根树中,一个节点的出度可以称为元,或更形象地称为叉. 在数据结构中有称为“度”的,但容易与图论中节点的度数概念混淆. (1)m叉树的定义 Def 根树; 完全m叉树(complete m-tree): 图8-27(a); 正则m叉树 = 满m叉树(regular m-tree) ): 图8-27(b).

(2)m叉树的性质 Property 1 m叉树的第i层的节点至多为mi( i  0). (see below) Property 2 高度为h的m叉树至多有 mh+1 - 1(m  2)个节点. Property 3 一棵有l片树叶的m叉树的高度至少为logml.

Property 4 若一棵完全m叉树有l片树叶, t个分枝节点,则 (m – 1)t = l – 1. Hint mt条边, t – l个节点. Property 5 若2叉树有l片树叶,则出度为2的节点有l - 1个. Hint 由握手定理. Property 6 有l片树叶的完全2叉树有2l - 1个节点. Property 7 若完全2叉树有t个分枝节点,则E = I + 2t,其中E为外部路径长度,I为内部路径长度.

(3)叶赋权m叉树 下面讨论叶赋权叉树. Definition 设G = (V, E)是一棵m叉树,若的每一片树叶上都赋予一个非负实数,则称G为叶赋权m叉树. 可以将树叶理解为苹果,树叶上所赋的权理解为苹果的重量(see below).

Def 8-11 设G = (V, E)是一棵叶赋权m叉树,其l片树叶上的权分别为w1, w2,…, wl记根节点到权为wi的树叶节点的路径长度(即距离)为l(wi), 称 为m叉树的权,记为W(G).

下面仅讨论最优2叉树问题,它在解决某些判定问题是可以得到最佳判定算法. 所得结论可以推广到一般的最优叉树. Def 8-12 设G = (V, E)是一棵叶赋权2叉树,其l片树叶上的权分别为w1, w2,…, wl,在所有树叶数相同以及相应树叶上的权也相同的2叉树中,权最小的那棵2叉树称为最优2叉树或Huffman树.

赫夫曼(Huffman)在1952年首先给出一个求最优2叉树的有效算法,其基本思想是:

15 6 9 3 3 4 5 1 2

4.有序树 在根树中,对同一个节点的所有儿子节点是没有先后顺序的,这与家族树不太一致. 同时,在有些应用问题中,需要对同一个节点的所有儿子节点规定一个先后顺序,通常是从左至右顺序,这就是有序树. Def 8-13 设G是一棵根树,若对同一个节点的所有儿子节点规定一个先后顺序,则称G为有序树(ordered tree).

在有序树中,一个节点的最左边的儿子常称为该节点的长子. 在同一个父节点的所有子节点中,一个节点的右边第一个节点称为该节点的大弟. 如果一片森林中,每一棵根树都是有序树,且全体有序树的根也规定了先后顺序,则称该森林为有序森林(ordered forest),其中一棵有序树的右边第一棵有序树的根是前一棵有序树的根的大第. 例8-12 用有序树表示一个代数表达式? 关键是注意先后位置.

/ / || || - - b a c c a b

5.定位2叉树 对于2叉有序树,每个分枝节点至多两个儿子. 若对这两个儿子,包括只有一个儿子的情形,还根据实际情况确定了其左右位置,分别称为左儿子和右儿子,这就是定位2叉树. (1)定义 Def 设G是一棵有序2叉树,若对同一个节点的所有儿子(至多2个!)节点规定一个左右位置,则称G为定位2叉树(positional binary tree).

(红色?) 定位2叉树是数据结构中的2叉树(binary tree. 左儿子和右儿子? 左子树和右子树.

(2) Huffman编码 在定位2叉树中,与Huffman树密切相关的是Huffman编码. 现给出前缀及前缀码的定义. Def 设 是长度为n的符号串,则称子串 分别为 的长度为1, 2, …, n - 1的前缀. 设 是符号串组成的集合,若对于任意i  j均有 与 互不为前缀,则称A为前缀码(prefix code). 若 中只出现0或1两个符号, 则称A为二元前缀码(binary prefix code).

用二进制对计算机及通讯中使用的符号进行编码: (1)保证编码没有歧义,不会将字母传错; (2)二要保证码长要尽可能地短; (3)电文总长最短.

为了使电文总长尽可能地短, 使用Huffman编码即可. Huffman编码是使得电文总长最短的2进制前缀编码, 其叶上的权为传输各符号的频率, 所得到的Huffman树的权为传输一个符号需要使用的二进制数字的个数. 例8-14 将7个符号按其出现的频率0.2, 0.19, 0.18, 0.17, 0.15, 0.1, 0.01构造出其Huffman编码.

(3)遍历方式 遍历定位2叉树(traversing binary tree)有3种方式: (a)前序遍历: 根节点左子树右子树. (b)中序遍历: 左子树根节点右子树. (c)后序遍历: 左子树右子树根节点. (see below)

(a)前序遍历: (b)中序遍历: (c)后序遍历:

数据结构(如何遍历?): - + / a * e f b - c d

(4)有序森林与定位2叉树之间的转换 由于定位2叉树结构简单,经常将有序森林,特别是有序树,转换成定位2叉树. 我们以有序森林与定位2叉树之间的转换作为结束. 在有序森林与定位2叉树之间根据自然转换规则建立一一对应: (1)在F中u是v的长子,则在B中u是v的左儿子; (2)在F中u是v的大弟,则在B中u是v的右儿子. 例8-15 将图8-36(a)中的有序森林转换成定位2叉树.