离散数学7.8根数及其应用 习题PPT课件一等奖新名师优质课获奖比赛公开课.ppt

文档介绍：该【离散数学7.8根数及其应用 习题PPT课件一等奖新名师优质课获奖比赛公开课 】是由【书犹药也】上传分享，文档一共【42】页，该文档可以免费在线阅读，需要了解更多关于【离散数学7.8根数及其应用 习题PPT课件一等奖新名师优质课获奖比赛公开课 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。 根树及其应用(Rooted Trees and Its Applications)
有向树(directed tree )
m叉树(m-ary tree )
最优二叉树(optimal binary tree )
有向树(directed tree )
图
有向树(directed tree )
定义 一种有向图， 若不考虑边的方向， 它是一棵树， 则这个有向图称为有向树。 一棵有向树， 假如恰有一种结点的入度为０， 其他所有结点的入度都为１， 则称为根树， 其中入度为０的结点称为树根， 出度为０的结点称为树叶， 出度不为０的结点称为分枝点或内点。
(a)表达一棵根树， 其中v1为树根， v1， v2， v3为分枝点， 其他结点为树叶。 习惯上我们把根树的根画在上方， 叶画在下方。 这样就可以省去根树的箭头， (b)。 在根树中， 称从树根到结点v的距离为该点的层次。 ， v1的层次为０， v2、 v3的层次为１， 其他结点的层次均为２。 我们用家族关系表达根树中各结点的关系。
图 根树示例
在根树中， 若从vi到vj可达， 则称vi是vj的祖先， vj是vi的后裔； 又若〈vi， vj〉是根树中的有向边， 则称vi是vj的父亲， vj是vi的儿子； 假如两个结点是同一结点的儿子， 则称这两个结点是兄弟。
在根树中， 任一结点v及其v的所有后裔和从v 出发的所有有向路中的边构成的子图称为以v为根的子树。 根树中的结点u的子树是以u的儿子为根的子树。
在现实的家族关系中， 兄弟之间是有大小次序的， 为此我们又引入有序树的概念。
假如在根树中规定了每一层次上结点的次序， 这样的根树称为有序树。 我们在有序树中规定同一层次结点的次序是从左至右。
m叉树(m-ary tree )
在树的实际应用中， 我们常常研究完全m叉树。
在根树中， 若每个结点的出度不不小于或等于m， 则称这棵树为m叉树。 假如每个结点的出度恰好等于０或m， 则称这棵树为完全m叉树。 二叉树(binary tree )的每个结点v 至多有两棵子树， 分别称为v的左子树和右子树。
图
【】甲、 乙两人进行球赛， 规定三局两胜。 （图中结点标甲者表达甲胜， 标乙者表达乙胜）， 这是一棵完全二叉树。