[理学]16 树2.pdf

离散数学 第16章 树 第16章 树 16.3 根树及其应用 设D 是有向图，若D 的基图是无向树，则称D 为有向树。 在所有的有向树中，根树最重要，所以我们只讨论根树。 二叉树的应用 2 根树的定义 定义16.6 T是n (n ≥2)阶有向树， (1) T为根树— T中有一个顶点入度为0，其余顶点的入度均为1 (2) 树根——入度为0的顶点 (3) 树叶——入度为1，出度为0的顶点 (4) 内点——入度为1，出度不为0的顶点 (5) 分支点——树根与内点的总称 (6) 顶点v的层数——从树根到v的通路长度 (7) 树高—— T中层数最大顶点的层数 (8) 平凡树也是根树 3 根树的画法 树根放上方，省去所有有向边上的箭头。 树叶——8片 内点—— 6个 分支点—— 7个 高度—— 5 4 家族树 常将根树看成家族树，家族中成员之间的关系如下定义。 定义16.7 设T为一棵非平凡的根树， ∀v 、v ∈V(T) ，若v 可达v ，则称v 为v 的祖先，v 为v 的后代。 i j i j i j j i 若v 邻接到v （即v ,v ∈E(T) ），则称v 为v 的父亲，而v 为v i j i j i j j i 的儿子。 若v 、v 的父亲相同，则称v 与v 是兄弟。 j k j k 定义16.8 设v为根树T 中任意一顶点，称v及其后代的导出子图为 以v为根的根子树。 5 根树的分类 (1)设T为根树，若将T中层数相同的顶点都标定次序， 则称T为有序树。 (2)分类：根据根树T中每个分支点儿子数以及是否有序 r叉树——每个分支点至多有r个儿子 r叉有序树——r叉树是有序的 r叉正则树——每个分支点恰有r个儿子 r叉正则有序树——r叉正则树是有序的 r叉完全正则树——树叶层数均为树高的r叉正则树 r叉完全正则有序树——r叉完全正则树是有序的 6 例.英语句子“The big elephant ate the peanut”可 以图解为下图，称之为这个英语句子的语法树。可见，句 子的语法树是一棵有序树。 句子 主语 谓语 冠词 形容词 名词 动词 直接宾语 The big elephant ate 冠词 名词 图 9.2.3 the peanut 7 最优二叉树 定义16.9