7-8 根树及其应用.ppt

7-8 根树及其应用 上节重点讨论无向树。 本节将简单地讨论有向图中的树。 要求： 掌握6个定理 重点掌握最优二叉树的构造方法。 一、根树的基本概念 1、有向树 定义7-8.1 如果一个有向图在不考虑边的方向时是一棵树，那么该有向图称为 有向树。 2、根树 定义7-8.2 一棵有向树，如果恰有一个结点的入度为0，其余所有结点的入度都为1，则称为根树(rooted tree)。入度为0的结点称为T的树根。出度为0的结点称为树叶，出度不为0的结点称为分枝点或内点。 3、子树 定义7-8.3 任一结点v及其后代导出的子图称为根树的子树。 在有向树中，结点的出现次序是没有意义的。但实际应用中，有时要给出同一级中结点的相对次序，这便导出有序树的概念。 4、有序树 在根树中规定了每一层上结点的次序，称为有序树。 为表示结点间的关系，有时借用家族中的术语。 定义 在以v0为根的树中， （1）若从a到b有一条边，则结点b称为a的“儿子”，或称a为b的“父亲”。例：v1，v2称为v0的 儿子，v0称为它们的父亲。vi，vj 同为一顶点v的儿子时，称它们为兄弟。 （2）当vi为vi+1 (i = 1, 2,…, k-1) 的父亲时，v1是vk的祖先，vk为v1的子孙。 （3）根树T自身及以它的树根的子孙为根的根树（T的子图），均称为T的子树（subtree），后者又 称为T的真子树。 1、m叉树 定义7-8.4 在根树中若每个结点的出度均≤m，则称T为m叉树(m元树)。若每个分枝点的出度恰好等于m或零，则称T为完全m叉树，若T的所有树叶的层数均相同，则称T为正则m叉树。 若m叉树是有序的，则称T为m叉有序树。若完全m叉树是有序的，则称T为完全m叉有序树。若正则m叉树是有序的，则称T为正则m叉有序树。 2、二叉树 当m=2时，称为二叉树，二叉有序树的每个结点v至多有两个儿子，其序按左右分，分别为左儿子，右儿子，任一分枝点最多有两棵子树，称为左子树和右子树。 若v只有一个子树，则称它为左子树或右子树均可。在二叉树的图形表示中，v的左子树画在v的左下方，v的右子树画在v的右下方。 3、m叉树改为二叉树的方法 (1) 除最左边的分枝结点外，删去所有从每一个结点长出的分枝。在同一级中，兄弟结点之间用从左到右的弧连接。 (2) 选取直接位于给定结点下面的结点作为左儿子，与给定结点位于同一水平线上且紧靠它的右边结点作为右儿子，如此类推。 上述算法能够推广到有序森林上去。 三、最优树 二叉树的一个重要应用就是最优树问题。 给定一组数w1，w2，…，wn。令一棵二叉树有n个叶结点，并对它们分别指派w1，w2，…，wn作为权，则该二叉树称为加权二叉树。 例1 根据上述两个定理，求一棵有n个权的最优树，可简化为求一棵有n-1个权的最优树，而这又可简化为求一棵有n-2个权的最优树，依此类推。 具体作法是：首先找出两个最小的权值，设w1和w2。然后对n-1个权w1+w2，w3，…，wn求作一棵最优树，并且将这棵树中的结点 w1+w2 代之以 ，依此类推。 例2: 已知权值 W={ 5, 6, 2, 9, 7 } 7 9 2 6 5 7 9 6 7 2 5 7 2 5 9 13 7 6 0 0 0 0 1 1 1 1 00 01 10 110 111 W(T)= 6?2+7?2+9?2+5?3+2?3 =65 7 2 5 9 13 7 6 6 7 13 2 5 7 9 16 29 * 离散数学Discrete Mathematics 学习本节要熟悉如下术语（18个）： 有向树、 根树、 有序树、 结点的层次、 子根树、 m叉树、 完全m叉树、 分枝点、 根、 叶、 正则m叉树、 二叉树、 内部通路长度、 外部通路长度、 通路长度、 加权二叉树、 最优树、 前缀码 根树的画法有：树根在下，向上生长； 树根在上，向下生长。 习惯把有向树的根画在最上方，边的箭头全指向下，则可以省略全部箭头。 树根到一个结点的有向通路的长度称为该结点的层数。所有结点的最大层数称为树高。 定义7-8.3 根树包含一个或多个结点，这些结点中的某一个称为根，其他所有结点被分成有限个子根树。 二、二叉树 例 2叉有序树 2叉有序完全树 2叉有序完全正则树 (1) 2 2 1 1 1 (2) 2 2 2 1 1 1 (3) 2 2