樹

樹的定義

Q：什么是樹

A：樹是一種 非線性 的數(shù)據(jù)結(jié)構(gòu)，它是由 n （ n>=0 ）個有限結(jié)點組成一個具有層次關(guān)系的集合。把它叫做樹是因為它看起來像一棵倒掛的樹，也就是說它是根朝上，而葉朝下的。

Q：樹有什么特點

有一個特殊的結(jié)點，稱為根結(jié)點，根節(jié)點沒有前驅(qū)結(jié)點。

除根節(jié)點外，其余結(jié)點被分成M(M>0)個互不相交的集合T1、T2、……、Tm，其中每一個集合Ti(1<= i <= m)又是一棵結(jié)構(gòu)與樹類似的子樹。每棵子樹的根結(jié)點有且只有一個前驅(qū)，可以有0個或多個后繼。

樹是遞歸定義的

對于樹的定義還需要強調(diào)兩點：

當(dāng)n>0時，根結(jié)點是唯一的，不可能存在多個根結(jié)點。數(shù)據(jù)結(jié)構(gòu)中的樹是只能有一個根結(jié)點。

當(dāng)m>0時，子樹的個數(shù)沒有限制，但它們一定是互不相交的。像下圖中的結(jié)構(gòu)就不符合樹的定義，因為它們都有相交的子樹。

樹的名詞解釋

節(jié)點的度：一個節(jié)點含有的子樹的個數(shù)稱為該節(jié)點的度； 如上圖：A的為3

葉節(jié)點：度為0的節(jié)點稱為葉節(jié)點； 如上圖：I,G,K,G,L,M節(jié)點為葉節(jié)點

非終端節(jié)點或分支節(jié)點：度不為0的節(jié)點； 如上圖：B、D、C、E、F等節(jié)點為分支節(jié)點

雙親節(jié)點或父節(jié)點：若一個節(jié)點含有子節(jié)點，則這個節(jié)點稱為其子節(jié)點的父節(jié)點； 如上圖：A是B的父節(jié)點

孩子節(jié)點或子節(jié)點：一個節(jié)點含有的子樹的根節(jié)點稱為該節(jié)點的子節(jié)點； 如上圖：B是A的孩子節(jié)點

兄弟節(jié)點：具有相同父節(jié)點的節(jié)點互稱為兄弟節(jié)點； 如上圖：B、C是兄弟節(jié)點

樹的度：一棵樹中，最大的節(jié)點的度稱為樹的度； 如上圖：樹的度為3

節(jié)點的層次：從根開始定義起，根為第1層，根的子節(jié)點為第2層，以此類推

樹的高度或深度：樹中節(jié)點的最大層次； 如上圖：樹的高度為4

節(jié)點的祖先：從根到該節(jié)點所經(jīng)分支上的所有節(jié)點；如上圖：A是所有節(jié)點的祖先

子孫：以某節(jié)點為根的子樹中任一節(jié)點都稱為該節(jié)點的子孫。如上圖：所有節(jié)點都是A的子孫

森林：由m棵互不相交的樹的集合稱為森林

樹的表示

樹的存儲結(jié)構(gòu)

說到存儲結(jié)構(gòu)，自然就會想到我們前面講過的順序存儲和鏈?zhǔn)酱鎯煞N結(jié)構(gòu)。

順序存儲結(jié)構(gòu)：樹中某個結(jié)點的孩子可以有多個，若將樹中所有結(jié)點存儲到數(shù)組中，結(jié)點的存儲位置無法直接反應(yīng)其邏輯關(guān)系，因此：簡單的順序存儲結(jié)構(gòu)是不能滿足樹的實現(xiàn)要求的

鏈?zhǔn)酱鎯Y(jié)構(gòu)：鏈?zhǔn)酱鎯Y(jié)構(gòu)的特點，完全可以實現(xiàn)對樹的存儲結(jié)構(gòu)的表示。

表示方式：實際中樹有很多種表示方式， 如：雙親表示法，孩子表示法、孩子兄弟表示法等等。我們這里就簡單的了解其中最常用的孩子兄弟表示法。

代碼演示

typedef int DataType;
struct Node
{
    struct Node* _firstChild1;    // 第一個孩子結(jié)點
    struct Node* _pNextBrother;   // 指向其下一個兄弟結(jié)點
    DataType _data;               // 結(jié)點中的數(shù)據(jù)域
};

圖像演示

二叉樹的概念及結(jié)構(gòu)

二叉樹的概念

Q：什么是二叉樹

A：二叉樹是 n 個結(jié)點的有限集合。該集合或者為空集(空二叉樹)或者由一個根結(jié)點和兩棵互不相交的，分別稱為根結(jié)點的左子樹和右子樹的二叉樹組成。

Q：二叉樹有什么特點

每個結(jié)點最多有兩棵子樹，二叉樹不存在度大于2的結(jié)點。左子樹和右子樹是有順序的，次序不能任意顛倒。即使樹中某結(jié)點只有一棵子樹，也要區(qū)分左子樹還是右子樹。

Q：二叉樹有什么基本形式

空二叉樹只有一個根節(jié)點根節(jié)點只有左子樹根節(jié)點只有右子樹根節(jié)點既有左子樹又有右子樹

Q：特殊的二叉樹有哪些

（1）滿二叉樹：在一顆二叉樹中，如果所有分支結(jié)點都存在左子樹和右子樹，并且所有葉子都在同一層上，這樣的二叉樹稱為滿二叉樹。如果一個二叉樹的層數(shù)為K，且結(jié)點總數(shù)是(2^k) -1 ，則它就是滿二叉樹。

（2）完全二叉樹：對于一顆具有 n 個結(jié)點的二叉樹按層序編號，如果編號為i（1<=i<=n）的結(jié)點與同樣深度的滿二叉樹中編號為i的結(jié)點在二叉樹中的位置完全相同，則稱這棵二叉樹為完全二叉樹。滿二叉樹是一種特殊的完全二叉樹。

二叉樹的性質(zhì)

性質(zhì)一：在二叉樹的第 i 層上至多有2^(i-1) 個結(jié)點。

性質(zhì)二：深度為 k 的二叉樹至多有2^(k)-1個結(jié)點。

性質(zhì)三：對任何一棵二叉樹, 如果度為0，其葉結(jié)點個數(shù)為 n0, 度為2的分支結(jié)點個數(shù)為 n2,則有n0＝n2 + 1。

性質(zhì)四：具有 n 個結(jié)點的完全二叉樹的深度為

性質(zhì)五：對于具有 n 個結(jié)點的完全二叉樹，如果按照從上至下從左至右的數(shù)組順序?qū)λ泄?jié)點從 0 開始編號，則對于任意結(jié)點 i 有：

如果 i=1，則結(jié)點 i 是二叉樹的根，無雙親；如果 i>1，則其雙親是結(jié)點 1/2

如果 2i>n，則結(jié)點 i無左孩子；否則其左孩子是結(jié)點2i

如果 2i<n，則結(jié)點 i無右孩子；否則其右孩子是結(jié)點2i+1

二叉樹的存儲結(jié)構(gòu)

順序存儲結(jié)構(gòu)

順序結(jié)構(gòu)存儲就是使用數(shù)組來存儲，一般使用數(shù)組只適合表示完全二叉樹。因為不是完全二叉樹會有空間的浪費。而現(xiàn)實中使用中只有堆才會使用數(shù)組來存儲，二叉樹順序存儲在物理上是一個數(shù)組，在邏輯上是一顆二叉樹。

鏈?zhǔn)酱鎯Y(jié)構(gòu)

二叉樹每個結(jié)點最多有兩個孩子，所以為它分配一個數(shù)據(jù)域和兩個指針域是比較自然的想法，我們稱這樣的鏈表叫做二叉鏈表。結(jié)點結(jié)構(gòu)如圖：

代碼演示

typedef int BTDataType;
struct BinaryTreeNode
{
    struct BinTreeNode* _pLeft;       // 指向當(dāng)前節(jié)點左孩子
    struct BinTreeNode* _pRight;      // 指向當(dāng)前節(jié)點右孩子
    BTDataType _data;                 // 當(dāng)前節(jié)點值域
}