我如何证明一棵完整的二进制树具有$ lceil n/2 rceil $叶子？

Question

给定一棵带有$ n $节点的二进制树。我试图证明一棵完整的二进制树具有$ lceil n/2 rceil $叶子。我想我可以通过归纳来做到这一点。

对于$ h（t）= 0 $，树是空的。因此，没有叶子，索赔保留了一棵空树。

对于$ h（t）= 1 $，这棵树有1个节点，也是叶子，因此索赔保留。在这里，我卡住了，我不知道该选择是归纳假设以及如何做归纳步骤。

Answer 1

如果您要通过归纳证明的声明是

对于所有正整数$ n $，带有$ n $节点的完整二进制树具有$ lceil {n/2} rceil $叶子。

那么诱导假说必须是

对于所有积极整数$ k

同样，如果您要通过归纳证明的声明是

对于所有正整数$ n $，带有$ n $ whatsits的housegow具有$ 2^{ lfloor sqrt {n} rceil！} cdot n^ pi $ nubbleframets。

那么诱导假说必须是

对于所有积极整数$ k

Answer 2

首先，对您的术语更加具体，可能会有所帮助。我假设您的意思是“完成” [CLRS01]定义它：

所有叶子都具有相同的深度，所有内部节点均具有2度。

其次，这是作业吗？

您可以使用结构诱导来证明这一点。显示您对“基础”树的主张，然后考虑一下其他完整的二进制树是如何从中建立的。

当您以这种方式建造较大的树木时，节点总数如何增加？叶子的数量如何增加？

暗示：

$ lceil n+1 rceil = 2 lceil n/2 rceil $吗？