" />

欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

帶你了解Java數(shù)據(jù)結(jié)構(gòu)和算法之二叉樹

 更新時間:2022年01月21日 14:28:42   作者:YSOcean  
這篇文章主要為大家介紹了Java數(shù)據(jù)結(jié)構(gòu)和算法之二叉樹,具有一定的參考價值,感興趣的小伙伴們可以參考一下,希望能夠給你帶來幫助

1、樹

樹(tree)是一種抽象數(shù)據(jù)類型(ADT),用來模擬具有樹狀結(jié)構(gòu)性質(zhì)的數(shù)據(jù)集合。它是由n(n>0)個有限節(jié)點通過連接它們的邊組成一個具有層次關(guān)系的集合。把它叫做“樹”是因為它看起來像一棵倒掛的樹,也就是說它是根朝上,而葉朝下的。

①、節(jié)點:上圖的圓圈,比如A,B,C等都是表示節(jié)點。節(jié)點一般代表一些實體,在java面向?qū)ο缶幊讨校?jié)點一般代表對象。

②、邊:連接節(jié)點的線稱為邊,邊表示節(jié)點的關(guān)聯(lián)關(guān)系。一般從一個節(jié)點到另一個節(jié)點的唯一方法就是沿著一條順著有邊的道路前進。在Java當(dāng)中通常表示引用。

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

樹的常用術(shù)語

①、路徑:順著節(jié)點的邊從一個節(jié)點走到另一個節(jié)點,所經(jīng)過的節(jié)點的順序排列就稱為“路徑”。

②、根:樹頂端的節(jié)點稱為根。一棵樹只有一個根,如果要把一個節(jié)點和邊的集合稱為樹,那么從根到其他任何一個節(jié)點都必須有且只有一條路徑。A是根節(jié)點。

③、父節(jié)點:若一個節(jié)點含有子節(jié)點,則這個節(jié)點稱為其子節(jié)點的父節(jié)點;B是D的父節(jié)點。

④、子節(jié)點:一個節(jié)點含有的子樹的根節(jié)點稱為該節(jié)點的子節(jié)點;D是B的子節(jié)點。

⑤、兄弟節(jié)點:具有相同父節(jié)點的節(jié)點互稱為兄弟節(jié)點;比如上圖的D和E就互稱為兄弟節(jié)點。

⑥、葉節(jié)點:沒有子節(jié)點的節(jié)點稱為葉節(jié)點,也叫葉子節(jié)點,比如上圖的H、E、F、G都是葉子節(jié)點。

⑦、子樹:每個節(jié)點都可以作為子樹的根,它和它所有的子節(jié)點、子節(jié)點的子節(jié)點等都包含在子樹中。

⑧、節(jié)點的層次:從根開始定義,根為第一層,根的子節(jié)點為第二層,以此類推。

⑨、深度:對于任意節(jié)點n,n的深度為從根到n的唯一路徑長,根的深度為0;

⑩、高度:對于任意節(jié)點n,n的高度為從n到一片樹葉的最長路徑長,所有樹葉的高度為0;

2、二叉樹

二叉樹:樹的每個節(jié)點最多只能有兩個子節(jié)點

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

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

二叉搜索樹要求:若它的左子樹不空,則左子樹上所有結(jié)點的值均小于它的根結(jié)點的值; 若它的右子樹不空,則右子樹上所有結(jié)點的值均大于它的根結(jié)點的值; 它的左、右子樹也分別為二叉排序樹。

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

二叉樹的節(jié)點類:

package com.ys.tree;
 
public class Node {
    private Object data;    //節(jié)點數(shù)據(jù)
    private Node leftChild; //左子節(jié)點的引用
    private Node rightChild; //右子節(jié)點的引用
    //打印節(jié)點內(nèi)容
    public void display(){
        System.out.println(data);
    }
 
}

二叉樹的具體方法:

package com.ys.tree;
 
public interface Tree {
    //查找節(jié)點
    public Node find(Object key);
    //插入新節(jié)點
    public boolean insert(Object key);
    //刪除節(jié)點
    public boolean delete(Object key);
    //Other Method......
}

3、查找節(jié)點

查找某個節(jié)點,我們必須從根節(jié)點開始遍歷。

①、查找值比當(dāng)前節(jié)點值大,則搜索右子樹;

②、查找值等于當(dāng)前節(jié)點值,停止搜索(終止條件);

③、查找值小于當(dāng)前節(jié)點值,則搜索左子樹;

//查找節(jié)點
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;//遍歷完整個樹沒找到,返回null
}
  用變量

用變量current來保存當(dāng)前查找的節(jié)點,參數(shù)key是要查找的值,剛開始查找將根節(jié)點賦值到current。接在在while循環(huán)中,將要查找的值和current保存的節(jié)點進行對比。如果key小于當(dāng)前節(jié)點,則搜索當(dāng)前節(jié)點的左子節(jié)點,如果大于,則搜索右子節(jié)點,如果等于,則直接返回節(jié)點信息。當(dāng)整個樹遍歷完全,即current == null,那么說明沒找到查找值,返回null。

樹的效率:查找節(jié)點的時間取決于這個節(jié)點所在的層數(shù),每一層最多有2n-1個節(jié)點,總共N層共有2n-1個節(jié)點,那么時間復(fù)雜度為O(logN),底數(shù)為2。

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

4、插入節(jié)點

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

//插入節(jié)點
public boolean insert(int data) {
    Node newNode = new Node(data);
    if(root == null){//當(dāng)前樹為空樹,沒有任何節(jié)點
        root = newNode;
        return true;
    }else{
        Node current = root;
        Node parentNode = null;
        while(current != null){
            parentNode = current;
            if(current.data > data){//當(dāng)前值比插入值大,搜索左子節(jié)點
                current = current.leftChild;
                if(current == null){//左子節(jié)點為空,直接將新值插入到該節(jié)點
                    parentNode.leftChild = newNode;
                    return true;
                }
            }else{
                current = current.rightChild;
                if(current == null){//右子節(jié)點為空,直接將新值插入到該節(jié)點
                    parentNode.rightChild = newNode;
                    return true;
                }
            }
        }
    }
    return false;
}

5、遍歷樹

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

  • ①、中序遍歷:左子樹——》根節(jié)點——》右子樹
  • ②、前序遍歷:根節(jié)點——》左子樹——》右子樹
  • ③、后序遍歷:左子樹——》右子樹——》根節(jié)點  

//中序遍歷
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、查找最大值和最小值

這沒什么好說的,要找最小值,先找根的左節(jié)點,然后一直找這個左節(jié)點的左節(jié)點,直到找到?jīng)]有左節(jié)點的節(jié)點,那么這個節(jié)點就是最小值。同理要找最大值,一直找根節(jié)點的右節(jié)點,直到?jīng)]有右節(jié)點,則就是最大值。

//找到最大值
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é)點  

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

1、該節(jié)點是葉節(jié)點(沒有子節(jié)點)

2、該節(jié)點有一個子節(jié)點

3、該節(jié)點有兩個子節(jié)點

下面我們分別對這三種情況進行講解。

①、刪除沒有子節(jié)點的節(jié)點

要刪除葉節(jié)點,只需要改變該節(jié)點的父節(jié)點引用該節(jié)點的值,即將其引用改為 null 即可。要刪除的節(jié)點依然存在,但是它已經(jīng)不是樹的一部分了,由于Java語言的垃圾回收機制,我們不需要非得把節(jié)點本身刪掉,一旦Java意識到程序不在與該節(jié)點有關(guān)聯(lián),就會自動把它清理出存儲器。  

@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é)點沒有子節(jié)點
    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é)點,我們要先找到該節(jié)點,并記錄該節(jié)點的父節(jié)點。在檢查該節(jié)點是否有子節(jié)點。如果沒有子節(jié)點,接著檢查其是否是根節(jié)點,如果是根節(jié)點,只需要將其設(shè)置為null即可。如果不是根節(jié)點,是葉節(jié)點,那么斷開父節(jié)點和其的關(guān)系即可。

②、刪除有一個子節(jié)點的節(jié)點

刪除有一個子節(jié)點的節(jié)點,我們只需要將其父節(jié)點原本指向該節(jié)點的引用,改為指向該節(jié)點的子節(jié)點即可。  

//當(dāng)前節(jié)點有一個子節(jié)點
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;
}

③、刪除有兩個子節(jié)點的節(jié)點

當(dāng)刪除的節(jié)點存在兩個子節(jié)點,那么刪除之后,兩個子節(jié)點的位置我們就沒辦法處理了。既然處理不了,我們就想到一種辦法,用另一個節(jié)點來代替被刪除的節(jié)點,那么用哪一個節(jié)點來代替呢?

我們知道二叉搜索樹中的節(jié)點是按照關(guān)鍵字來進行排列的,某個節(jié)點的關(guān)鍵字次高節(jié)點是它的中序遍歷后繼節(jié)點。用后繼節(jié)點來代替刪除的節(jié)點,顯然該二叉搜索樹還是有序的。(這里用后繼節(jié)點代替,如果該后繼節(jié)點自己也有子節(jié)點,我們后面討論。)  

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

后繼節(jié)點也就是:比刪除節(jié)點大的最小節(jié)點。

算法:程序找到刪除節(jié)點的右節(jié)點,(注意這里前提是刪除節(jié)點存在左右兩個子節(jié)點,如果不存在則是刪除情況的前面兩種),然后轉(zhuǎn)到該右節(jié)點的左子節(jié)點,依次順著左子節(jié)點找下去,最后一個左子節(jié)點即是后繼節(jié)點;如果該右節(jié)點沒有左子節(jié)點,那么該右節(jié)點便是后繼節(jié)點。

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

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

這種情況簡單,只需要將后繼節(jié)點表示的子樹移到被刪除節(jié)點的位置即可!

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

④、刪除有必要嗎?

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

8、二叉樹的效率

從前面的大部分對樹的操作來看,都需要從根節(jié)點到下一層一層的查找。

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

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

在有1000000 個數(shù)據(jù)項的無序數(shù)組和鏈表中,查找數(shù)據(jù)項平均會比較500000 次,但是在有1000000個節(jié)點的二叉樹中,只需要20次或更少的比較即可。

有序數(shù)組可以很快的找到數(shù)據(jù)項,但是插入數(shù)據(jù)項的平均需要移動 500000 次數(shù)據(jù)項,在 1000000 個節(jié)點的二叉樹中插入數(shù)據(jù)項需要20次或更少比較,在加上很短的時間來連接數(shù)據(jù)項。

同樣,從 1000000 個數(shù)據(jù)項的數(shù)組中刪除一個數(shù)據(jù)項平均需要移動 500000 個數(shù)據(jù)項,而在 1000000 個節(jié)點的二叉樹中刪除節(jié)點只需要20次或更少的次數(shù)來找到他,然后在花一點時間來找到它的后繼節(jié)點,一點時間來斷開節(jié)點以及連接后繼節(jié)點。

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

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

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

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

樹中的每個位置,無論是否存在節(jié)點,都對應(yīng)于數(shù)組中的一個位置,樹中沒有節(jié)點的在數(shù)組中用0或者null表示。

假設(shè)節(jié)點的索引值為index,那么節(jié)點的左子節(jié)點是 2*index+1,節(jié)點的右子節(jié)點是 2*index+2,它的父節(jié)點是 (index-1)/2。

在大多數(shù)情況下,使用數(shù)組表示樹效率是很低的,不滿的節(jié)點和刪除掉的節(jié)點都會在數(shù)組中留下洞,浪費存儲空間。更壞的是,刪除節(jié)點如果要移動子樹的話,子樹中的每個節(jié)點都要移到數(shù)組中新的位置,這是很費時的。

不過如果不允許刪除操作,數(shù)組表示可能會很有用,尤其是因為某種原因要動態(tài)的為每個字節(jié)分配空間非常耗時。

10、完整的BinaryTree代碼

Node.java

package com.ys.tree;
 
public class Node {
    int data;   //節(jié)點數(shù)據(jù)
    Node leftChild; //左子節(jié)點的引用
    Node rightChild; //右子節(jié)點的引用
    boolean isDelete;//表示節(jié)點是否被刪除
     
    public Node(int data){
        this.data = data;
    }
    //打印節(jié)點內(nèi)容
    public void display(){
        System.out.println(data);
    }
 
}

Tree.java

package com.ys.tree;
 
public interface Tree {
    //查找節(jié)點
    public Node find(int key);
    //插入新節(jié)點
    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é)點
    public boolean delete(int key);
     
    //Other Method......
}

BinaryTree.java

package com.ys.tree;
 
public class BinaryTree implements Tree {
    //表示根節(jié)點
    private Node root;
 
    //查找節(jié)點
    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;//遍歷完整個樹沒找到,返回null
    }
 
    //插入節(jié)點
    public boolean insert(int data) {
        Node newNode = new Node(data);
        if(root == null){//當(dāng)前樹為空樹,沒有任何節(jié)點
            root = newNode;
            return true;
        }else{
            Node current = root;
            Node parentNode = null;
            while(current != null){
                parentNode = current;
                if(current.data > data){//當(dāng)前值比插入值大,搜索左子節(jié)點
                    current = current.leftChild;
                    if(current == null){//左子節(jié)點為空,直接將新值插入到該節(jié)點
                        parentNode.leftChild = newNode;
                        return true;
                    }
                }else{
                    current = current.rightChild;
                    if(current == null){//右子節(jié)點為空,直接將新值插入到該節(jié)點
                        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é)點沒有子節(jié)點
        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é)點有一個子節(jié)點,右子節(jié)點
        }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é)點有一個子節(jié)點,左子節(jié)點
        }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é)點存在兩個子節(jié)點
            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é)點不是刪除節(jié)點的右子節(jié)點,將后繼節(jié)點替換刪除節(jié)點
        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);//刪除沒有子節(jié)點的節(jié)點
        bt.delete(30);//刪除有一個子節(jié)點的節(jié)點
        bt.delete(80);//刪除有兩個子節(jié)點的節(jié)點
        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)編碼

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

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

答案是不可以的,因為在編碼序列中是沒有空格或其他特殊字符存在的,全都是有0和1構(gòu)成的序列,比如E用01來表示,X用01011000表示,那么在解碼的時候就弄不清楚01是表示E還是表示X的起始部分,所以在編碼的時候就定下了一個規(guī)則:每個代碼都不能是其它代碼的前綴。

①、哈夫曼編碼 

二叉樹中有一種特別的樹——哈夫曼樹(最優(yōu)二叉樹),其通過某種規(guī)則(權(quán)值)來構(gòu)造出一哈夫曼二叉樹,在這個二叉樹中,只有葉子節(jié)點才是有效的數(shù)據(jù)節(jié)點(很重要),其他的非葉子節(jié)點是為了構(gòu)造出哈夫曼而引入的!
哈夫曼編碼是一個通過哈夫曼樹進行的一種編碼,一般情況下,以字符:‘0’與‘1’表示。編碼的實現(xiàn)過程很簡單,只要實現(xiàn)哈夫曼樹,通過遍歷哈夫曼樹,規(guī)定向左子樹遍歷一個節(jié)點編碼為“0”,向右遍歷一個節(jié)點編碼為“1”,結(jié)束條件就是遍歷到葉子節(jié)點!因為上面說過:哈夫曼樹葉子節(jié)點才是有效數(shù)據(jù)節(jié)點!

我們用01表示S,用00表示空格后,就不能用01和11表示某個字符了,因為它們是其它字符的前綴。在看三位的組合,分別有000,001,010,100,101,110和111,A是010,I是110,為什么沒有其它三位的組合了呢?因為已知是不能用01和11開始的組合了,那么就減少了四種選擇,同時011用于U和換行符的開始,111用于E和Y的開始,這樣就只剩下2個三位的組合了,同理可以理解為什么只有三個四位的代碼可用。

所以對于消息:SUSIE SAYS IT IS EASY

哈夫曼編碼為:100111110110111100100101110100011001100011010001111010101110

②、哈夫曼解碼

如果收到上面的一串哈夫曼編碼,怎么解碼呢?消息中出現(xiàn)的字符在哈夫曼樹中是葉節(jié)點,也就是沒有子節(jié)點,如下圖:它們在消息中出現(xiàn)的頻率越高,在樹中的位置就越高,每個圓圈外面的數(shù)字就是頻率,非葉節(jié)點外面的數(shù)字是它子節(jié)點數(shù)字的和。

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

12、總結(jié)

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

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

相關(guān)文章

  • Springboot使用redis實現(xiàn)接口Api限流的實例

    Springboot使用redis實現(xiàn)接口Api限流的實例

    本文介紹的內(nèi)容如題,就是利用redis實現(xiàn)接口的限流(某時間范圍內(nèi),最大的訪問次數(shù)),具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2021-07-07
  • SpringMVC @RequestBody Date類型的Json轉(zhuǎn)換方式

    SpringMVC @RequestBody Date類型的Json轉(zhuǎn)換方式

    這篇文章主要介紹了SpringMVC @RequestBody Date類型的Json轉(zhuǎn)換方式,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教
    2021-10-10
  • Mybatis延遲加載原理和延遲加載配置詳解

    Mybatis延遲加載原理和延遲加載配置詳解

    這篇文章主要介紹了Mybatis延遲加載原理和延遲加載配置詳解,MyBatis中的延遲加載,也稱為懶加載,是指在進行表的關(guān)聯(lián)查詢時,按照設(shè)置延遲規(guī)則推遲對關(guān)聯(lián)對象的select查詢,需要的朋友可以參考下
    2023-10-10
  • Java IO復(fù)用_動力節(jié)點Java學(xué)院整理

    Java IO復(fù)用_動力節(jié)點Java學(xué)院整理

    這篇文章主要介紹了Java IO復(fù)用的相關(guān)知識,非常不錯,具有參考借鑒價值,需要的的朋友參考下吧
    2017-05-05
  • 最小樹形圖模板朱劉算法分享

    最小樹形圖模板朱劉算法分享

    這篇文章主要介紹了最小樹形圖模板朱劉算法,有需要的朋友可以參考一下
    2014-01-01
  • SpringBoot整合dataworks的實現(xiàn)過程

    SpringBoot整合dataworks的實現(xiàn)過程

    這篇文章主要介紹了SpringBoot整合dataworks的實現(xiàn)過程,實現(xiàn)主要是編寫工具類,如果需要則可以配置成SpringBean,注入容器即可使用,需要的朋友可以參考下
    2022-08-08
  • Java 數(shù)據(jù)結(jié)構(gòu)與算法系列精講之紅黑樹

    Java 數(shù)據(jù)結(jié)構(gòu)與算法系列精講之紅黑樹

    紅黑樹的應(yīng)用比較廣泛,主要是用它來存儲有序的數(shù)據(jù),它的時間復(fù)雜度是O(lgn),效率非常之高。例如,Java集合中的TreeSet和TreeMap,C++ STL中的set、map,以及Linux虛擬內(nèi)存的管理,都是通過紅黑樹去實現(xiàn)的
    2022-02-02
  • SpringBoot擴展SpringMVC原理并實現(xiàn)全面接管

    SpringBoot擴展SpringMVC原理并實現(xiàn)全面接管

    這篇文章主要介紹了SpringBoot擴展SpringMVC原理并實現(xiàn)全面接管,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下
    2020-11-11
  • 微服務(wù)?Spring?Boot?整合?Redis?BitMap?實現(xiàn)?簽到與統(tǒng)計功能

    微服務(wù)?Spring?Boot?整合?Redis?BitMap?實現(xiàn)?簽到與統(tǒng)計功能

    這篇文章主要介紹了微服務(wù)?Spring?Boot?整合?Redis?BitMap?實現(xiàn)?簽到與統(tǒng)計功能,文章簡單介紹了Redis BitMap 基本用法結(jié)合實例代碼給大家介紹的非常詳細(xì),需要的朋友可以參考下
    2023-01-01
  • Java基礎(chǔ)-Java編程語言發(fā)展史

    Java基礎(chǔ)-Java編程語言發(fā)展史

    這篇文章主要介紹了Java基礎(chǔ)-Java編程語言發(fā)展簡史,Java源自Sun公司的一個叫Green的項目,其原先的目的是為家用電子消費產(chǎn)品開發(fā)一個分布式代碼系統(tǒng),這樣就可以將通信和控制信息發(fā)給電冰箱、電視機、烤面包機等家用電器,對它們進行控制和信息交流,需要的朋友可以參考一下
    2022-01-01

最新評論