二叉搜索树中的叶子数量

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⌉。