哈尔滨理工大学：《离散数学 Discrete Mathematics》课程教学资源（PPT课件讲稿）23 根树及其应用

7-8根树及其应用

7-8 根树及其应用

根树 1、有向树 定义7-8.1如果一个有向图在不考虑边的方向时 是一棵树,那么,该有向图称为有向树。 He

一、根树 1、有向树 定义7-8.1 如果一个有向图在不考虑边的方向时 是一棵树，那么，该有向图称为 有向树

2、根树 定义7-8.2一棵有向树,如果恰有一个 结点的入度为0,其余所有结点的入度都为1, 则称为根树( Rooted tree)。入度为0的结点称 为T的树根。出度为0的结点称为树叶,出度 不为0的结点称为分支点或内点。 根树的画法有:树根在下,向上生长; 树根在上,向下生长

2、根树 定义7-8.2 一棵有向树,如果恰有一个 结点的入度为0，其余所有结点的入度都为1, 则称为根树(rooted tree)。入度为0的结点称 为T的树根。出度为0的结点称为树叶，出度 不为0的结点称为分支点或内点。 根树的画法有：树根在下，向上生长； 树根在上，向下生长

习惯把有向树的根画在最上方,边的箭头全指 向下,则可以省略全部箭头,树根到一个结点的有 向通路的长度称为该点的层数。所有结点的最大层 数称为树高。 8 10 U10

习惯把有向树的根画在最上方，边的箭头全指 向下，则可以省略全部箭头，树根到一个结点的有 向通路的长度称为该点的层数。所有结点的最大层 数称为树高

3、子树 定义7-83:任一结点v及其后代导出的子图 称为根树的子树。 定义783根树包含一个或多个结点,这些结 点中的某一个称为根,其他所有结点被分成有限个 子根树

3、子树 定义7-8.3：任一结点v及其后代导出的子图 称为根树的子树。 定义7-8.3 根树包含一个或多个结点,这些结 点中的某一个称为根,其他所有结点被分成有限个 子根树

在有向树中,结点的出现次序是没有意义的。 但实际应用中,有时要给出同一级中结点的相对 次序,这便导出有序树的概念。 4、有序树:在根树中规定了每一层上结点的次 序,称为有序树

在有向树中，结点的出现次序是没有意义的。 但实际应用中，有时要给出同一级中结点的相对 次序，这便导出有序树的概念。 4、有序树：在根树中规定了每一层上结点的次 序，称为有序树

为表示结点间的关系,有时借用家族中的术语。 定义在以v0为根的树中, (1)v1,V2,,v称为v的儿子,v称为它们的 父亲。v,v同为一顶点v的儿子时,称它们为兄弟 (2)顶点间的父子关系的传递闭包称为顶点间 的祖孙关系。即当v为v1(=1,2,,,41)的父亲时, v1是v的祖先,Vv为v1的子孙。 (3)根树T自身及以它的树根的子孙为根的根树 (T的子图),均称为T的子树(bre),后者又 称为T的真子树

为表示结点间的关系，有时借用家族中的术语。 定义 在以v0为根的树中， （1）v1，v2 ,…，vk称为v0的 儿子，v0称为它们的 父亲。vi，vj 同为一顶点v的儿子时，称它们为兄弟。 （2）顶点间的父子关系的传递闭包称为顶点间 的祖孙关系。即当vi为vi+1 (i = 1, 2,…, l-1) 的父亲时， v1是vl的祖先，vl为v1的子孙。 （3）根树T自身及以它的树根的子孙为根的根树 （T的子图），均称为T的子树（subtree），后者又 称为T的真子树

5、m叉树 定义7-84:在根树中若每个结点的出度均≤m, 则称T为m元树(m叉树),若每个分支点的出度恰好 等于m,则称T为m叉完全树,若T的所有树叶的层数 均相同,则称T正则m元树。 若m元树是有序的,则称T为m元有序树,若m 元完全树是有序的则称T为完全m元有序树,若m元 正则树是有序的,则称T为m元正则有序树。 当m=2时,称为二元树,二元有序树的每个结 点至多有两个儿子,其序按左右分,分别为左儿子, 右儿子,任一分支点最多有两棵子树,称为左子树 和右子树

5、m叉树 定义7-8.4：在根树中若每个结点的出度均≤m， 则称T为m元树(m叉树)，若每个分支点的出度恰好 等于m，则称T为m叉完全树，若T的所有树叶的层数 均相同，则称T正则m元树。 若m元树是有序的，则称T为m元有序树，若m 元完全树是有序的则称T为完全m元有序树，若m元 正则树是有序的，则称T为m元正则有序树。 当m=2时，称为二元树，二元有序树的每个结 点至多有两个儿子，其序按左右分，分别为左儿子， 右儿子，任一分支点最多有两棵子树，称为左子树 和右子树

当m=2时,便可得到常用的二叉树、完全二 叉树和正则二叉树。不难看出,二叉树中的每个 结点v,至多有两个子树,分别称为v的左子树和 右子树。若v只有一个子树,则称它为左子树或右 子树均可。在二叉树的图形表示中,v的左子树画 在v的左下方,v的右子树画在v的右下方

当m=2时，便可得到常用的二叉树、完全二 叉树和正则二叉树。不难看出，二叉树中的每个 结点v，至多有两个子树，分别称为v的左子树和 右子树。若v只有一个子树，则称它为左子树或右 子树均可。在二叉树的图形表示中，v的左子树画 在v的左下方，v的右子树画在v的右下方

有很多实际应用,可用二叉树或m叉树表示。 可以指出,按下面算法,任何一棵有序树均能转 成二叉树。其算法是: (1)除最左边的分枝结点外,删去所有从每一个结 点长出的分枝。在同一级中,兄弟结点之间用从 左到右的弧连接 (2)选取直接位于给定结点下面的结点作为左儿子, 与给定结点位于同一水平线上且紧靠它的右边结 点作为右儿子,如此类推 上述算法能够推广到有序森林上去

有很多实际应用，可用二叉树或m叉树表示。 可以指出，按下面算法，任何一棵有序树均能转 成二叉树。其算法是： (1) 除最左边的分枝结点外，删去所有从每一个结 点长出的分枝。在同一级中，兄弟结点之间用从 左到右的弧连接。 (2) 选取直接位于给定结点下面的结点作为左儿子， 与给定结点位于同一水平线上且紧靠它的右边结 点作为右儿子，如此类推。 上述算法能够推广到有序森林上去