（六）樹與二叉樹
1．樹的基本概念
樹是一種簡單的非線性結構。在樹結構中，數(shù)據(jù)元素之間有著明顯的層次結構。在樹的圖形表示中，用直線連接兩端的結點，上端點為前件，下端點為后件。
在樹結構中，每一個結點只有一個前件，稱為父結點。如A即為結點B、C、D的父結點。
沒有父結點的結點只有一個，稱為根結點。如上圖所示，結點A即為根結點。
每一個結點可以有多個后件，它們均稱為該結點的子結點。如結點G、H、I是結點D的子結點。
沒有后件的結點，稱為葉子結點。上圖中，葉子結點有：J、M、N、L、C、G、H、I。
在樹結構中，一個結點所擁有的后件結點個數(shù)稱為該結點的度。例如，結點D的度為3，結點E的度為1等，按此原則，所有葉子結點的度均為0。
在樹中，所有結點中的度稱為該樹的度。上圖所示的樹中，所有結點中的度是3，所以該樹的度為3。
樹分層，根結點為第一層，往下依次類推。同一層結點的所有子結點均在下一層。如上圖：A結點在第1層，B、C、D結點在第2層；E、F、G、H、I在第3層；J、K、L在第4層；M、N在第5層。
樹的層次稱為樹的深度。上圖樹的深度為5。
在樹中，某結點的一個子結點為根構成的樹稱作該結點的子樹。葉子結點沒有子樹。
在計算機中，可以用樹來表示算術表達式。原則如下：
（1）表達式中每一個運算符在樹中對應一個結點，稱為運算符結點
（2）運算符的每一個運算對象在樹中為該運算符結點的子樹（在樹中的順序為從左到右）
（3）運算對象中的單變量均為葉子結點
樹在計算機中用多重鏈表表示。多重鏈表中的每個結點描述了樹中對應結點的信息，而每個結點中的鏈域（即指針域）個數(shù)將隨著樹中該結點的度而定義。
如果在樹中，每一個結點的子結點的個數(shù)不相同，因此在多重鏈中各結點的鏈域個數(shù)也不相同，會導致算法太復雜。因此，在樹中，常采用定長結點來表示樹中的每一個結點，即取樹的度作為每個結點的鏈域的個數(shù)。這樣，管理相對簡化了，但會造成空間的浪費，因為有許多的結點存在空鏈域。
2．二叉樹及其基本性質
1）二叉樹的定義
二叉樹的特點：
非空二叉樹只有一個根結點
每一個結點最多只有兩個子結點，且結點分左右。則一個結點最多可以有兩棵子樹，分別稱為左子樹和右子樹
在二叉樹中，每一個結點的度為2，即二叉樹的度為2。在二叉樹中，任何的子樹也均為二叉樹。
在二叉樹中，每一個結點的子樹被分為左子樹和右子樹。在二叉樹中，允許某一個結點只有左子樹或只有右子樹。如果一個結點既沒有左子樹，也沒有右子樹，則該結點為葉子結點。
2）二叉樹的性質
性質1：在二叉樹的第k層上，最多有2k-1（k≥1）個結點。
性質2：深度為m的二叉樹最多有2m-1個結點。
性質3：在任意一棵二叉樹中，度為0的結點（即葉子結點）總比度為2的結點多一個。
性質4：具有n個結點的二叉樹，其深度至少為[log2n]+1，其中[log2n]表示log2n的整數(shù)部分。
3）滿二叉樹與完全二叉樹
（1）滿二叉樹
滿二叉樹的特點：
除最后一層外，每一層上的所有結點都有兩個子結點。即在滿二叉樹中，每一層上的結點數(shù)都達到值，即在滿二叉樹上的第k層上有2k-1個結點。如下即為一棵滿二叉樹。
（2）完全二叉樹
特點：除最后一層外，每一層上的結點數(shù)均達到值，在最后一層上只缺少右邊的若干個結點。
即如果從根結點開始，對二叉樹的結點自上而下、自左而右用自然數(shù)進行連續(xù)編號，則深度為m、且有n個結點的二叉樹，當且僅當其每一個結點都與深度為m的滿二叉樹中編號從1到n的結點一一對應，則是完全二叉樹。
對于完全二叉樹，葉子結點只能在層次的兩層中出現(xiàn)；對于任何一個結點，若其右分支下的子樹結點的層次為p，則其分支下的子孫結點的層次為p或p+1。
完全二叉樹具有的性質：
性質5：具有n個結點的完全二叉樹的深度為[log2n]+1
性質6：設完全二叉樹共有n個結點。如果從根結點開始，按層次（每一層從左到右）用自然數(shù)1、2……、n給結點編號，對于編號為k（k=1,2,……n）的結點有如下結論：
① 若k=1，則該結點為根結點，它沒有父結點；若k>1，則該結點的父結點編號為INT(k/2)。
② 若2k≤n，則編號為k的結點的左子結點編號為2k；否則該結點無左子結點（當然也沒有右子結點）
③ 若2k+1≤n，則編號為k的結點的右子結點編號為2k+1；否則該結點無右子結點。
3．二叉樹的存儲結構
二叉樹的存儲常采用鏈式存儲結構。
存儲二叉樹中各元素的存儲結點由兩個部分組成：數(shù)據(jù)域和指針域。在二叉樹中，由于每個結點可有兩個子結點，則它的指針域有兩個：一個用于存儲該結點的左子結點的存儲地址，即稱為左指針域；一個用于存儲指向該結點的右子結點的存儲地址，稱為右指針域。
存儲結構如下：
即二叉樹的存儲結構中每一個存儲結點都有兩個指針域，因此，二叉樹的鏈式存儲結構也稱為二叉樹的鏈表。在二叉樹在存儲中，用一個頭指針指向二叉樹的根結點的存儲地址。
如圖所示的二叉樹：
如果我們將該二叉樹的所有結點順序編號，順序存放在存儲空間里，則它們在內存空間中的存放方式是：
當然，對于滿二叉樹或完全二叉樹而言，也可采用順序存儲的方式，但順序存儲的方式不適合其他的二叉樹。
4．二叉樹的遍歷
二叉樹的遍歷即是不重復地訪問二叉樹的所有結點。
在遍歷二叉樹時，一般先遍歷左子樹，然后再遍歷右子樹。在先左后右的原則下，二叉樹的遍歷又可分為三種：前序遍歷、中序遍歷和后序遍歷。
1）前序遍歷
前序遍歷即先訪問根結點，然后遍歷左子樹，最后遍歷右子樹。在遍歷左子樹和遍歷右子樹時，依然是先遍歷根結點，然后是左子樹，再是右子樹。
操作的具體方式：
若二叉樹為空，則結束返回。
否則：訪問根結點前序遍歷左子樹前序遍歷右子樹
如上圖所示的完全二叉樹，它的前序遍歷結果是：A、B、D、H、P、Q、I、R、E、J、K、C、F、L、M、G、N、O
2）中序遍歷
中序遍歷，即先遍歷左子樹，然后訪問根結點，最后是遍歷右子樹。
具體的操作方式：
若二叉樹為空，則結束返回。
否則：中序遍歷左子樹訪問根結點 中序遍歷右子樹
這里強調，在遍歷左子樹和右子樹時，仍然要采用中序遍歷的方法。
如上圖所示的完全二叉樹，它的中序遍歷結果是：P、H、Q、D、R、I、B、J、E、K、A、L、F、M、C、N、G、O
3）后序遍歷
后序遍歷，即選遍歷左子樹，然后是遍歷右子樹，最后訪問根結點。
具體的操作方式：
若二叉樹為空，則結束返回。
否則：前序遍歷左子樹前序遍歷右子樹訪問根結點
如上圖所示的完全二叉樹，它的后序遍歷結果是：P、Q、H、R、I、D、J、K、E、B、L、M、F、N、O、G、C、A