一、樹的定義

樹是一種數據結構，它是由n（n>=1）個有限結點組成一個具有層次關系的集合。

?

樹具有的特點有：

（1）每個結點有零個或多個子結點

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

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

（4）除了根結點外，每個子結點可以分為多個不相交的子樹。

?

樹的基本術語有：

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

?

結點的度：結點擁有的子樹的數目

葉子結點：度為0的結點

分支結點：度不為0的結點

樹的度：樹中結點的最大的度

層次：根結點的層次為1，其余結點的層次等于該結點的雙親結點的層次加1

樹的深度：樹中結點的最大層次

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

?

二、二叉樹

1、二叉樹的定義

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

?

2、二叉樹的性質

性質1：二叉樹第i層上的結點數目最多為2^i-1(i>=1)

性質2：深度為k的二叉樹至多有2^k-1個結點（k>=1）

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

性質4：在任意一棵二叉樹中，若終端結點的個數為n₀，度為2的結點數為n₂，則n₀=n₂+1

?

3、性質4的證明

性質4：在任意一棵二叉樹中，若終端結點的個數為n₀，度為2的結點數為n₂，則n₀=n₂+1

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

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

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

?

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

1、滿二叉樹

定義：高度為h，并且由2^h-1個結點組成的二叉樹，稱為滿二叉樹

?

2、完全二叉樹

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

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

?

面試題：如果一個完全二叉樹的結點總數為768個，求葉子結點的個數。

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

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

?

3、二叉查找樹

定義：二叉查找樹又被稱為二叉搜索樹。設x為二叉查找樹中的一個結點，x結點包含關鍵字key，結點x的key值計為key[x]。如果y是x的左子樹中的一個結點，則key[y]

?

在二叉查找樹中：

（1）若任意結點的左子樹不空，則左子樹上所有結點的值均小于它的根結點的值。

（2）任意結點的右子樹不空，則右子樹上所有結點的值均大于它的根結點的值。

（3）任意結點的左、右子樹也分別為二叉查找樹。

（4）沒有鍵值相等的結點。

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

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

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

可以看出插入和刪除速度都快。
二叉樹的缺點是不能隨機訪問。