對於具有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。希望這可以幫助