C++筆試題之求完全二叉樹葉子節(jié)點(diǎn)數(shù)

一、樹的定義

樹是一種數(shù)據(jù)結(jié)構(gòu)，它是由n（n>=1）個有限結(jié)點(diǎn)組成一個具有層次關(guān)系的集合。

?

樹具有的特點(diǎn)有：

（1）每個結(jié)點(diǎn)有零個或多個子結(jié)點(diǎn)

（2）沒有父節(jié)點(diǎn)的結(jié)點(diǎn)稱為根節(jié)點(diǎn)

（3）每一個非根結(jié)點(diǎn)有且只有一個父節(jié)點(diǎn)

（4）除了根結(jié)點(diǎn)外，每個子結(jié)點(diǎn)可以分為多個不相交的子樹。

?

樹的基本術(shù)語有：

若一個結(jié)點(diǎn)有子樹，那么該結(jié)點(diǎn)稱為子樹根的“雙親”，子樹的根稱為該結(jié)點(diǎn)的“孩子”。有相同雙親的結(jié)點(diǎn)互為“兄弟”。一個結(jié)點(diǎn)的所有子樹上的任何結(jié)點(diǎn)都是該結(jié)點(diǎn)的后裔。從根結(jié)點(diǎn)到某個結(jié)點(diǎn)的路徑上的所有結(jié)點(diǎn)都是該結(jié)點(diǎn)的祖先。

?

結(jié)點(diǎn)的度：結(jié)點(diǎn)擁有的子樹的數(shù)目

葉子結(jié)點(diǎn)：度為0的結(jié)點(diǎn)

分支結(jié)點(diǎn)：度不為0的結(jié)點(diǎn)

樹的度：樹中結(jié)點(diǎn)的最大的度

層次：根結(jié)點(diǎn)的層次為1，其余結(jié)點(diǎn)的層次等于該結(jié)點(diǎn)的雙親結(jié)點(diǎn)的層次加1

樹的深度：樹中結(jié)點(diǎn)的最大層次

森林：0個或多個不相交的樹組成。對森林加上一個根，森林即成為樹；刪去根，樹即成為森林。

?

二、二叉樹

1、二叉樹的定義

二叉樹是每個結(jié)點(diǎn)最多有兩個子樹的樹結(jié)構(gòu)。它有五種基本形態(tài)：二叉樹可以是空集；根可以有空的左子樹或右子樹；或者左、右子樹皆為空。

?

2、二叉樹的性質(zhì)

性質(zhì)1：二叉樹第i層上的結(jié)點(diǎn)數(shù)目最多為2^i-1(i>=1)

性質(zhì)2：深度為k的二叉樹至多有2^k-1個結(jié)點(diǎn)（k>=1）

性質(zhì)3：包含n個結(jié)點(diǎn)的二叉樹的高度至少為(log₂n)+1

性質(zhì)4：在任意一棵二叉樹中，若終端結(jié)點(diǎn)的個數(shù)為n₀，度為2的結(jié)點(diǎn)數(shù)為n₂，則n₀=n₂+1

?

3、性質(zhì)4的證明

性質(zhì)4：在任意一棵二叉樹中，若終端結(jié)點(diǎn)的個數(shù)為n₀，度為2的結(jié)點(diǎn)數(shù)為n₂，則n₀=n₂+1

證明：因為二叉樹中所有結(jié)點(diǎn)的度數(shù)均不大于2，不妨設(shè)n₀表示度為0的結(jié)點(diǎn)個數(shù)，n₁表示度為1的結(jié)點(diǎn)個數(shù)，n₂表示度為2的結(jié)點(diǎn)個數(shù)。三類結(jié)點(diǎn)加起來為總結(jié)點(diǎn)個數(shù)，于是便可得到：n=n₀+n₁+n_2?(1)

由度之間的關(guān)系（二叉樹的各結(jié)點(diǎn)的總度數(shù)=結(jié)點(diǎn)數(shù)-1，這個很直觀，比如只有3個結(jié)點(diǎn)的二叉樹，總度數(shù)為2）可得第二個等式：n=n₀*0+n₁*1+n₂*2+1即n=n₁+2n₂+1?(2)

將（1）（2）組合在一起可得到n₀=n₂+1

?

三、滿二叉樹、完全二叉樹和二叉查找樹

1、滿二叉樹

定義：高度為h，并且由2^h-1個結(jié)點(diǎn)組成的二叉樹，稱為滿二叉樹

?

2、完全二叉樹

定義：一棵二叉樹中，只有最下面兩層結(jié)點(diǎn)的度可以小于2，并且最下層的葉結(jié)點(diǎn)集中在靠左的若干位置上，這樣的二叉樹稱為完全二叉樹。

特點(diǎn)：葉子結(jié)點(diǎn)只能出現(xiàn)在最下層和次下層，且最下層的葉子結(jié)點(diǎn)集中在樹的左部。顯然，一棵滿二叉樹必定是一棵完全二叉樹，而完全二叉樹未必是滿二叉樹。

?

面試題：如果一個完全二叉樹的結(jié)點(diǎn)總數(shù)為768個，求葉子結(jié)點(diǎn)的個數(shù)。

由二叉樹的性質(zhì)知：n₀=n₂+1，將之帶入768=n₀+n₁+n₂中得：768=n₁+2n₂+1，因為完全二叉樹度為1的結(jié)點(diǎn)個數(shù)要么為0，要么為1，那么就把n₁=0或者1都代入公式中，很容易發(fā)現(xiàn)n₁=1才符合條件。所以算出來n₂=383，所以葉子結(jié)點(diǎn)個數(shù)n₀=n₂+1=384。

總結(jié)規(guī)律：如果一棵完全二叉樹的結(jié)點(diǎn)總數(shù)為n，那么葉子結(jié)點(diǎn)等于n/2（當(dāng)n為偶數(shù)時）或者(n+1)/2（當(dāng)n為奇數(shù)時）

?

3、二叉查找樹

定義：二叉查找樹又被稱為二叉搜索樹。設(shè)x為二叉查找樹中的一個結(jié)點(diǎn)，x結(jié)點(diǎn)包含關(guān)鍵字key，結(jié)點(diǎn)x的key值計為key[x]。如果y是x的左子樹中的一個結(jié)點(diǎn)，則key[y]

?

在二叉查找樹中：

（1）若任意結(jié)點(diǎn)的左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值。

（2）任意結(jié)點(diǎn)的右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值。

（3）任意結(jié)點(diǎn)的左、右子樹也分別為二叉查找樹。

（4）沒有鍵值相等的結(jié)點(diǎn)。

這里既然提到了二叉查找樹，那么二叉查找樹能夠解決聲明問題呢？

比如說,你想從微博中找到一個人，最快的方法一般是二分查找。但當(dāng)有新用戶增加時，都得將新用戶插入組別內(nèi)再排序。因為二分查找法只會有序的組別才有用。
因此有人想到了用二叉樹。對于每個結(jié)點(diǎn)，左子節(jié)點(diǎn)的值都比它小，右子節(jié)點(diǎn)值都比它大。

如上圖，MAGGIE排在DAVID后面，因此向右找，MAGGIE排在MANNING前面，因此向左找。這個運(yùn)行時間，用大O表示法，平均運(yùn)行時間是O(log2 N)，最差運(yùn)行時間是O(N)在有序數(shù)組查找時，與二分查找法運(yùn)行時間相同。二叉樹對比二分查找法優(yōu)勢在于下圖。

可以看出插入和刪除速度都快。
二叉樹的缺點(diǎn)是不能隨機(jī)訪問。