时间戳

首页 > 解决方案 > 如何计算有根树中节点和叶子的最小和最大数量？

graph - 如何计算有根树中节点和叶子的最小和最大数量？

问题描述

我正在寻找高度为 h 和度数为 d 的有根树中节点和叶子的最小和最大数量。

我猜叶子的最小数量总是1（如果h> = 2）。节点的最大数量应该是 G^(h-2)，叶子应该是 G^(h-1)。对于最少数量的节点，我一无所知。

我是正确的还是我错过了什么？

标签： graphtreecomputer-sciencedirected-graph

解决方案

鉴于树的高度为 h 和度数为 d，以下适用。

最小节点数

要构建一个高度为 h 且节点数尽可能少的树，您会希望每个节点只有一个子节点。因此，您将需要 h 个节点。

最大节点数

要使用尽可能多的节点，您会希望每个节点（除了叶子）都有尽可能多的子节点，即 d 子节点。这看起来像：

level      nodes at level 

  1              1    (d^0)
  2              d    (d^1)
  3              d^2
  4              d^3

所以节点的数量是一个总和

num_nodes = d^0 + d^1 + d^2 + d^3 + ....

这是一个几何和，可以计算为：

num_nodes = (1 - d^h)/(1 - d)

推荐阅读