1、樹(shù)

樹(shù)（tree）是一種抽象數(shù)據(jù)類型（ADT），用來(lái)模擬具有樹(shù)狀結(jié)構(gòu)性質(zhì)的數(shù)據(jù)集合。它是由n（n>0）個(gè)有限節(jié)點(diǎn)通過(guò)連接它們的邊組成一個(gè)具有層次關(guān)系的集合。把它叫做“樹(shù)”是因?yàn)樗雌饋?lái)像一棵倒掛的樹(shù)，也就是說(shuō)它是根朝上，而葉朝下的。

①、節(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)中通常表示引用。

樹(shù)有很多種，向上面的一個(gè)節(jié)點(diǎn)有多余兩個(gè)的子節(jié)點(diǎn)的樹(shù)，稱為多路樹(shù)，后面會(huì)講解2-3-4樹(shù)和外部存儲(chǔ)都是多路樹(shù)的例子。而每個(gè)節(jié)點(diǎn)最多只能有兩個(gè)子節(jié)點(diǎn)的一種形式稱為二叉樹(shù)，這也是本篇博客講解的重點(diǎn)。

樹(shù)的常用術(shù)語(yǔ)

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

②、根：樹(shù)頂端的節(jié)點(diǎn)稱為根。一棵樹(shù)只有一個(gè)根，如果要把一個(gè)節(jié)點(diǎn)和邊的集合稱為樹(shù)，那么從根到其他任何一個(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)含有的子樹(shù)的根節(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)：沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)稱為葉節(jié)點(diǎn)，也叫葉子節(jié)點(diǎn)，比如上圖的H、E、F、G都是葉子節(jié)點(diǎn)。

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

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

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

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

2、二叉樹(shù)

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

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

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

二叉搜索樹(shù)要求：若它的左子樹(shù)不空，則左子樹(shù)上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值； 若它的右子樹(shù)不空，則右子樹(shù)上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值； 它的左、右子樹(shù)也分別為二叉排序樹(shù)。

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

二叉樹(shù)的節(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);
    }
 
}

二叉樹(shù)的具體方法：

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)開(kāi)始遍歷。

①、查找值比當(dāng)前節(jié)點(diǎn)值大，則搜索右子樹(shù)；

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

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

//查找節(jié)點(diǎn)
public Node find(int key) {
    Node current = root;
    while(current != null){
        if(current.data > key){//當(dāng)前值比查找值大，搜索左子樹(shù)
            current = current.leftChild;
        }else if(current.data < key){//當(dāng)前值比查找值小，搜索右子樹(shù)
            current = current.rightChild;
        }else{
            return current;
        }
    }
    return null;//遍歷完整個(gè)樹(shù)沒(méi)找到，返回null
}
　　用變量

用變量current來(lái)保存當(dāng)前查找的節(jié)點(diǎn)，參數(shù)key是要查找的值，剛開(kāi)始查找將根節(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è)樹(shù)遍歷完全，即current == null，那么說(shuō)明沒(méi)找到查找值，返回null。

樹(shù)的效率：查找節(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。

我看評(píng)論有對(duì)這里的時(shí)間復(fù)雜度不理解，這里解釋一下，O(logN)，N表示的是二叉樹(shù)節(jié)點(diǎn)的總數(shù)，而不是層數(shù)。

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

要插入節(jié)點(diǎn)，必須先找到插入的位置。與查找操作相似，由于二叉搜索樹(shù)的特殊性，待插入的節(jié)點(diǎn)也需要從根節(jié)點(diǎn)開(kāi)始進(jìn)行比較，小于根節(jié)點(diǎn)則與根節(jié)點(diǎn)左子樹(shù)比較，反之則與右子樹(shù)比較，直到左子樹(shù)為空或右子樹(shù)為空，則插入到相應(yīng)為空的位置，在比較的過(guò)程中要注意保存父節(jié)點(diǎn)的信息 及 待插入的位置是父節(jié)點(diǎn)的左子樹(shù)還是右子樹(shù)，才能插入到正確的位置。

//插入節(jié)點(diǎn)
public boolean insert(int data) {
    Node newNode = new Node(data);
    if(root == null){//當(dāng)前樹(shù)為空樹(shù)，沒(méi)有任何節(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、遍歷樹(shù)

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

• ①、中序遍歷:左子樹(shù)——》根節(jié)點(diǎn)——》右子樹(shù)
• ②、前序遍歷:根節(jié)點(diǎn)——》左子樹(shù)——》右子樹(shù)
• ③、后序遍歷:左子樹(shù)——》右子樹(shù)——》根節(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+" ");
    }
}

6、查找最大值和最小值

這沒(méi)什么好說(shuō)的，要找最小值，先找根的左節(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;
}

7、刪除節(jié)點(diǎn)　　

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

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

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

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

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

①、刪除沒(méi)有子節(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)不是樹(shù)的一部分了，由于Java語(yǔ)言的垃圾回收機(jī)制，我們不需要非得把節(jié)點(diǎn)本身刪掉，一旦Java意識(shí)到程序不在與該節(jié)點(diǎn)有關(guān)聯(lián)，就會(huì)自動(dòng)把它清理出存儲(chǔ)器?！　?/p>

@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)沒(méi)有子節(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;
}

刪除節(jié)點(diǎn)，我們要先找到該節(jié)點(diǎn)，并記錄該節(jié)點(diǎn)的父節(jié)點(diǎn)。在檢查該節(jié)點(diǎn)是否有子節(jié)點(diǎn)。如果沒(méi)有子節(jié)點(diǎn)，接著檢查其是否是根節(jié)點(diǎn)，如果是根節(jié)點(diǎn)，只需要將其設(shè)置為null即可。如果不是根節(jié)點(diǎn)，是葉節(jié)點(diǎn)，那么斷開(kāi)父節(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)的位置我們就沒(méi)辦法處理了。既然處理不了，我們就想到一種辦法，用另一個(gè)節(jié)點(diǎn)來(lái)代替被刪除的節(jié)點(diǎn)，那么用哪一個(gè)節(jié)點(diǎn)來(lái)代替呢？

我們知道二叉搜索樹(shù)中的節(jié)點(diǎn)是按照關(guān)鍵字來(lái)進(jìn)行排列的，某個(gè)節(jié)點(diǎn)的關(guān)鍵字次高節(jié)點(diǎn)是它的中序遍歷后繼節(jié)點(diǎn)。用后繼節(jié)點(diǎn)來(lái)代替刪除的節(jié)點(diǎn)，顯然該二叉搜索樹(shù)還是有序的。（這里用后繼節(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)后才能滿足二叉搜索樹(shù)的特性。

后繼節(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)沒(méi)有左子節(jié)點(diǎn)，那么該右節(jié)點(diǎn)便是后繼節(jié)點(diǎn)。

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

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

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

②、后繼節(jié)點(diǎn)是刪除節(jié)點(diǎn)的右子節(jié)點(diǎn)的左子節(jié)點(diǎn)

④、刪除有必要嗎？

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

8、二叉樹(shù)的效率

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

一顆滿樹(shù)，每層節(jié)點(diǎn)數(shù)大概為2n-1，那么最底層的節(jié)點(diǎn)個(gè)數(shù)比樹(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)的無(wú)序數(shù)組和鏈表中，查找數(shù)據(jù)項(xiàng)平均會(huì)比較500000 次，但是在有1000000個(gè)節(jié)點(diǎn)的二叉樹(shù)中，只需要20次或更少的比較即可。

有序數(shù)組可以很快的找到數(shù)據(jù)項(xiàng)，但是插入數(shù)據(jù)項(xiàng)的平均需要移動(dòng) 500000 次數(shù)據(jù)項(xiàng)，在 1000000 個(gè)節(jié)點(diǎn)的二叉樹(shù)中插入數(shù)據(jù)項(xiàng)需要20次或更少比較，在加上很短的時(shí)間來(lái)連接數(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)的二叉樹(shù)中刪除節(jié)點(diǎn)只需要20次或更少的次數(shù)來(lái)找到他，然后在花一點(diǎn)時(shí)間來(lái)找到它的后繼節(jié)點(diǎn)，一點(diǎn)時(shí)間來(lái)斷開(kāi)節(jié)點(diǎn)以及連接后繼節(jié)點(diǎn)。

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

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

9、用數(shù)組表示樹(shù)

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

樹(shù)中的每個(gè)位置，無(wú)論是否存在節(jié)點(diǎn)，都對(duì)應(yīng)于數(shù)組中的一個(gè)位置，樹(shù)中沒(méi)有節(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ù)組表示樹(shù)效率是很低的，不滿的節(jié)點(diǎn)和刪除掉的節(jié)點(diǎn)都會(huì)在數(shù)組中留下洞，浪費(fèi)存儲(chǔ)空間。更壞的是，刪除節(jié)點(diǎn)如果要移動(dòng)子樹(shù)的話，子樹(shù)中的每個(gè)節(jié)點(diǎn)都要移到數(shù)組中新的位置，這是很費(fèi)時(shí)的。

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

10、完整的BinaryTree代碼

Node.java

package com.ys.tree;
 
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)是否被刪除
     
    public Node(int data){
        this.data = data;
    }
    //打印節(jié)點(diǎn)內(nèi)容
    public void display(){
        System.out.println(data);
    }
 
}

Tree.java

package com.ys.tree;
 
public interface Tree {
    //查找節(jié)點(diǎn)
    public Node find(int key);
    //插入新節(jié)點(diǎn)
    public boolean insert(int data);
     
    //中序遍歷
    public void infixOrder(Node current);
    //前序遍歷
    public void preOrder(Node current);
    //后序遍歷
    public void postOrder(Node current);
     
    //查找最大值
    public Node findMax();
    //查找最小值
    public Node findMin();
     
    //刪除節(jié)點(diǎn)
    public boolean delete(int key);
     
    //Other Method......
}

BinaryTree.java

package com.ys.tree;
 
public class BinaryTree implements Tree {
    //表示根節(jié)點(diǎn)
    private Node root;
 
    //查找節(jié)點(diǎn)
    public Node find(int key) {
        Node current = root;
        while(current != null){
            if(current.data > key){//當(dāng)前值比查找值大，搜索左子樹(shù)
                current = current.leftChild;
            }else if(current.data < key){//當(dāng)前值比查找值小，搜索右子樹(shù)
                current = current.rightChild;
            }else{
                return current;
            }
        }
        return null;//遍歷完整個(gè)樹(shù)沒(méi)找到，返回null
    }
 
    //插入節(jié)點(diǎn)
    public boolean insert(int data) {
        Node newNode = new Node(data);
        if(root == null){//當(dāng)前樹(shù)為空樹(shù)，沒(méi)有任何節(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;
    }
     
    //中序遍歷
    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+" ");
            infixOrder(current.leftChild);
            infixOrder(current.rightChild);
        }
    }
     
    //后序遍歷
    public void postOrder(Node current){
        if(current != null){
            infixOrder(current.leftChild);
            infixOrder(current.rightChild);
            System.out.print(current.data+" ");
        }
    }
    //找到最大值
    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;
    }
     
    @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)沒(méi)有子節(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;
             
            //當(dāng)前節(jié)點(diǎn)有一個(gè)子節(jié)點(diǎn)，右子節(jié)點(diǎn)
        }else 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;
            //當(dāng)前節(jié)點(diǎn)有一個(gè)子節(jié)點(diǎn)，左子節(jié)點(diǎn)
        }else if(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;
        }else{
            //當(dāng)前節(jié)點(diǎn)存在兩個(gè)子節(jié)點(diǎn)
            Node successor = getSuccessor(current);
            if(current == root){
                root= successor;
            }else if(isLeftChild){
                parent.leftChild = successor;
            }else{
                parent.rightChild = successor;
            }
            successor.leftChild = current.leftChild;
        }
        return false;
         
    }
 
    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)的右子節(jié)點(diǎn)，將后繼節(jié)點(diǎn)替換刪除節(jié)點(diǎn)
        if(successor != delNode.rightChild){
            successorParent.leftChild = successor.rightChild;
            successor.rightChild = delNode.rightChild;
        }
         
        return successor;
    }
     
    public static void main(String[] args) {
        BinaryTree bt = new BinaryTree();
        bt.insert(50);
        bt.insert(20);
        bt.insert(80);
        bt.insert(10);
        bt.insert(30);
        bt.insert(60);
        bt.insert(90);
        bt.insert(25);
        bt.insert(85);
        bt.insert(100);
        bt.delete(10);//刪除沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)
        bt.delete(30);//刪除有一個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn)
        bt.delete(80);//刪除有兩個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn)
        System.out.println(bt.findMax().data);
        System.out.println(bt.findMin().data);
        System.out.println(bt.find(100));
        System.out.println(bt.find(200));
         
    }
 
}

11、哈夫曼(Huffman)編碼

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

有很多壓縮數(shù)據(jù)的方法，就是減少表示最常用字符的位數(shù)量，比如英語(yǔ)中，E是最常用的字母，我們可以只用兩位01來(lái)表示，2位有四種組合：00、01、10、11，那么我們可以用這四種組合表示四種常用的字符嗎？

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

①、哈夫曼編碼　

二叉樹(shù)中有一種特別的樹(shù)——哈夫曼樹(shù)（最優(yōu)二叉樹(shù)），其通過(guò)某種規(guī)則（權(quán)值）來(lái)構(gòu)造出一哈夫曼二叉樹(shù)，在這個(gè)二叉樹(shù)中，只有葉子節(jié)點(diǎn)才是有效的數(shù)據(jù)節(jié)點(diǎn)（很重要），其他的非葉子節(jié)點(diǎn)是為了構(gòu)造出哈夫曼而引入的！
哈夫曼編碼是一個(gè)通過(guò)哈夫曼樹(shù)進(jìn)行的一種編碼，一般情況下，以字符：‘0’與‘1’表示。編碼的實(shí)現(xiàn)過(guò)程很簡(jiǎn)單，只要實(shí)現(xiàn)哈夫曼樹(shù)，通過(guò)遍歷哈夫曼樹(shù)，規(guī)定向左子樹(shù)遍歷一個(gè)節(jié)點(diǎn)編碼為“0”，向右遍歷一個(gè)節(jié)點(diǎn)編碼為“1”，結(jié)束條件就是遍歷到葉子節(jié)點(diǎn)！因?yàn)樯厦嬲f(shuō)過(guò)：哈夫曼樹(shù)葉子節(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，為什么沒(méi)有其它三位的組合了呢？因?yàn)橐阎遣荒苡?1和11開(kāi)始的組合了，那么就減少了四種選擇，同時(shí)011用于U和換行符的開(kāi)始，111用于E和Y的開(kāi)始，這樣就只剩下2個(gè)三位的組合了，同理可以理解為什么只有三個(gè)四位的代碼可用。

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

哈夫曼編碼為：100111110110111100100101110100011001100011010001111010101110

②、哈夫曼解碼

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

每個(gè)字符都從根開(kāi)始，如果遇到0，就向左走到下一個(gè)節(jié)點(diǎn)，如果遇到1，就向右。比如字符A是010，那么先向左，再向右，再向左，就找到了A，其它的依次類推。

12、總結(jié)

樹(shù)是由邊和節(jié)點(diǎn)構(gòu)成，根節(jié)點(diǎn)是樹(shù)最頂端的節(jié)點(diǎn)，它沒(méi)有父節(jié)點(diǎn)；二叉樹(shù)中，最多有兩個(gè)子節(jié)點(diǎn)；某個(gè)節(jié)點(diǎn)的左子樹(shù)每個(gè)節(jié)點(diǎn)都比該節(jié)點(diǎn)的關(guān)鍵字值小，右子樹(shù)的每個(gè)節(jié)點(diǎn)都比該節(jié)點(diǎn)的關(guān)鍵字值大，那么這種樹(shù)稱為二叉搜索樹(shù)，其查找、插入、刪除的時(shí)間復(fù)雜度都為logN；可以通過(guò)前序遍歷、中序遍歷、后序遍歷來(lái)遍歷樹(shù)，前序是根節(jié)點(diǎn)-左子樹(shù)-右子樹(shù)，中序是左子樹(shù)-根節(jié)點(diǎn)-右子樹(shù)，后序是左子樹(shù)-右子樹(shù)-根節(jié)點(diǎn)；刪除一個(gè)節(jié)點(diǎn)只需要斷開(kāi)指向它的引用即可；哈夫曼樹(shù)是二叉樹(shù)，用于數(shù)據(jù)壓縮算法，最經(jīng)常出現(xiàn)的字符編碼位數(shù)最少，很少出現(xiàn)的字符編碼位數(shù)多一些。

本篇文章就到這里了，希望能夠給你帶來(lái)幫助，也希望您能夠多多關(guān)注腳本之家的更多內(nèi)容!

最新評(píng)論