樹與二叉樹

一、樹的基本概念

1.1 樹的定義

      樹是N個結點的有限集合，N=0時稱為空樹。任何一顆非空樹均滿足有且僅有一個根結點，其余結點可分為m個互不相交的有限集合，其中每一個集合本身又是一棵樹，稱為根結點的子樹。

      樹的定義是遞歸的，一棵樹由若干個子樹組成，子樹又由更小的子樹構成。樹是一種重要的非線性結構，也是一種分層結構，用來描述客觀世界中廣泛存在的層次結構。

圖1 樹知識結構

1.2 基本術語

      樹的樹形表示：

圖2 樹形結構

（1）考慮K結點，根A到結點K的唯一路徑上的任意結點，稱為K的祖先結點。如結點B為K的祖先結點，K為結點B的子孫結點。結點E稱為K的雙親結點，K為結點E的孩子結點。有相同雙親的結點稱為兄弟結點，如結點K和結點L為兄弟結點。

（2）樹中一個結點的子結點個數稱為該結點的度，樹中結點的最大度數稱為樹的度。如節點B的度為2，節點D的度為3，樹的度為3。

（3）度大於0的結點稱為分支結點（非終端節點）；度為0（沒有子女結點）的結點稱為葉子結點（終端節點）。每個結點的分支數就是該節點的度。

（4）節點的深度、高度和層次

      結點層次從樹根開始定義，根節點為第一層，它子結點為第二層，以此類推。

      結點深度從根結點開始自頂向下逐層累加。

      結點高度從葉結點開始自底向上逐層累加。

      樹的高度是樹中節點最大的層數，如上圖樹的高度為4。

（5）有序樹和無序樹。樹中結點的左右是有次序的，不能交換稱之為有序樹；反之稱為無序樹。

（6）路徑和路徑長度，兩結點間路徑是兩個結點之間所經過的結點序列構成的，路徑長度是路徑上經歷過的邊的個數。如上圖，結點A和K的路徑長度為3，中間經過結點B和結點E。

（7）森林，森林是m顆互不相交的樹的集合。把樹的根節點刪去就成了森林，反之，給n顆獨立的樹加上一個跟結點，森林就成了樹。

1.3 樹的性質

（1）    樹中結點數等於所有結點的度數加1

（2）    度為m的樹中第i層上至多有m^i-1個結點（i >= 1）

（3）    高度為h的m叉樹至多有(m^h-1)/(m-1)個結點

（4）    具有n個結點的m叉樹的最小高度為⌈log_m(n(m-1)+1)⌉(向上取整)

樹結點與度之間的關系：

1．  總結點數 = N₀+ N₁+ N₂ + … + N_m;

2．  總分支數 = 1* N₁ + 2* N₂ + … + m* N_m（度為m的結點引出m條分支）

3．  總結點數 = 總分支數 + 1

二、二叉樹的概念

2.1 二叉樹的定義

      二叉樹的特點是每個結點至多有兩顆子樹（不存在度大於2的結點），並且其子樹有左右之分，次序不能顛倒，即使在結點只有一顆子樹的情況下也要明確指出是左子樹還是右子樹。

幾個特殊的二叉樹

1．滿二叉樹

      一顆高度為h且含有2^h-1個結點的二叉樹稱為滿二叉樹，樹中的每一層都含有最多的結點，滿二叉樹的葉子結點都集中在最底層，除葉子結點之外的其他結點度均為2。

圖3 滿二叉樹

      對滿二叉樹按層次順序編號如上圖，約定根結點從1開始，自上而下，自左至右。那麼對於編號為i的結點，若有雙親，其雙親為⌊i/2⌋ (向下取整)，若有左孩子則為2i，若有右孩子則為2i+1。

2．完全二叉樹

      高度為h，有n個結點的二叉樹，當且僅當其每一個結點都與深度為h的滿二叉樹中編號1~n的結點一一對應時，稱為完全二叉樹，如下圖。該樹的特點如下：

圖4 完全二叉樹

（1）    葉子結點只可能在層次最大的兩層上出現

（2）    若有度為1的結點，只可能有一個，且該結點只有左孩子沒有右孩子

（3）    若i<=⌊n/2⌋，則i為分支結點，否則為葉子結點

（4）    按層次編號時，一旦出現某結點i為葉子結點或只有左孩子，那麼編號大於i的結點均為葉子結點

（5）    若n為奇數，每個分支結點都有左右孩子；若n為偶數，則編號為n/2的結點只有左孩子，其余分支結點左右孩子都有

3．二叉排序樹

      二叉排序樹是具有以下性質的二叉樹：左子樹上所有結點的關鍵字均小於根節點的關鍵字；右子樹上所有結點的關鍵字均大於根節點的關鍵字。左右子樹又各是一顆二叉排序樹。

4．平衡二叉樹

      樹上任一結點的左子樹和右子樹的深度之差不超過1。

2.2 二叉樹的性質

（1）非空二叉樹上葉子結點數等於度為2的結點數加1，即N₀ = N₂+1。

      證明：設度為0、1和2的結點個數分別為N₀、N₁和N₂、結點總數N= N₀ +N₁+ N₂。再看二叉樹中的分支數，除根節點外，其余結點都有一個分支進入，設B為分支總數，則N=B+1。由於這些分支由度為1或2的結點射出，所以B= N₁+ 2N₂。

      於是得出N₀ +N₁+ N₂ = N₁+ 2N₂+1，則N₀ = N₂+1。

（2）非空二叉樹第K層至多有2^k-1個結點（K>=1）

（3）高度為h的二叉樹至多有2^h-1個結點（h>=1）

（4）對完全二叉樹按從上到下，從左到右的順序編號為1，2，…，N則有以下關系：

      ① 當I > 1時，結點i的雙親結點編號為⌊i/2⌋

      ② 當2i <= N時，結點i的左孩子編號為2i，否則無右孩子

      ③ 當2i+1 <= N時，結點i的右孩子編號為2i+1，否則無左孩子

      ④ 結點i所在層次（深度）為⌊log₂i⌋+1

      ⑤ 具有N個結點的完全二叉樹的高度為⌈log₂(N+1)⌉或⌊log₂N⌋+1

       接下來分別對二叉樹的順序存儲和鏈式存儲進行總結，分別實現二叉樹的前中後序遍歷的遞歸和非遞歸算法，以及層次遍歷。