树的知识总结
樹TREE
?如圖所示：?
樹的概念
?
需要注意：
樹( tree)是n(n≥0)個結點的有限集合。當n=0時,稱為空樹;任意一棵非空樹滿足以下條件:
1)有且僅有一個特定的稱為根(root)的結點。
(2)當n>1時,除根結點之外的其余結點被分成m(m>0)個互不相交的有限集合：T1，T2,…,Tm,其中每個集合又是一棵樹,并稱為這個根結點的子樹(subtree)。需要強調(diào)的是,樹中根結點的子樹之間是互不相交的。
?
結點分類：
結點之間的關系：
(1)結點的度、樹的度
某結點所擁有的子樹的個數(shù)為該節(jié)點的度，樹的度是每個結點的度中的最大值。
(2)葉子結點、分支結點
度為0的結點稱為葉子結點或者稱為終端結點：度不為0的結點稱為分支結點,也稱為非終端結點。 (3)孩子結點、雙親結點、兄弟結點
某結點的子樹的根結點稱為該結點的孩子結點(child node):反之，該結點稱為其孩子結點的雙親結點(parent node):具有同一個雙親的孩子結點互稱為兄弟結點(brother node)。
?
樹其他相關概念：
?
?
樹具有的特點：
?
樹的相關術語：
?
樹的存儲結構
1.雙親表示法：
樹除了根結點外，其余每個結點，它不一定有孩子，但一定有且僅有一個雙親。 假設以一組連續(xù)空間存儲樹的結點，同時在每個結點中，附設一個指示器指示其雙親結點到鏈表中的位置。也就是說，每個結點除了知道自己是誰以外，還知道它的雙親在哪里。它的結點結構如圖6-4-1所示。 其中data是數(shù)據(jù)域，存儲結點的數(shù)據(jù)信息，parent是指針域，存儲該結點的雙親在數(shù)組中的下標。 以下是雙親表示法的結點結構定義代碼：
/*樹的雙親表示法結點結構定義*/ #define MAX_TREE_SIZE 100 typedef int TElemType;/*樹結點的數(shù)據(jù)類型，暫且定為整型*/ typedef struct PTNode/*結點結構*/ {TElemType data;/*結點數(shù)據(jù)*/int parent;/*雙親位置*/ }PTNode; typedef struct/*樹結構*/ {PTNode nodes[MAX_TREE_SIZE];/*結點數(shù)組*/int r, n;/*根的位置和結點數(shù)*/ }PTree; ?由于根結點是沒有雙親的，所以我們約定根結點的位置域設置為-1，這就意味著我們所有的結點都存有它的雙親位置。如圖6-4-1的樹結構和表6-4-2的樹雙親表示法所示。
?
這樣的存儲結構我們可以根據(jù)結點的parent指針很容易找到它的雙親位置，所用的時間復雜度為O(1），知道parent=-1時表示找到了樹結點的根。但如果要知道結點的孩子是什么，需要遍歷整個結構。
為了更方便地找到結點的孩子，我們增加一個結點最左邊孩子的域，稱為長子域，這樣就可以很容易地得到結點地孩子。如果沒有孩子地結點，這個長子域就設置為-1，如表6-4-3所示。
對于有0個或1個孩子結點來說，這樣地結構是解決了要找孩子結點的問題了。甚至是有兩個孩子，知道了長子是誰，另一個當然是次子了。 為了體現(xiàn)各兄弟之間的關系，可以增加一個有兄弟域來體現(xiàn)兄弟的關系，也就是說每一個結點如果它存在右兄弟，則記錄下右兄弟的下標。同樣地，如果右兄弟不存在，則賦值為-1，如表6-4-4所示。
但如果結點地孩子很多，超過了2個，我們又關注結點的孩子，又關注結點的雙親，還關注結點的右兄弟，而且對時間遍歷要求還比較高，那么我們可以把此結構擴展為有雙親域、長子域、還有右兄弟域(即用 空間換取了時間)。存儲結構的設計是一個非常長靈活的過程。一個存儲結構設計得是否合理，取決于基于該存儲結構的運算是否適合、是否方便，時間復雜度好不好等。注意也不是越多越好，有需要再設計相應的結構。
2.孩子表示法：
換一種完全不同的考慮方法。由于樹中每個結點可能有多棵子樹，可以考慮用多重鏈表，即每個結點有多個指針域，其中每個指針指向一棵子樹的根結點，我們把這種方法叫作多重鏈表表示法。不過樹的每個結點的度，也就是它的孩子的個數(shù)是不相同的。所以可以設計兩種方案來解決。
方案一： 一種是指針域的個數(shù)就等于樹的度，因為樹的度是樹各個結點度的最大值。其結構如下表：
其中data是數(shù)據(jù)域，child1到childd是指針域，用來指向該結點的孩子結點。 對于圖6-4-1的樹來說，樹的度是3，所以指針域的個數(shù)是3，這種方法實現(xiàn)如下圖：
?
這種方法對于樹中各結點的度相差很大時，顯然是很浪費空間的，因為有很多的結點，它的指針域都是空的。不過如果樹中各結點的度相差很小時，那就意味著開辟的空間被充分利用了，這時存儲結構的缺點反而變成優(yōu)點了。 既然很多指針域都可能為空，那就按需分配空間，即引出了第二中分配方法。
方案二： 第二種方案每個結點指針域的個數(shù)等于該結點的度，專門取一個位置來存儲結點指針域的個數(shù)，其結構如下表所示：
其中data是數(shù)據(jù)域，degree為度域，也就是存儲該結點的孩子結點的個數(shù)，child1到childd是指針域，用來指向該結點的孩子結點。 對于圖6-4-2的樹來說，該方法實現(xiàn)如下圖：
這種方法克服了浪費空間的缺點，對空間利用率是很高了，但是由于各個結點的鏈表是不同的結構，加上要維護結點的度的數(shù)值，在運算上就會帶來時間上的損耗。 為了既可以減少空指針的浪費又能使結點結構相同，可以把每個結點放到一個順序存儲的結構數(shù)組中，再對每個結點的孩子建立一個單鏈表體現(xiàn)它們的關系。 這就是我們要講的孩子表示法。具體辦法是，將每個結點的孩子結點排列起來，以單鏈表作存儲結構，則n個結點有n個孩子鏈表，如果是葉子結點，則此單鏈表為空。然后n個頭指針又組成一個線性表，采用順序存儲結構，存放進一個一維數(shù)組中，如圖6-4-4所示。
為此，設計兩種結點結構，一個是孩子鏈表的孩子結點，如下表：
其中，child是數(shù)據(jù)域，用來存儲某個結點在表頭數(shù)組中的下標。next是指針域，用來存儲指向某結點的下一個孩子結點的指針。 另一個是表頭數(shù)組 的表頭結點，如下表 ：
其中data是數(shù)據(jù)域，存儲某結點的數(shù)據(jù)信息。firstchild是頭指針域，存儲該結點的孩子鏈表的頭指針。 以下是孩子結點表示法的結構定義代碼：
/*樹的孩子表示法結構定義*/ typedef struct CTNode/*孩子結點*/ {int child;/*孩子結點在表頭數(shù)組中的下標*/CTNode* next;/*指向某結點的下一個孩子結點*/ }*ChildPtr; typedef struct/*表頭數(shù)組 */ {TElemType data;/*某結點的數(shù)據(jù)域，存儲某節(jié)點的數(shù)據(jù)信息*/ChildPtr firstchild;/*指向某結點的第一個孩子結點*/ }CTBox; typedef struct/*樹結構*/ {CTBox nodes[MAX_TREE_SIZE];/*結點數(shù)組*/int r, n;/*根的位置和結點數(shù)*/ }CTree這樣的結構對于要找某個結點的孩子，或者找某個結點的兄弟，只需要查找這個結點的孩子單鏈表即可。對于遍歷整棵樹也是很方便，對頭結點的數(shù)組進行循環(huán)即可。 但是，這也存在著問題，要想知道某個結點的雙親是誰，需要整棵樹遍歷才行，比較麻煩。 把雙親表示法和孩子表示法綜合，如下圖：
把這種方法稱為孩子雙親表示法，應該算是孩子表示法的改進，其結構代碼定義如下：
typedef struct/*表頭數(shù)組 */ {TElemType data;/*某結點的數(shù)據(jù)域，存儲某節(jié)點的數(shù)據(jù)信息*/ChildPtr firstchild;/*指向某結點的第一個孩子結點*/int parent;/*雙親位置*/ }CTBox;其余和孩子表示法相同。
3.孩子兄弟表示法：
觀察發(fā)現(xiàn) 任意發(fā)現(xiàn)，任意一棵樹，它的結點的第一個孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的。因此，我們設置兩個指針 分別指向該結點的第一個孩子和此節(jié)點的右兄弟。 結點結構如下表：
其中data是數(shù)據(jù)域，firstchild為指針域，存儲該結點的第一個孩子結點的存儲地址，rightsib是指針域，存儲該結點的右兄弟結點的存儲地址。 結構定義代碼如下 ：
/*樹的孩子兄弟法結構定義 */ typedef struct {TElemType data;/*數(shù)據(jù)域*/struct CSNode* firstchild, *rightsib;/*指向第一個孩子結點和右兄弟結點*/ }CSNode,*CSTree;對于圖6-4-1的樹來說，這種方法實現(xiàn)的示意圖如下圖所示：
這樣表示方法，給查找某個結點的某個孩子帶來了方便，只需要通過firstchild找到此結點的長子，然后再通過此結點的rightsib找到它的二弟，接著一直下去，直到找到具體的孩子。如果要查找某個結點的雙親，可以再增加一個parent指針域來解決快速查找雙親的問題。 其實這個表示法最大的好處是它把一棵復雜的樹變成了一棵二叉樹。把圖6-4-6變形即可得到下圖這個樣子：
這樣就可以充分利用二叉樹的性質(zhì)和算法來處理這棵樹了 。
二叉樹
?
二叉樹的定義
對于這種在某個階段都是兩種結果的情形，比如開和關、0和1、真和假、上和下、對與錯、正面和反面等，都適合用樹狀結構來建模，而這種樹是很特殊的樹狀結構，叫做二叉樹。 二叉樹(Binary Tree)是n(n≥0)個結點的有限集合，該集合或者為空集(稱為空二叉樹)，或者由一個根結點和兩棵互不相交的、分別稱為根結點的左子樹和右子樹的二叉樹組成。如下圖：
(1)二叉樹特點
二叉樹的特點有：
1）每個結點最多有兩棵子樹，所以二叉樹中不存在度大于2的結點。注意不是只有兩棵子樹，而是最多有。沒有子樹或者有一棵子樹也是可以的。
2)左子樹和右子樹 是有順序的，次序不能任意顛倒。
3）即使樹中某結點只有一棵子樹，也要區(qū)分它是左子樹還是右子樹。如下圖，樹1和樹2是同一棵樹，但它們卻是不同的二叉樹。
二叉樹具有五種基本形態(tài)：
1)空二叉樹；
2）只有一個根結點；
3）根結點只有左子樹；
4）根結點只有右子樹；
5)根結點既有左子樹又有右子樹。
?
如果有三個結點，則存在如下物種二叉樹：
（2）特殊二叉樹
1）斜樹 斜樹一定是斜的，但往哪里斜還是有講究的。所有結點都只有左子樹的二叉樹叫左斜樹。所有結點都只有右子樹的二叉樹叫右斜樹。這兩者統(tǒng)稱為斜樹。圖6-5-4中的樹2就是左斜樹，樹3就是右斜樹。斜樹有很明顯的特點，就是每一層都只有結點，結點的個數(shù)與二叉樹的深度相同。 其實線性表的結構可以理解為樹的一種極為特殊的表現(xiàn)形式。
2）滿二叉樹 在一棵二叉樹中，如果所有分支結點都存在左子樹和右子樹，并且所有葉子都在同一層上，這樣的二叉樹稱為滿二叉樹，如下圖：
?
滿二叉樹的特點有： 葉子只出現(xiàn)在最下一層，出現(xiàn)在其他層就不可能達到平衡； 非葉子結點的度一定是2； 在同樣深度的二叉樹中，滿二叉樹的結點個數(shù)最大，葉子個數(shù)也最多。
3）完全二叉樹
二叉樹的性質(zhì)
(1)第i層的至多結點個數(shù)
（2）深度為k的結點個數(shù)
（3）終端結點個數(shù)和度為2的結點個數(shù)的關系
（4）具有n個結點的完全二叉樹的深度
（5）判斷根、雙親、左右孩子的編號和總的結點個數(shù)的關系
二叉樹的存儲結構
（1）二叉樹順序存儲結構
前面提到順序存儲對樹這種一對多的關系結構實現(xiàn)起來是比較困難的，但是二叉樹是一種特殊的樹，它的特殊性使得用順序存儲結構也可以實現(xiàn)。 二叉樹的順序存儲結構就是用一維數(shù)組存儲二叉樹中的結點，并且結點的存儲位置，也就是數(shù)組的下標要能體現(xiàn)結點之間的邏輯關系，比如雙親與孩子的關系、左右兄弟的關系等。
/*二叉樹順序存儲結構，其中數(shù)組下標即表示結點的編號*/ typedef int SBElemType;/*SBElemType依據(jù)實際類型而定，這里假設為int型*/ typedef struct {SBElemType data[MAX_TREE_SIZE];/*結點數(shù)據(jù)域*/int len;/*數(shù)組長度*/ }SBTree; 1234567（2）二叉鏈表
二叉樹每個結點最多有兩個孩子，所以為它設計一個數(shù)據(jù)域和兩個指針域是比較自然的想法。我們稱這樣的鏈表叫二叉鏈表，其結點結構圖如下表： 其中data是數(shù)據(jù)域，lchild和rchild是指針域，分別存放指向左孩子和右孩子的指針。 以下是二叉鏈表結點結構的定義代碼：
/*二叉樹的結點結構定義代碼*/ typedef struct BiTNode/*結點結構*/ {TElemType data;/*結點數(shù)據(jù)*/struct BiTNode* lchild, *rchild;/*左右孩子指針*/ }BiTNode,*BiTree;結構示意圖如下所示： 就如同樹的存儲結構中討論的一樣，如果有需要，還可以再增加一個指向其雙親的指針域，那樣就稱之為三叉鏈表。
遍歷二叉樹
（1）二叉樹遍歷原理
對于二叉樹的遍歷來說，次序顯得很重要。 二叉樹的遍歷(traversing binary tree)是指從根結點出發(fā)，按照某種次序依次訪問二叉樹中所有結點，使得每個結點被訪問依次且僅被訪問一次。 這里有兩個關鍵詞，訪問和次序。 訪問其實是要根據(jù)實際的需要來確定具體做什么，比如對每個結點進行相關計算、輸出打印等，它其實算是一個抽象操作。在這里我們可以簡單假定就是輸出結點的數(shù)據(jù)信息。 二叉樹的遍歷次序不同于線性結構，最多也是從頭至尾、循環(huán)、雙向等簡單的遍歷方式。樹的結點之間不存在唯一的前驅(qū)和后繼關系，在訪問一個結點后，下一個被訪問的結點面臨著不同的選擇，由于選擇方式的不同，遍歷的次序就完全不同了。
（2）二叉樹遍歷方法
二叉樹的遍歷方式可以有很多，如果我們限制了從左到右的遍歷方式，那么主要就分為四種：
1)前序遍歷
規(guī)則是若二叉樹為空，則空操作返回，否則先訪問根結點，然后前序遍歷左子樹（注意是左子樹而不是左結點），再前序遍歷右子樹，如下圖，遍歷次序為：ABDGHCEIF。
?
2）中序遍歷
規(guī)則是若樹為，則空操作返回，否則從根結點開始(注意并不是先訪問根結點)，中序遍歷根結點的左子樹，然后是訪問中結點，最后中序遍歷右 子樹。如下圖，遍歷的順序為：GDHBAEICF。
?
3）后序遍歷
規(guī)則是若樹為空，則空操作返回，否則從左到右先葉子后結點的方式遍歷 訪問左右子樹，最后是訪問根結點。如下圖，遍歷次序為：GHDBIEFCA。
?
4）層次遍歷
規(guī)則是若樹為空，則空操作返回，否則從樹的第一層，也就是根結點開始訪問，從上而下逐層遍歷 ，在同一層中，按從左到右的順序?qū)Y點逐個訪問。如下圖，遍歷順序為：ABCDEFGHI。
?
我們用圖形的方式來表現(xiàn)樹的結構，應該說是非常直觀和容易理解，但對于計算機來說，它只有循環(huán)、判斷等方式來處理，也就是說，它只會處理線性序列，而我們剛才提到的四種遍歷方法，其實都是在把 樹中的結點變成某種意義的線性序列，這就給程序 的實現(xiàn)帶來了好處。 另外不同的遍歷提供了 對結點依次處理的不同方式，可以在遍歷過程中對結點進行各種處理。
(3)前序遍歷算法
二叉樹的定義是用遞歸的方式，所以，實現(xiàn)遍歷算法也可以采用遞歸，而且及其簡單明了。二叉樹的前序遍歷算法，代碼如下：
/*二叉樹的前序遍歷算法*/ void PreOrderTraverse(BiTree T) {if (NULL == T)/*退出遞歸的條件*/return;printf("%c", T->data);/*顯示結點數(shù)據(jù)，可以改為其他對結點的操作*/PreOrderTraverse(T->lchild);/*再先遍歷左子樹*/PreOrderTraverse(T->rchild);/*最后遍歷右子樹*/ }對過程6的理解： “訪問了K結點的右孩子，也是null，返回。于是此函數(shù)執(zhí)行完畢”：“此函數(shù)”是指T指向K結點時的函數(shù)，“執(zhí)行完畢”是指該結點不存在左孩子和右孩子，因此不再發(fā)生下一級遞歸，故已完成該函數(shù)的遞歸。 “返回到上一級遞歸函數(shù)”：能返回的原因是本級的遞歸是在上一級調(diào)用PreOrderTraverse(T->lchild)時發(fā)生的，這就意味著，上一級的遞歸還沒完成就已進入本級遞歸，故本級遞歸完成后，自然要繼續(xù)執(zhí)行上一級未完成的遞歸。 “也執(zhí)行完畢”：因為結點K是結點H的右孩子，所以結點K的遞歸完成，也就意味著在結點H遞歸中已執(zhí)行完PreOrderTraverse(T->rchild)語句，故結點H也完成了遞歸。 “返回到打印D時的函數(shù)，調(diào)用PreOrderTraverse(T->rchild)“：”函數(shù)“中 的T指向結點D；已完成結點D左子樹的遞歸，繼續(xù)執(zhí)行其右子樹的遞歸。 T指向J時的函數(shù)執(zhí)行完之后，意味著所有結點的遞歸都執(zhí)行完，因此完成了該算法的遞歸調(diào)用。
（4）中序遍歷算法
/*二叉樹的中序遍歷遞歸算法*/ void InOrderTraverse(BiTree T) {if (NULL == T)/*遞歸退出的條件*/return;InOrderTraverse(T->lchild);/*先中序遍歷左子樹*/printf("%c", T->data);/*顯示結點數(shù)據(jù)，可以改為其他對結點的操作*/InOrderTraverse(T->rchild);/*最后中遍歷右子樹*/ }（5)后序遍歷算法
/*二叉樹的后序遍歷遞歸算法*/ void PostOrderTraverse(BiTree T) {if (NULL == T)/*遞歸退出的條件*/return;PostOrderTraverse(T->lchild);/*先中序遍歷左子樹*/PostOrderTraverse(T->rchild);/*再后序遍歷右子樹*/printf("%c", T->data);/*顯示結點數(shù)據(jù)，可以改為其他對結點的操作*/ }打印后續(xù)結點的過程：打印K之后，結點H的遞歸執(zhí)行完，打印H；執(zhí)行上一級，結點D無右孩子，打印D，D結點完成遞歸；執(zhí)行上一級，執(zhí)行B結點的右孩子E遞歸，E無左右孩子，打印E，B的遞歸完成，打印B；執(zhí)行上一級，執(zhí)行A的右孩子C遞歸，C有左孩子F，F有左孩子I，I無左右孩子，打印I；F無右孩子，F遞歸結束，打印F；返回上一級，C有右孩子G，G無左孩子,有右孩子J，J無左右孩子，打印J；G完成遞歸，打印G；C完成遞歸，打印C；A完成遞歸，打印A。至此，該遞歸算法執(zhí)行結束。
（6）推導遍歷結果
本篇大部分是我向其他人學習的，如有不會，可以一起探討。網(wǎng)上也有相應的課程學習，比如一個青島大學的老師，我就在她那學習的。
總結
