1.樹：是一種抽象數(shù)據(jù)類型（ADT），用來模擬具有樹狀結(jié)構(gòu)性質(zhì)的數(shù)據(jù)集合第步。它是由n（n>0）個(gè)有限節(jié)點(diǎn)通過連接它們的邊組成一個(gè)具有層次關(guān)系的集合所计。把它叫做“樹”是因?yàn)樗雌饋硐褚豢玫箳斓臉洌簿褪钦f它是根朝上佃声，而葉朝下的。

①迄委、節(jié)點(diǎn)：上圖的圓圈褐筛，比如A,B,C等都是表示節(jié)點(diǎn)。節(jié)點(diǎn)一般代表一些實(shí)體叙身，在java面向?qū)ο缶幊讨杏嬖?jié)點(diǎn)一般代表對(duì)象。

②信轿、邊：連接節(jié)點(diǎn)的線稱為邊晃痴，邊表示節(jié)點(diǎn)的關(guān)聯(lián)關(guān)系。一般從一個(gè)節(jié)點(diǎn)到另一個(gè)節(jié)點(diǎn)的唯一方法就是沿著一條順著有邊的道路前進(jìn)虏两。在Java當(dāng)中通常表示引用愧旦。

　　樹有很多種，向上面的一個(gè)節(jié)點(diǎn)有多余兩個(gè)的子節(jié)點(diǎn)的樹定罢，稱為多路樹笤虫。

①、路徑：順著節(jié)點(diǎn)的邊從一個(gè)節(jié)點(diǎn)走到另一個(gè)節(jié)點(diǎn)祖凫，所經(jīng)過的節(jié)點(diǎn)的順序排列就稱為“路徑”琼蚯。

②、根：樹頂端的節(jié)點(diǎn)稱為根惠况。一棵樹只有一個(gè)根遭庶，如果要把一個(gè)節(jié)點(diǎn)和邊的集合稱為樹，那么從根到其他任何一個(gè)節(jié)點(diǎn)都必須有且只有一條路徑稠屠。A是根節(jié)點(diǎn)峦睡。

③、父節(jié)點(diǎn)：若一個(gè)節(jié)點(diǎn)含有子節(jié)點(diǎn)权埠，則這個(gè)節(jié)點(diǎn)稱為其子節(jié)點(diǎn)的父節(jié)點(diǎn)榨了；B是D的父節(jié)點(diǎn)。

④攘蔽、子節(jié)點(diǎn)：一個(gè)節(jié)點(diǎn)含有的子樹的根節(jié)點(diǎn)稱為該節(jié)點(diǎn)的子節(jié)點(diǎn)龙屉；D是B的子節(jié)點(diǎn)。

⑤满俗、兄弟節(jié)點(diǎn)：具有相同父節(jié)點(diǎn)的節(jié)點(diǎn)互稱為兄弟節(jié)點(diǎn)转捕；比如上圖的D和E就互稱為兄弟節(jié)點(diǎn)。

⑥唆垃、葉節(jié)點(diǎn)：沒有子節(jié)點(diǎn)的節(jié)點(diǎn)稱為葉節(jié)點(diǎn)五芝，也叫葉子節(jié)點(diǎn)，比如上圖的H辕万、E与柑、F谤辜、G都是葉子節(jié)點(diǎn)。

⑦价捧、子樹：每個(gè)節(jié)點(diǎn)都可以作為子樹的根丑念，它和它所有的子節(jié)點(diǎn)、子節(jié)點(diǎn)的子節(jié)點(diǎn)等都包含在子樹中结蟋。

⑧脯倚、節(jié)點(diǎn)的層次：從根開始定義，根為第一層嵌屎，根的子節(jié)點(diǎn)為第二層推正，以此類推。

⑨宝惰、深度：對(duì)于任意節(jié)點(diǎn)n,n的深度為從根到n的唯一路徑長(zhǎng)植榕，根的深度為0；

⑩尼夺、高度：對(duì)于任意節(jié)點(diǎn)n,n的高度為從n到一片樹葉的最長(zhǎng)路徑長(zhǎng)尊残，所有樹葉的高度為0；

2.二叉樹：　二叉樹：樹的每個(gè)節(jié)點(diǎn)最多只能有兩個(gè)子節(jié)點(diǎn)

　　上圖的第一幅圖B節(jié)點(diǎn)有DEF三個(gè)子節(jié)點(diǎn)淤堵，就不是二叉樹寝衫，稱為多路樹；而第二幅圖每個(gè)節(jié)點(diǎn)最多只有兩個(gè)節(jié)點(diǎn)拐邪，是二叉樹慰毅，并且二叉樹的子節(jié)點(diǎn)稱為“左子節(jié)點(diǎn)”和“右子節(jié)點(diǎn)”。上圖的D,E分別是B的左子節(jié)點(diǎn)和右子節(jié)點(diǎn)扎阶。

　　如果我們給二叉樹加一個(gè)額外的條件汹胃，就可以得到一種被稱作二叉搜索樹(binary search tree)的特殊二叉樹。

　　二叉搜索樹要求：若它的左子樹不空东臀，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值着饥； 若它的右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值啡邑； 它的左贱勃、右子樹也分別為二叉排序樹井赌。

　二叉搜索樹作為一種數(shù)據(jù)結(jié)構(gòu)谤逼，那么它是如何工作的呢？它查找一個(gè)節(jié)點(diǎn)仇穗，插入一個(gè)新節(jié)點(diǎn)流部，以及刪除一個(gè)節(jié)點(diǎn)，遍歷樹等工作效率如何纹坐，下面我們來一一介紹枝冀。

二叉樹的節(jié)點(diǎn)類：

package?com.ys.tree;

public?class?Node {

????private?Object data;?//節(jié)點(diǎn)數(shù)據(jù)

????private?Node leftChild;?//左子節(jié)點(diǎn)的引用

????private?Node rightChild;?//右子節(jié)點(diǎn)的引用

????//打印節(jié)點(diǎn)內(nèi)容

????public?void?display(){

????????System.out.println(data);

????}

}

二叉樹的具體方法：

package?com.ys.tree;

public?interface?Tree {

????//查找節(jié)點(diǎn)

????public?Node find(Object key);

????//插入新節(jié)點(diǎn)

????public?boolean?insert(Object key);

????//刪除節(jié)點(diǎn)

????public?boolean?delete(Object key);

????//Other Method......

}

3.查找節(jié)點(diǎn)：

　查找某個(gè)節(jié)點(diǎn)，我們必須從根節(jié)點(diǎn)開始遍歷。

　」①球切、查找值比當(dāng)前節(jié)點(diǎn)值大，則搜索右子樹绒障；

　《执铡②、查找值等于當(dāng)前節(jié)點(diǎn)值户辱，停止搜索（終止條件）鸵钝；

　　③庐镐、查找值小于當(dāng)前節(jié)點(diǎn)值恩商，則搜索左子樹；

//查找節(jié)點(diǎn)

public?Node find(int?key) {

????Node current = root;

????while(current !=?null){

????????if(current.data > key){//當(dāng)前值比查找值大必逆，搜索左子樹

????????????current = current.leftChild;

????????}else?if(current.data < key){//當(dāng)前值比查找值小怠堪，搜索右子樹

????????????current = current.rightChild;

????????}else{

????????????return?current;

????????}

????}

????return?null;//遍歷完整個(gè)樹沒找到，返回null

}

用變量current來保存當(dāng)前查找的節(jié)點(diǎn)末患，參數(shù)key是要查找的值研叫，剛開始查找將根節(jié)點(diǎn)賦值到current。接在在while循環(huán)中璧针，將要查找的值和current保存的節(jié)點(diǎn)進(jìn)行對(duì)比嚷炉。如果key小于當(dāng)前節(jié)點(diǎn)，則搜索當(dāng)前節(jié)點(diǎn)的左子節(jié)點(diǎn)探橱，如果大于申屹，則搜索右子節(jié)點(diǎn)，如果等于隧膏，則直接返回節(jié)點(diǎn)信息哗讥。當(dāng)整個(gè)樹遍歷完全，即current == null胞枕，那么說明沒找到查找值杆煞，返回null。

樹的效率：查找節(jié)點(diǎn)的時(shí)間取決于這個(gè)節(jié)點(diǎn)所在的層數(shù)腐泻，每一層最多有2n-1個(gè)節(jié)點(diǎn)决乎，總共N層共有2n-1個(gè)節(jié)點(diǎn)，那么時(shí)間復(fù)雜度為O(logn),底數(shù)為2派桩。

4.插入節(jié)點(diǎn)：

?要插入節(jié)點(diǎn)构诚，必須先找到插入的位置。與查找操作相似铆惑，由于二叉搜索樹的特殊性范嘱，待插入的節(jié)點(diǎn)也需要從根節(jié)點(diǎn)開始進(jìn)行比較送膳，小于根節(jié)點(diǎn)則與根節(jié)點(diǎn)左子樹比較，反之則與右子樹比較丑蛤，直到左子樹為空或右子樹為空叠聋，則插入到相應(yīng)為空的位置，在比較的過程中要注意保存父節(jié)點(diǎn)的信息 及 待插入的位置是父節(jié)點(diǎn)的左子樹還是右子樹受裹，才能插入到正確的位置晒奕。

//插入節(jié)點(diǎn)

public?boolean?insert(int?data) {

????Node newNode =?new?Node(data);

????if(root ==?null){//當(dāng)前樹為空樹，沒有任何節(jié)點(diǎn)

????????root = newNode;

????????return?true;

????}else{

????????Node current = root;

????????Node parentNode =?null;

????????while(current !=?null){

????????????parentNode = current;

????????????if(current.data > data){//當(dāng)前值比插入值大名斟，搜索左子節(jié)點(diǎn)

????????????????current = current.leftChild;

????????????????if(current ==?null){//左子節(jié)點(diǎn)為空脑慧，直接將新值插入到該節(jié)點(diǎn)

????????????????????parentNode.leftChild = newNode;

????????????????????return?true;

????????????????}

????????????}else{

????????????????current = current.rightChild;

????????????????if(current ==?null){//右子節(jié)點(diǎn)為空，直接將新值插入到該節(jié)點(diǎn)

????????????????????parentNode.rightChild = newNode;

????????????????????return?true;

????????????????}

????????????}

????????}

????}

????return?false;

}

5.遍歷樹：　遍歷樹是根據(jù)一種特定的順序訪問樹的每一個(gè)節(jié)點(diǎn)砰盐。比較常用的有前序遍歷闷袒，中序遍歷和后序遍歷。而二叉搜索樹最常用的是中序遍歷岩梳。

　∧抑琛①、中序遍歷:左子樹——》根節(jié)點(diǎn)——》右子樹

　〖街怠②也物、前序遍歷:根節(jié)點(diǎn)——》左子樹——》右子樹

　　③列疗、后序遍歷:左子樹——》右子樹——》根節(jié)點(diǎn)

//中序遍歷

public?void?infixOrder(Node current){

????if(current !=?null){

????????infixOrder(current.leftChild);

????????System.out.print(current.data+" ");

????????infixOrder(current.rightChild);

????}

}

//前序遍歷

public?void?preOrder(Node current){

????if(current !=?null){

????????System.out.print(current.data+" ");

????????preOrder(current.leftChild);

????????preOrder(current.rightChild);

????}

}

//后序遍歷

public?void?postOrder(Node current){

????if(current !=?null){

????????postOrder(current.leftChild);

????????postOrder(current.rightChild);

????????System.out.print(current.data+" ");

????}

}

查找最大值和最小值：要找最小值滑蚯，先找根的左節(jié)點(diǎn)，然后一直找這個(gè)左節(jié)點(diǎn)的左節(jié)點(diǎn)抵栈，直到找到?jīng)]有左節(jié)點(diǎn)的節(jié)點(diǎn)告材，那么這個(gè)節(jié)點(diǎn)就是最小值。同理要找最大值古劲，一直找根節(jié)點(diǎn)的右節(jié)點(diǎn)斥赋，直到?jīng)]有右節(jié)點(diǎn)，則就是最大值产艾。

//找到最大值

public?Node findMax(){

????Node current = root;

????Node maxNode = current;

????while(current !=?null){

????????maxNode = current;

????????current = current.rightChild;

????}

????return?maxNode;

}

//找到最小值

public?Node findMin(){

????Node current = root;

????Node minNode = current;

????while(current !=?null){

????????minNode = current;

????????current = current.leftChild;

????}

????return?minNode;

}

6.刪除節(jié)點(diǎn)：

　刪除節(jié)點(diǎn)是二叉搜索樹中最復(fù)雜的操作疤剑，刪除的節(jié)點(diǎn)有三種情況，前兩種比較簡(jiǎn)單闷堡，但是第三種卻很復(fù)雜隘膘。

　　1、該節(jié)點(diǎn)是葉節(jié)點(diǎn)（沒有子節(jié)點(diǎn)）

　　2缚窿、該節(jié)點(diǎn)有一個(gè)子節(jié)點(diǎn)

　　3棘幸、該節(jié)點(diǎn)有兩個(gè)子節(jié)點(diǎn)

　　下面我們分別對(duì)這三種情況進(jìn)行講解焰扳。

　【肓恪①误续、刪除沒有子節(jié)點(diǎn)的節(jié)點(diǎn)

　　要?jiǎng)h除葉節(jié)點(diǎn)，只需要改變?cè)摴?jié)點(diǎn)的父節(jié)點(diǎn)引用該節(jié)點(diǎn)的值扫茅，即將其引用改為 null 即可蹋嵌。要?jiǎng)h除的節(jié)點(diǎn)依然存在，但是它已經(jīng)不是樹的一部分了葫隙，由于Java語言的垃圾回收機(jī)制栽烂，我們不需要非得把節(jié)點(diǎn)本身刪掉，一旦Java意識(shí)到程序不在與該節(jié)點(diǎn)有關(guān)聯(lián)恋脚，就會(huì)自動(dòng)把它清理出存儲(chǔ)器腺办。

@Override

public?boolean?delete(int?key) {

????Node current = root;

????Node parent = root;

????boolean?isLeftChild =?false;

????//查找刪除值，找不到直接返回false

????while(current.data != key){

????????parent = current;

????????if(current.data > key){

????????????isLeftChild =?true;

????????????current = current.leftChild;

????????}else{

????????????isLeftChild =?false;

????????????current = current.rightChild;

????????}

????????if(current ==?null){

????????????return?false;

????????}

????}

????//如果當(dāng)前節(jié)點(diǎn)沒有子節(jié)點(diǎn)

????if(current.leftChild ==?null?&& current.rightChild ==?null){

????????if(current == root){

????????????root =?null;

????????}else?if(isLeftChild){

????????????parent.leftChild =?null;

????????}else{

????????????parent.rightChild =?null;

????????}

????????return?true;

????}

????return?false;

}

7.刪除節(jié)點(diǎn)糟描，我們要先找到該節(jié)點(diǎn)怀喉，并記錄該節(jié)點(diǎn)的父節(jié)點(diǎn)。在檢查該節(jié)點(diǎn)是否有子節(jié)點(diǎn)船响。如果沒有子節(jié)點(diǎn)躬拢，接著檢查其是否是根節(jié)點(diǎn)，如果是根節(jié)點(diǎn)见间，只需要將其設(shè)置為null即可聊闯。如果不是根節(jié)點(diǎn)，是葉節(jié)點(diǎn)米诉，那么斷開父節(jié)點(diǎn)和其的關(guān)系即可菱蔬。

　②史侣、刪除有一個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn)

　　刪除有一個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn)汗销，我們只需要將其父節(jié)點(diǎn)原本指向該節(jié)點(diǎn)的引用，改為指向該節(jié)點(diǎn)的子節(jié)點(diǎn)即可抵窒。

//當(dāng)前節(jié)點(diǎn)有一個(gè)子節(jié)點(diǎn)

if(current.leftChild ==?null?&& current.rightChild !=?null){

????if(current == root){

????????root = current.rightChild;

????}else?if(isLeftChild){

????????parent.leftChild = current.rightChild;

????}else{

????????parent.rightChild = current.rightChild;

????}

????return?true;

}else{

????//current.leftChild != null && current.rightChild == null

????if(current == root){

????????root = current.leftChild;

????}else?if(isLeftChild){

????????parent.leftChild = current.leftChild;

????}else{

????????parent.rightChild = current.leftChild;

????}

????return?true;

}

③弛针、刪除有兩個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn)

當(dāng)刪除的節(jié)點(diǎn)存在兩個(gè)子節(jié)點(diǎn)，那么刪除之后李皇，兩個(gè)子節(jié)點(diǎn)的位置我們就沒辦法處理了削茁。既然處理不了，我們就想到一種辦法掉房，用另一個(gè)節(jié)點(diǎn)來代替被刪除的節(jié)點(diǎn)茧跋，那么用哪一個(gè)節(jié)點(diǎn)來代替呢？

　　我們知道二叉搜索樹中的節(jié)點(diǎn)是按照關(guān)鍵字來進(jìn)行排列的卓囚，某個(gè)節(jié)點(diǎn)的關(guān)鍵字次高節(jié)點(diǎn)是它的中序遍歷后繼節(jié)點(diǎn)瘾杭。用后繼節(jié)點(diǎn)來代替刪除的節(jié)點(diǎn)，顯然該二叉搜索樹還是有序的哪亿。

那么如何找到刪除節(jié)點(diǎn)的中序后繼節(jié)點(diǎn)呢粥烁？其實(shí)我們稍微分析贤笆，這實(shí)際上就是要找比刪除節(jié)點(diǎn)關(guān)鍵值大的節(jié)點(diǎn)集合中最小的一個(gè)節(jié)點(diǎn)，只有這樣代替刪除節(jié)點(diǎn)后才能滿足二叉搜索樹的特性讨阻。

　　后繼節(jié)點(diǎn)也就是：比刪除節(jié)點(diǎn)大的最小節(jié)點(diǎn)芥永。

　　算法：程序找到刪除節(jié)點(diǎn)的右節(jié)點(diǎn)，(注意這里前提是刪除節(jié)點(diǎn)存在左右兩個(gè)子節(jié)點(diǎn)钝吮，如果不存在則是刪除情況的前面兩種)埋涧，然后轉(zhuǎn)到該右節(jié)點(diǎn)的左子節(jié)點(diǎn)，依次順著左子節(jié)點(diǎn)找下去奇瘦，最后一個(gè)左子節(jié)點(diǎn)即是后繼節(jié)點(diǎn)棘催；如果該右節(jié)點(diǎn)沒有左子節(jié)點(diǎn)，那么該右節(jié)點(diǎn)便是后繼節(jié)點(diǎn)耳标。

　需要確定后繼節(jié)點(diǎn)沒有子節(jié)點(diǎn)巧鸭，如果后繼節(jié)點(diǎn)存在子節(jié)點(diǎn)，那么又要分情況討論了麻捻。

　「偃浴①、后繼節(jié)點(diǎn)是刪除節(jié)點(diǎn)的右子節(jié)點(diǎn)

　　這種情況簡(jiǎn)單贸毕，只需要將后繼節(jié)點(diǎn)表示的子樹移到被刪除節(jié)點(diǎn)的位置即可郑叠！

public?Node getSuccessor(Node delNode){

????Node successorParent = delNode;

????Node successor = delNode;

????Node current = delNode.rightChild;

????while(current !=?null){

????????successorParent = successor;

????????successor = current;

????????current = current.leftChild;

????}

????//將后繼節(jié)點(diǎn)替換刪除節(jié)點(diǎn)

????if(successor != delNode.rightChild){

????????successorParent.leftChild = successor.rightChild;

????????successor.rightChild = delNode.rightChild;

????}

????return?successor;

}

④、刪除有必要嗎明棍？

?　　通過上面的刪除分類討論乡革，我們發(fā)現(xiàn)刪除其實(shí)是挺復(fù)雜的，那么其實(shí)我們可以不用真正的刪除該節(jié)點(diǎn)摊腋，只需要在Node類中增加一個(gè)標(biāo)識(shí)字段isDelete沸版，當(dāng)該字段為true時(shí)，表示該節(jié)點(diǎn)已經(jīng)刪除兴蒸，反正沒有刪除视粮。那么我們?cè)谧霰热鏵ind()等操作的時(shí)候，要先判斷isDelete字段是否為true橙凳。這樣刪除的節(jié)點(diǎn)并不會(huì)改變樹的結(jié)構(gòu)蕾殴。

public?class?Node {

????int?data;?//節(jié)點(diǎn)數(shù)據(jù)

????Node leftChild;?//左子節(jié)點(diǎn)的引用

????Node rightChild;?//右子節(jié)點(diǎn)的引用

????boolean?isDelete;//表示節(jié)點(diǎn)是否被刪除

}

8.二叉樹的效率：

從前面的大部分對(duì)樹的操作來看，都需要從根節(jié)點(diǎn)到下一層一層的查找岛啸。

一顆滿樹钓觉，每層節(jié)點(diǎn)數(shù)大概為2n-1，那么最底層的節(jié)點(diǎn)個(gè)數(shù)比樹的其它節(jié)點(diǎn)數(shù)多1坚踩，因此荡灾，查找、插入或刪除節(jié)點(diǎn)的操作大約有一半都需要找到底層的節(jié)點(diǎn)，另外四分之一的節(jié)點(diǎn)在倒數(shù)第二層批幌，依次類推础锐。

總共N層共有2n-1個(gè)節(jié)點(diǎn)，那么時(shí)間復(fù)雜度為O(logn),底數(shù)為2逼裆。

　　在有1000000 個(gè)數(shù)據(jù)項(xiàng)的無序數(shù)組和鏈表中，查找數(shù)據(jù)項(xiàng)平均會(huì)比較500000 次赦政，但是在有1000000個(gè)節(jié)點(diǎn)的二叉樹中胜宇，只需要20次或更少的比較即可。

　　有序數(shù)組可以很快的找到數(shù)據(jù)項(xiàng)恢着，但是插入數(shù)據(jù)項(xiàng)的平均需要移動(dòng) 500000 次數(shù)據(jù)項(xiàng)桐愉，在 1000000 個(gè)節(jié)點(diǎn)的二叉樹中插入數(shù)據(jù)項(xiàng)需要20次或更少比較，在加上很短的時(shí)間來連接數(shù)據(jù)項(xiàng)掰派。

　　同樣从诲，從 1000000 個(gè)數(shù)據(jù)項(xiàng)的數(shù)組中刪除一個(gè)數(shù)據(jù)項(xiàng)平均需要移動(dòng) 500000 個(gè)數(shù)據(jù)項(xiàng)，而在 1000000 個(gè)節(jié)點(diǎn)的二叉樹中刪除節(jié)點(diǎn)只需要20次或更少的次數(shù)來找到他靡羡，然后在花一點(diǎn)時(shí)間來找到它的后繼節(jié)點(diǎn)系洛，一點(diǎn)時(shí)間來斷開節(jié)點(diǎn)以及連接后繼節(jié)點(diǎn)。

　　所以略步，樹對(duì)所有常用數(shù)據(jù)結(jié)構(gòu)的操作都有很高的效率描扯。

　　遍歷可能不如其他操作快，但是在大型數(shù)據(jù)庫中趟薄，遍歷是很少使用的操作绽诚，它更常用于程序中的輔助算法來解析算術(shù)或其它表達(dá)式。

9.用數(shù)組表示樹：

用數(shù)組表示樹杭煎，那么節(jié)點(diǎn)是存在數(shù)組中的恩够，節(jié)點(diǎn)在數(shù)組中的位置對(duì)應(yīng)于它在樹中的位置。下標(biāo)為 0 的節(jié)點(diǎn)是根羡铲，下標(biāo)為 1 的節(jié)點(diǎn)是根的左子節(jié)點(diǎn)蜂桶，以此類推，按照從左到右的順序存儲(chǔ)樹的每一層也切。

樹中的每個(gè)位置屎飘，無論是否存在節(jié)點(diǎn)，都對(duì)應(yīng)于數(shù)組中的一個(gè)位置贾费，樹中沒有節(jié)點(diǎn)的在數(shù)組中用0或者null表示钦购。

　　假設(shè)節(jié)點(diǎn)的索引值為index，那么節(jié)點(diǎn)的左子節(jié)點(diǎn)是 2*index+1褂萧，節(jié)點(diǎn)的右子節(jié)點(diǎn)是 2*index+2押桃，它的父節(jié)點(diǎn)是 （index-1）/2。

　　在大多數(shù)情況下导犹，使用數(shù)組表示樹效率是很低的唱凯，不滿的節(jié)點(diǎn)和刪除掉的節(jié)點(diǎn)都會(huì)在數(shù)組中留下洞羡忘，浪費(fèi)存儲(chǔ)空間。更壞的是磕昼，刪除節(jié)點(diǎn)如果要移動(dòng)子樹的話卷雕，子樹中的每個(gè)節(jié)點(diǎn)都要移到數(shù)組中新的位置，這是很費(fèi)時(shí)的票从。

　　不過如果不允許刪除操作漫雕，數(shù)組表示可能會(huì)很有用，尤其是因?yàn)槟撤N原因要?jiǎng)討B(tài)的為每個(gè)字節(jié)分配空間非常耗時(shí)峰鄙。

10.哈夫曼(Huffman)編碼：

　我們知道計(jì)算機(jī)里每個(gè)字符在沒有壓縮的文本文件中由一個(gè)字節(jié)（比如ASCII碼）或兩個(gè)字節(jié)（比如Unicode,這個(gè)編碼在各種語言中通用）表示浸间，在這些方案中，每個(gè)字符需要相同的位數(shù)吟榴。

　　有很多壓縮數(shù)據(jù)的方法魁蒜，就是減少表示最常用字符的位數(shù)量，比如英語中吩翻，E是最常用的字母兜看，我們可以只用兩位01來表示，2位有四種組合：00狭瞎、01铣减、10、11脚作，那么我們可以用這四種組合表示四種常用的字符嗎葫哗？

答案是不可以的，因?yàn)樵诰幋a序列中是沒有空格或其他特殊字符存在的球涛，全都是有0和1構(gòu)成的序列劣针，比如E用01來表示，X用01011000表示亿扁，那么在解碼的時(shí)候就弄不清楚01是表示E還是表示X的起始部分捺典，所以在編碼的時(shí)候就定下了一個(gè)規(guī)則：每個(gè)代碼都不能是其它代碼的前綴。

　　①从祝、哈夫曼編碼

二叉樹中有一種特別的樹——哈夫曼樹（最優(yōu)二叉樹）襟己，其通過某種規(guī)則（權(quán)值）來構(gòu)造出一哈夫曼二叉樹，在這個(gè)二叉樹中牍陌，只有葉子節(jié)點(diǎn)才是有效的數(shù)據(jù)節(jié)點(diǎn)（很重要）擎浴，其他的非葉子節(jié)點(diǎn)是為了構(gòu)造出哈夫曼而引入的！

哈夫曼編碼是一個(gè)通過哈夫曼樹進(jìn)行的一種編碼毒涧，一般情況下贮预，以字符：‘0’與‘1’表示。編碼的實(shí)現(xiàn)過程很簡(jiǎn)單，只要實(shí)現(xiàn)哈夫曼樹仿吞，通過遍歷哈夫曼樹滑频，規(guī)定向左子樹遍歷一個(gè)節(jié)點(diǎn)編碼為“0”，向右遍歷一個(gè)節(jié)點(diǎn)編碼為“1”唤冈，結(jié)束條件就是遍歷到葉子節(jié)點(diǎn)峡迷！因?yàn)樯厦嬲f過：哈夫曼樹葉子節(jié)點(diǎn)才是有效數(shù)據(jù)節(jié)點(diǎn)！

　我們用01表示S你虹，用00表示空格后绘搞，就不能用01和11表示某個(gè)字符了，因?yàn)樗鼈兪瞧渌址那熬Y售葡。在看三位的組合看杭，分別有000,001,010,100,101,110和111忠藤，A是010挟伙，I是110，為什么沒有其它三位的組合了呢模孩？因?yàn)橐阎遣荒苡?1和11開始的組合了尖阔，那么就減少了四種選擇，同時(shí)011用于U和換行符的開始榨咐，111用于E和Y的開始介却，這樣就只剩下2個(gè)三位的組合了，同理可以理解為什么只有三個(gè)四位的代碼可用块茁。

　　所以對(duì)于消息：SUSIE SAYS IT IS EASY

　　哈夫曼編碼為：100111110110111100100101110100011001100011010001111010101110

　〕菘馈②、哈夫曼解碼

　　如果收到上面的一串哈夫曼編碼数焊，怎么解碼呢永淌？消息中出現(xiàn)的字符在哈夫曼樹中是葉節(jié)點(diǎn)，也就是沒有子節(jié)點(diǎn)佩耳，如下圖：它們?cè)谙⒅谐霈F(xiàn)的頻率越高遂蛀，在樹中的位置就越高，每個(gè)圓圈外面的數(shù)字就是頻率干厚，非葉節(jié)點(diǎn)外面的數(shù)字是它子節(jié)點(diǎn)數(shù)字的和李滴。

　　每個(gè)字符都從根開始，如果遇到0蛮瞄，就向左走到下一個(gè)節(jié)點(diǎn)所坯，如果遇到1，就向右挂捅。比如字符A是010包竹，那么先向左，再向右，再向左周瞎，就找到了A苗缩，其它的依次類推。

總結(jié)：樹是由邊和節(jié)點(diǎn)構(gòu)成声诸，根節(jié)點(diǎn)是樹最頂端的節(jié)點(diǎn)酱讶，它沒有父節(jié)點(diǎn)；二叉樹中彼乌，最多有兩個(gè)子節(jié)點(diǎn)泻肯；某個(gè)節(jié)點(diǎn)的左子樹每個(gè)節(jié)點(diǎn)都比該節(jié)點(diǎn)的關(guān)鍵字值小，右子樹的每個(gè)節(jié)點(diǎn)都比該節(jié)點(diǎn)的關(guān)鍵字值大慰照，那么這種樹稱為二叉搜索樹灶挟，其查找、插入毒租、刪除的時(shí)間復(fù)雜度都為logN稚铣；可以通過前序遍歷、中序遍歷墅垮、后序遍歷來遍歷樹惕医，前序是根節(jié)點(diǎn)-左子樹-右子樹，中序是左子樹-根節(jié)點(diǎn)-右子樹算色，后序是左子樹-右子樹-根節(jié)點(diǎn)抬伺；刪除一個(gè)節(jié)點(diǎn)只需要斷開指向它的引用即可；哈夫曼樹是二叉樹灾梦，用于數(shù)據(jù)壓縮算法峡钓，最經(jīng)常出現(xiàn)的字符編碼位數(shù)最少，很少出現(xiàn)的字符編碼位數(shù)多一些若河。