帶你了解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-07
SpringMVC @RequestBody Date類型的Json轉(zhuǎn)換方式
這篇文章主要介紹了SpringMVC @RequestBody Date類型的Json轉(zhuǎn)換方式，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-10-10
這篇文章主要介紹了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ù)用的相關(guān)知識，非常不錯，具有參考借鑒價值，需要的的朋友參考下吧2017-05-05
這篇文章主要介紹了最小樹形圖模板朱劉算法，有需要的朋友可以參考一下2014-01-01
SpringBoot整合dataworks的實現(xiàn)過程
這篇文章主要介紹了SpringBoot整合dataworks的實現(xiàn)過程,實現(xiàn)主要是編寫工具類，如果需要則可以配置成SpringBean，注入容器即可使用，需要的朋友可以參考下2022-08-08
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)全面接管,文中通過示例代碼介紹的非常詳細(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
這篇文章主要介紹了Java基礎(chǔ)-Java編程語言發(fā)展簡史,Java源自Sun公司的一個叫Green的項目,其原先的目的是為家用電子消費產(chǎn)品開發(fā)一個分布式代碼系統(tǒng),這樣就可以將通信和控制信息發(fā)給電冰箱、電視機、烤面包機等家用電器,對它們進行控制和信息交流,需要的朋友可以參考一下2022-01-01