帶你了解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限流的實例
本文介紹的內(nèi)容如題,就是利用redis實現(xiàn)接口的限流(某時間范圍內(nèi),最大的訪問次數(shù)),具有一定的參考價值,感興趣的小伙伴們可以參考一下2021-07-07SpringMVC @RequestBody Date類型的Json轉(zhuǎn)換方式
這篇文章主要介紹了SpringMVC @RequestBody Date類型的Json轉(zhuǎn)換方式,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教2021-10-10Java IO復(fù)用_動力節(jié)點Java學(xué)院整理
這篇文章主要介紹了Java IO復(fù)用的相關(guān)知識,非常不錯,具有參考借鑒價值,需要的的朋友參考下吧2017-05-05SpringBoot整合dataworks的實現(xiàn)過程
這篇文章主要介紹了SpringBoot整合dataworks的實現(xiàn)過程,實現(xiàn)主要是編寫工具類,如果需要則可以配置成SpringBean,注入容器即可使用,需要的朋友可以參考下2022-08-08Java 數(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-02SpringBoot擴展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)計功能,文章簡單介紹了Redis BitMap 基本用法結(jié)合實例代碼給大家介紹的非常詳細(xì),需要的朋友可以參考下2023-01-01