高度爲5的二叉樹頂點的最小數量5

Question

什麼是求高度爲5的二叉樹（不是完整的二叉樹）所需的最小頂點數的公式？

Answer 1

二叉樹的高度不能大於樹中節點或頂點的數量。所以是的，一個高度爲5的二叉樹所需的最小頂點數將是5.另外，它們之間必須有n-1條邊。你可以想象一個單一系列的連接節點，這基本上是你得到的。

或者，完整的二叉樹是一棵二叉樹，其中每個內部頂點恰好有兩個孩子。這意味着一個具有n個內部頂點的二叉樹具有2n + 1個頂點，2n個邊和n + 1個葉。

Answer 2

高度爲n的二叉樹中的最小頂點數（沒有進一步約束）始終爲n。

證明：

1. 如果有超過n個節點是少，樹就不會是一個有效的二叉樹（我想我不需要進一步說明了這一點）
2. 如果有超過n個節點，這意味着至少有一個節點有一個兄弟（鴿子原理），它可以從樹中取出，並且會產生一個有效的，更小的二叉樹，所以我們知道這棵樹不是最小的，這反對我們對最小樹的假設。 - >二叉樹T是最小的 - > T有n個節點