樹與二叉樹——二叉樹中計算葉子結點個數問題

1、已知完全二叉樹具有967個結點，則其葉子結點個數為：

詳解：

首先明确一點該二叉樹是一棵二叉樹，那可以使用二叉樹的一些性質。

從第一層開始計算每層的節點個數：1，2,4,8,16,32,64,128,256,512,1024...

将前9層的結點數量全部加起來有511個，如果加上第十層1024，則超過967，是以該完全二叉樹肯定是有十層的，是以葉子結點分布在第9層和第10層，且第10層全部都是葉子結點。

設第9層的葉子個數為b，第9層的分支結點個數為a；

由于是完全二叉樹，又該樹有10層，是以第9層肯定有2^(9-1) = 256個結點，則有關系式：

a + b = 256    ---------------(1)

又第9層的分支結點個數為a,那麼第10層的葉子個數為2*a, 或者2*a-1 個，對于這兩種情況，可以根據總的結點個數來确定，因為967是一個奇數，又第1層根節點隻有一個，總的結點個數減去1，則為966，是一個偶數，是以第10層的葉子個數肯定為2*a個。

已知前9層共有1+2+4+8+16+32+64+128+256 = 511個結點，第10層有2*a個結點，是以結點總數為前9層的總數加上第10層的個數，則有關系式：

2*a + 511 = 967  ---------------(2)

結合關系式（1）（2），可解得a = 228, b = 28，

葉子結點總數為第9層的葉子數加上第10層的葉子數：b + 2*a = 28 + 2 * 228 = 484。

2、在一棵度為4的樹T中，如有20個度為4的結點，10個度為3的結點，1個度為2的結點，10個度為1的結點，則樹T中的葉子結點個數為：

解：設結點總數為n,葉子結點個數為m。

則結點總數: n = 20 + 10 + 1 + 10 + m        ---------------(1)

還有一個關系式是關于結點總數和總度數的。

假如将“度”了解為一根繩子，對于每一棵樹，我們都很清楚，每一個結點都是由一個度牽引着的，除了根節點這個特殊結點沒有被度牽引。是以，總結點數是總的度數加上根節點的數目，而根節點隻有一個，是以總結點數 = 總的度數 + 1，由此，可以得到下面的結點總數和度總數的關系式：

n = 20*4 + 10*3 + 1*2 + 10*1 + m*0  + 1      ---------------(2)

聯合關系式（1）（2），可解得m = 82。

3、一棵度為3的樹中，有3度結點100個，有2度結點200個，則葉子結點個數為：

解：雖然這棵樹不是二叉樹，但是有些性質也是适用的。其中，最重要的一個性質是結點總數和總度數的關系。

設1度結點共有a個，葉子結點共有b個，總的結點個數為n,則有以下關系式：

n = 100 + 200 + a + b

n = 3 * 100 + 2 * 200 + 1 * a + 0 * b + 1

聯合以上兩個關系式可以解得 b = 401，即葉子個數為401個。

總結：

大部分關于二叉樹的計算問題，隻要僅僅抓住二叉樹和樹的性質，基本上都能很快解決。

是以對于二叉樹的性質要非常熟悉，不僅僅要知道性質的内容，也要知道性質的推倒過程。