离散数学(7.8根数及其应用 习题).ppt

* 7.6 根树及其应用(Rooted Trees and Its Applications) 7.6.1 有向树(directed tree ) 7.6.2 m叉树(m-ary tree ) 7.6.3 最优二叉树(optimal binary tree ) 7.6.1 有向树(directed tree ) 图 7.6.1 7.6.1 有向树(directed tree ) 定义 7.6.1 一个有向图， 若不考虑边的方向， 它是一棵树， 则这个有向图称为有向树。 一棵有向树， 如果恰有一个结点的入度为０， 其余所有结点的入度都为１， 则称为根树， 其中入度为０的结点称为树根， 出度为０的结点称为树叶， 出度不为０的结点称为分枝点或内点。 如图7.6.2(a)表示一棵根树， 其中v1为树根， v1， v2， v3为分枝点， 其余结点为树叶。 习惯上我们把根树的根画在上方， 叶画在下方。 这样就可以省去根树的箭头， 如图7.6.2(b)。 在根树中， 称从树根到结点v的距离为该点的层次。 这样对图7.6.2中的根树， v1的层次为０， v2、 v3的层次为１， 其余结点的层次均为２。 我们用家族关系表示根树中各结点的关系。 图 7.6.2 根树示例 定义7.6.2 在根树中， 若从vi到vj可达， 则称vi是vj的祖先， vj是vi的后代； 又若〈vi， vj〉是根树中的有向边， 则称vi是vj的父亲， vj是vi的儿子； 如果两个结点是同一结点的儿子， 则称这两个结点是兄弟。 定义7.6.3 在根树中， 任一结点v及其v的所有后代和从v 出发的所有有向路中的边构成的子图称为以v为根的子树。 根树中的结点u的子树是以u的儿子为根的子树。 ? 在现实的家族关系中， 兄弟之间是有大小顺序的， 为此我们又引入有序树的概念。 定义7.6.4 如果在根树中规定了每一层次上结点的次序， 这样的根树称为有序树。 我们在有序树中规定同一层次结点的次序是从左至右。 7.6.2 m叉树(m-ary tree ) 在树的实际应用中， 我们经常研究完全m叉树。 定义7.6.5 在根树中， 若每个结点的出度小于或等于m， 则称这棵树为m叉树。 如果每个结点的出度恰好等于０或m， 则称这棵树为完全m叉树。 二叉树(binary tree )的每个结点v 至多有两棵子树， 分别称为v的左子树和右子树。 图 7.6.3 【例7.6.1】甲、 乙两人进行球赛， 规定三局两胜。 图7.6.4表示了比赛可能出现的各种情况（图中结点标甲者表示甲胜， 标乙者表示乙胜）， 这是一棵完全二叉树。 图7.6.4 定理7.6.1 在完全m叉树中， 若树叶数为 t， 分枝点数为 i， 则 (m-1)i＝t-１ 证明: 由假设知， 该树有 i+t 个结点， 由定理7.5.2知， 该树边数为 i+t -１。 因为所有结点出度之和等于边数所以根据完全m叉树的定义知， mi＝ i+t -１ 即 (m-1)i＝t-１ 【例7.6.2】假设有一台计算机， 它有一条加法指令， 可计算 3 个数之和。 如果要求 9 个数x1， x2， …， x9之和， 问至少要执行几次加法指令？ 解: 用 3 个结点表示 3 个数， 把 9 个数看成树叶， 将表示 3 数之和的结点作为它们的父亲结点。 这样本问题可理解为求一个完全三叉树的分枝点的个数问题。 由定理7.6.1知， 有 (３-１)i＝９-１ 得 i＝４ 所以要执行 4 次加法指令。 图7.6.5表示了两种可能的顺序。 图 7.6.5 【例7.6.3】设有２８盏灯，拟公用一个电源，则至少需要多少个４插头的接线板 ? ? 解:把 28盏灯看成树叶， 将４插头的接线板看成分枝点, 这样本问题可理解为求一个完全四叉树的分枝点的个数 i的问题。 由定理7.6.1知， 有 (4-１)i＝28-１ 得 i＝9 所以至少需要9个４插头的接线板 。 【例7.6.4】 8 枚硬币问题。 若有 8 枚硬币a， b， c， d，