对于具有n个节点的完整二叉树，叶节点有多少个节点？

Question

我们的Powerpoint中的答案之一表示它是n/2叶，但我看到另一个说（n + 1）/ 2的答案。我想知道哪一个是正确的，为什么？

Answer 1

在最简单的情况下，具有根节点，左和右的二叉树有3个节点，其中两个是叶节点。它是（n + 1）/ 2。

Answer 2

如果您的总节点数为n,i是内部节点的总数，即度数为1。如果所考虑的树是二叉树，则该关系成立。

2i + 3 = n。根和叶节点不是内部节点。 因此，2i + 3 = 1 + i + l其中l是叶节点的数量。 这给了我们，i + 2 = l。我们知道i = (n-3)/2。因此，l = (n+1)/2。希望这可以帮助