binary-search-tree - 如何证明一棵完整的二叉树有 \lceil n/2 \rceil 叶？

Question

给定具有 n 个节点的完全二叉树。我试图证明一棵完整的二叉树正好有 \lceil n/2 \rceil 叶。我想我可以通过归纳来做到这一点。

对于 h(t)=0，树是空的。因此，没有叶子，并且对一棵空树的主张成立。

对于 h(t)=1，树有 1 个节点，这也是一个叶子，所以该声明成立。在这里我被卡住了，我不知道选择什么作为归纳假设以及如何进行归纳步骤。

Answer 1

如果根节点不是叶子，那么它有两个子树，您可以递归求解。每个子树的叶子比非叶子节点多一个，因此当您将根（它的非叶子节点比叶子节点多一个！）和两个子树一起添加时，您会比非叶子节点多一个叶子，或者换句话说，叶子节点占节点数量的一半，四舍五入。