1001個結點的二叉樹有多少個子葉

1001個結點的二叉樹有多少個子葉？

1001個結點的二叉樹，最少只有一個葉子結點，也就是每一層都只有一個結點，每個結點最多只有一個子結點的情況。

而當二叉樹是完全二叉樹時，它的葉子最多。我們來算下1001個結點的完全二叉樹有多少個葉子。我們知道，n個結點的完全二叉樹的高度是?log?(n+1)?， 1001個結點的完全二叉樹的高度是?log?(1001+1)?=10。那么它前9層的結點總數有:2^9-1=511，第10層的葉子結點數為:1001-512=489，第9層的結點數為:2^8=256。第9層當然不會都是分支，由第10層的489個葉子，可知第9層的分支結點有: ?489/2?=245個，那么第9層的葉子結點有256-245=11個。葉子總數是11+489=500。