二叉树的节点数与高度之间的关系

在本节中，我们将学习关于二叉树的高度与节点数之间关系的大量案例。为了理解这个概念，我们需要学习二叉树及其属性。我们还将学习最小和最大节点数。

二叉树

二叉树可以描述为节点和顶点的集合。它包含一个根节点，它是树中的最顶层节点。在树中，我们可以定义节点的层级。根节点始终位于 Level 0。二叉树中的所有节点最多可以包含 2 个子节点。如果根节点有子节点，则它们位于 level 1。

例如： 在此示例中，我们将使用 5 个节点构建一个 level 2 的二叉树。

在上面的树中，总共有 5 个节点，根节点的高度为 0。根节点的子节点的高度为 1。

最小和最大节点数

最小和最大节点数描述如下：

最小节点数

我们已经看到，我们需要至少 1 个节点才能构建一个具有 level n 的二叉树。我们可以通过公式：**n - 1** 来计算二叉树中具有 level n 的**最小节点数**。链表数据结构的行为与二叉树相同。

定理： 可以使用以下定理来查找最小节点数。

假设有一棵高度为 n（n >= 0）的二叉树 T。在这种情况下，T 将包含至少 n + 1 个节点。

最大节点数

要构建具有 level n 的二叉树中的最大节点数，我们需要确保该树的所有内部节点都具有两个子节点。该树的所有叶节点必须位于 level n。

例如： 在此示例中，我们在 level 0 处有一个根节点。我们在 level 1 处有两个节点，它们是根节点的子节点。同样，我们可以看到我们在 level 2 处有 4 个节点，它们是 level 1 处节点的子节点。

从上面的示例可以看出，节点数从前一个级别到下一个级别翻倍。这就是为什么每个内部节点都有两个子节点的原因。以下公式用于确定 level n 的最大节点数：

这种类型的二叉树称为满二叉树。

定理： 可以使用以下定理来查找最大节点数。

假设有一棵高度为 n（n >= 0）的二叉树 T。在这种情况下，T 将最多有 2ⁿ⁺¹ -1 个节点。

根据节点数计算最大和最小高度

二叉搜索树的高度可以描述为从根节点到树中任何叶节点的路径中最长的那一条。假设有一个包含 n 个级别的二叉树。因此，在此二叉树中，**最大高度**将是“n-1”，而**最小高度**将是**“floor (log2n)”**。现在我们有两个图来理解二叉树的高度，描述如下：

在上面的二叉树的右侧，有 5 个节点，其高度为 floor (log 25) = 2。在此图中，从根节点 5 到节点 2 的最长路径是 n - 1。这里右侧图像包含 3 个级别（级别 0、级别 1 和级别 2）。这意味着总共有 3 个级别。因此 n = 3，最小高度为 3 - 1 = 2。因此，我们可以说右图中二叉树的高度为 2。在左侧图像中，从根节点到节点 1 的最长路径是 n - 1。在左侧，总共有 5 个级别。因此，n = 5，最小高度为 5 - 1 = 4。因此，左侧图像中二叉树的高度为 4。

根据高度计算最小和最大节点数

假设有一个高度为 h 的二叉树。因此，在此二叉树中，最小节点数将是 h + 1（在右偏和左偏二叉树的情况下）。

例如： 在下图的左侧，二叉树显示高度为 2，包含 3 个节点。

假设有一个高度为 h 的二叉树。如果树的所有级别都已完全填满，在这种情况下，节点总数将由以下公式确定：

例如： 在上图中，二叉树的右侧显示高度为 2，包含 2 ^ (2 + 1) - 1 = 7 个节点。

二叉搜索树

二叉搜索树有两个子节点，即左子节点和右子节点。子节点的左值必须小于父节点的值，而子节点的右值必须大于父节点的值。

根据节点数计算最小和最大高度

假设有一个包含 n 个节点的二叉搜索树。因此，在此二叉搜索树中，**最大高度**将是“n-1”，而**最小高度**将是**“ceil (log2n)”**。

根据高度计算最小和最大节点数

假设有一个高度为 h 的二叉搜索树。因此，在此二叉搜索树中，最小节点数将是 h + 1（在右偏和左偏二叉搜索树的情况下）。

假设有一个高度为 h 的二叉搜索树。如果树的所有级别都已完全填满，在这种情况下，节点总数将由以下公式确定：

总之，我们可以说二叉树和二叉搜索树的规则是相同的，并且我们也可以以相同的方式可视化它们。