资讯

历史

科技

环境与自然

成长

游戏

财经

文学与艺术

美食

健康

家居

文化

情感

汽车

三农

军事

旅行

运动

教育

生活

星座命理

树中结点，高度及度的计算

创作时间:

作者:

@小白创作中心

树中结点，高度及度的计算

引用

CSDN

https://blog.csdn.net/Cidom/article/details/140445198

本文主要讲解了树中结点、高度及度的计算方法，包括m叉树最小高度的计算、树的相关概念区分、度的计算方法以及二叉树的性质和计算。文章内容较为专业，主要面向计算机科学和数据结构的学习者，具有较高的学术价值和实用价值。

计算m叉树的最小高度

为了计算m叉树的最小高度，我们首先需要了解每一层的结点数是如何增长的。具体来说：

第一层有1个结点
第二层有m个结点
第三层有m^2个结点
...
第h层有m^(h-1)个结点

因此，m叉树应满足：每层都应为满结点。设结点数为n，则n ≤ 1 + m + m^2 + ⋯ + m^(h-1)。利用数列前n项和公式：

等差数列前 n 项和 : S_n = \frac{n(a_1+a_n)}{2}=\frac{na_1+n(n+1)}{2}d
等比数列前 n 项和 : S_n = \frac{a_1(1-q^n)}{1-q}

我们可以得到：

n ≤ \frac{1·(1-m^{h})}{1-m} ⟹ nm-n+1 ≤ m^{h-1}

两边取对数得：

h = \lceil \log_m(nm-n+1) \rceil

树易混淆概念

在讨论树的结构时，有几个容易混淆的概念需要特别注意：

树的高度：是从下往上数
树的深度：从上往下数
树的度：各结点的度的最大值
如上面树的度= 3，是结点D

度的计算

树中结点数等于所有结点的度数之和加上1（根节点）。

度为m的树中第i层至多有m^(i-1)个结点，即满m叉树的情况。

例1：

已知一棵树度为4的树中，度为0, 1, 2, 3的结点数分别为14, 4, 3, 2，求该树的结点总数n和度为4的结点个数，并给出推导过程。

解：设n_i表示度为i的结点，则总结点数n：

① n = n_0 + n_1 + n_2 + n_3 + n_4 = 23 + n_4

且树种结点数等于所有结点度数之和+1

② n = n_0·0 + n_1·1 + n_2·2 + n_3·3 + n_4·4 = 0·14 + 1·4 + 2·3 + 3·2 + 4·n_4 + 1 = 17 + 4n_4

故 17 + 4n_4 = 23 + n_4, 得 n_4 = 2, n = 25

∴ 该树总结点数为25, n_4为2

例2：

已知一棵度为m的树中，有n_1个度为1的结点，有n_2个度为2的结点...有n_m个度为m的结点，问该树有多少个叶结点。

解：树中结点数等于所有结点的度数之和加上1：

即n = n_1 + 2n_2 + ⋯ + mn_m + 1 = \sum_{i=1}^{m}in_i + 1

且总结点数n = n_0 + n_1 + ⋯ + n_m, 即

n_0 = \sum_{i=1}^{m}in_i - (n_1 + n_2 + ⋯ + n_m) + 1

= \sum_{i=1}^{m}in_i - \sum_{i=1}^{m}n_i + 1

= 1 + \sum_{i=1}^{m}n_i(i-1)

二叉树易混淆知识点

满二叉树：一棵高度为h，且含有2^h-1个结点的二叉树称为满二叉树，即树中每层含有最多的结点。
完全二叉树：当且仅当其每个结点都与高度为h的满二叉树中编号为1~n的结点一一对应时，称为完全二叉树。

完全二叉树特点：

只有最后两层可能有叶子结点；
且最多只有一个度为1的结点。
按层序从1开始编号，结点i的左孩子为2i，右孩子为2i+1；结点i的父结点为[i/2]
i ≤ [n/2]为分支结点，i > [n/2]为叶子结点，即若n为奇数，则每个分支结点都有左右孩子；若为偶数，则编号最大的分支结点(n/2)只有左孩子，没有右孩子，其余分支结点左、右孩子都有。
一个结点如果有孩子，一定是左孩子。
结点i所在层次(深度)，为⌊log_2i⌋+1

注意：满二叉树是完全二叉树，而完全二叉树不一定是满二叉树。