php怎么做视频网站,手机上的网页游戏,保定网站建设解决方案,安卓软件开发目录 5.1树的基本概念
5.1.2基本术语
【森林中树的数量、边数和结点数的关系#xff08;2016#xff09;】
5.1.3树的性质
【树中结点数和度数的关系的应用#xff08;2010、2016#xff09;】
【指定结点数的三叉树的最小高度分析#xff08;2022#xff09;】 5.1…目录 5.1树的基本概念
5.1.2基本术语
【森林中树的数量、边数和结点数的关系2016】
5.1.3树的性质
【树中结点数和度数的关系的应用2010、2016】
【指定结点数的三叉树的最小高度分析2022】 5.1树的基本概念
5.1.2基本术语
下面结合图5.1中的树来说明一些基本术语和概念。 1祖先、子孙、双亲、孩子、兄弟和堂兄弟。祖先考虑结点K从根A到结点K的唯一路径上的所有其他结点称为结点K的祖先。
子孙如结点B是结点K的祖先而K是B的子孙结点B的子孙包括EFK.L。
双亲路径上最接近结点K的结点E称为K的双亲而K为E的孩子。根A是树中唯一没有双亲的结点。
兄弟有相同双亲的结点称为兄弟如结点K和结点L有相同的双亲E即K和L为兄弟。
堂兄弟双亲在同一层的结点互为堂兄弟结点G与EEHIJ互为堂兄弟。
2结点的度和树的度。 树中一个结点的孩子个数称为该结点的度树中结点的最大度数称为树的度。如结点B的度为 2结点D的度为3树的度为3。
3分支结点和叶结点。 度大于0的结点称为分支结点(又称非终端结点)度为0(没有孩子结点)的结点称为叶结点(又称终端结点)。在分支结点中每个结点的分支数就是该结点的度。
4)结点的深度、高度和层次。 结点的层次从树根开始定义根结点为第1层它的孩子为第2层以此类推。
结点的深度就是结点所在的层次。
树的高度(或深度)是树中结点的最大层数。图5.1中树的高度为4。
结点的高度是以该结点为根的子树的高度。
5有序树和无序树。 树中结点的各子树从左到右是有次序的不能互换称该树为有序树否则称为无序树。
假设图 5.1为有序树若将子结点位置互换则变成一棵不同的树。
6路径和路径长度。 树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成的而路径长度是路径上所经过的边的个数。 注意因为树中的分支是有向的即从双亲指向孩子所以树中的路径是从上向下的同一双亲的两个孩子之间不存在路径。 7森林
【森林中树的数量、边数和结点数的关系2016】
森林是 m(m≥0)棵互不相交的树的集合。森林的概念与树的概念十分相近因为只要把树的根结点删去就成了森林。反之只要给m棵独立的树加上一个结点并把这 m棵树作为该结点的子树则森林就变成了树。 注意上述概念无须刻意记忆根据实例理解即可。考研时不大可能直接考查概念而都是结合具体的题目考查。做题时遇到不熟悉的概念可以翻书练习得多自然就记住了。 5.1.3树的性质
树具有如下最基本的性质:
【树中结点数和度数的关系的应用2010、2016】
1树的结点数n等于所有结点的度数之和加1。 结点的度是指该结点的孩子数量每个结点与其每个孩子都由唯一的边相连因此树中所有结点的度数之和等于树中的边数之和。
树中的结点(除根外)都有唯一的双亲因此结点数 n等于边数之和加1即所有结点的度数之和加1。
2度为m的树中第i层上至多有 个结点(i 1)。 第1层至多有1个结点(即根结点)第2层至多有m个结点第3层至多有㎡个结点以此类推。使用数学归纳法可推出第i层至多有个结点。
3高度为h的 m 叉树至多有个结点。 当各层结点数达到最大时树中至多有个结点。
【指定结点数的三叉树的最小高度分析2022】
4度为 m、具有n个结点的树的最小高度h为 为使树的高度最小在前 h-1 层中每层的结点数都要达到最大前 h-1 层最多有个结点,前h层最多有个结点。因此即 ,
解得 。
5度为 m、具有n个结点的树的最大高度h为n-m1。 由于树的度为 m因此至少有一个结点有 m个孩子它们处于同一层。为使树的高度最大其他层可仅有一个结点因此最大高度(层数)为n-m1。由此也可逆推出高度为 h、度为m的树至少有 hm-1 个结点。
