计算二叉树内部节点

Question

我可以找到一个有关全二叉树的问题。

完整的二叉树是一棵有根树，其中每个内部节点只有两个孩子。有500个叶子的完整二​​叉树中有多少个内部节点？

我感觉答案250请解释

Answer 1

任取两片叶子，并结合他们创造一个内部节点。现在，你可以增加一个内部节点的数量，并删除两个使用过的叶子，它们比新叶子中的内部节点变换。

因此，如果我们呼叫f(n)有n个叶子的内部节点的数量，先前的参数会导致我们到f(n) = 1 + f(n - 1)，其中f(2) = 1。因此，f(n) = n - 1。

因此，对于500的结果为499。

Answer 2

如果满二叉树（T）具有500种的叶子（L），则内部节点的数量是I = L - 1，即I = 500 - 1。

Result is 499.