树和二叉树的基本概念和相关计算

发布于:2023-01-20 ⋅ 阅读:(8) ⋅ 点赞:(0) ⋅ 评论:(0)

1、高度为h的m叉树的最多有多少个结点?

在这里插入图片描述
在上面的计算方法中,如果要想高度为h的m叉树的结点最多,只有当m叉树是满的情况,即所有的结点都有m个孩子!此时m叉树必然有最多的结点!(可以理解为满m叉树,满二叉树的概念是一样的)

2、高度为h的m叉树至少有几结点?

在这里插入图片描述

高度为h的m叉树,我们只是规定了m叉树中每个孩子结点的上限是多少,并没有规定说每个孩子结点的下限是多少,所以对于高度为h的m叉树,要想高度最小,那么至少需要h个结点!也即每个结点只需要有一个孩子结点即可!此时高度为h的m叉树的结点必然是最少的!

3、高度为h的度为m的树至少有多少个结点?

在这里插入图片描述
对于高度为h,度为m的树,题目中并没有说该树 是多少叉树,那么假设该树中只有一个结点有m个孩子(度为m的树 ),其余的h-1层全是每个结点只有一个孩子,那么这种情况下至少有 h -1 + m个结点!

4、具有n个结点的m叉树的最小高度是?

解题思路:高度最小的情况是n个结点构成的树是满的,即每一个结点拥有m个孩子!此时树的高度最宽!那么n个结点构成的m叉树的高度最小!
在这里插入图片描述

5、具有n个结点的m叉树的最大高度是?

具有n个结点的m叉树,此时并没有限制m叉树中每个结点最少有几个孩子,所以直接让每个结点就只有一个孩子,这样做的情况下n个结点的m叉树的最大高度是n

6、若有n个结点度为m的树,当只有最后一层有m个节点,其余层均只有一个节点,在所有含有n个节点的度为m的树中一定是最高的,为 n - m + 1

6 、结点数 = 总度数(分支数)+ 1(最简单的是自己画个树验证结论的正确性)

7、度为m的树和m叉树的区别

在这里插入图片描述
其中度为m大的树,规定了树的度为m,也即树中存在一个结点有三个孩子结点的情况!
m叉树,允许所有结点的度都可以是小于m,甚至是空树!