二叉搜索樹中的葉子數量

Question

是否有一種方法可以準確知道二叉搜索樹中有多少葉子？像有沒有一些公式總是找出來？例如，如果BST中有100個節點，您可以使用該值（n = 100）來查找有多少葉子？

Answer 1

It depends on the type of tree in question.

對於任何一般的「二叉搜索樹」，沒有進一步的說明或信息，我們無法知道。

可以從

• 只是一個單一的（1）葉（其中除了最後所有的節點都只有1子節點 - 實際上是一個鏈表）在任何地方
• 到最大值[（ N + 1）/ 2]葉（其中所有的節點，保存爲葉，每個都具有2個節點。）

類型樹可以定義多少離開它具有的。例如上面，後者是「完整」二叉樹的定義。

Answer 2

設T是n> 0節點的二叉樹。

• 如果T是最大程度地平衡，則T已⌈n/2⌉=（N + 1）// 2個葉節點，
  其中//表示整數除法。

• 如果T是最小平衡的，那麼T有1個葉節點。

• 如果T有m個葉子，則1≤m≤⌈n/2⌉。