一、樹(shù)的定義

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

?

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

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

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

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

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

?

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

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

?

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

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

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

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

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

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

森林：0個(gè)或多個(gè)不相交的樹(shù)組成。對(duì)森林加上一個(gè)根，森林即成為樹(shù)；刪去根，樹(shù)即成為森林。

?

二、二叉樹(shù)

1、二叉樹(shù)的定義

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

?

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

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

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

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

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

?

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

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

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

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

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

?

三、滿二叉樹(shù)、完全二叉樹(shù)和二叉查找樹(shù)

1、滿二叉樹(shù)

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

?

2、完全二叉樹(shù)

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

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

?

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

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

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

?

3、二叉查找樹(shù)

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

?

在二叉查找樹(shù)中：

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

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

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

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

這里既然提到了二叉查找樹(shù)，那么二叉查找樹(shù)能夠解決聲明問(wèn)題呢？

比如說(shuō),你想從微博中找到一個(gè)人，最快的方法一般是二分查找。但當(dāng)有新用戶增加時(shí)，都得將新用戶插入組別內(nèi)再排序。因?yàn)槎植檎曳ㄖ粫?huì)有序的組別才有用。
因此有人想到了用二叉樹(shù)。對(duì)于每個(gè)結(jié)點(diǎn)，左子節(jié)點(diǎn)的值都比它小，右子節(jié)點(diǎn)值都比它大。

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

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