全網(wǎng)最精細詳解二叉樹,2萬字帶你進入算法領(lǐng)域
更新時間：2021年08月20日 11:03:02 作者：哪 吒
大家好,我是哪吒,一個熱愛編碼的Java工程師,本著"欲速則不達,欲達則欲速"的學習態(tài)度,在程序猿這條不歸路上不斷成長,所謂成長,不過是用時間慢慢擦亮你的眼睛,少時看重的,年長后卻視若鴻毛,少時看輕的,年長后卻視若泰山,成長之路,亦是漸漸放下執(zhí)念,內(nèi)心歸于平靜的旅程
也許，我們永遠都不會知道自己能走到何方，遇見何人，最后會變成什么樣的人，但一定要記住，能讓自己登高的，永遠不是別人的肩膀，而是挑燈夜戰(zhàn)的自己，人生的道路剛剛啟程，當你累了倦了也不要迷茫，回頭看一看，你早已不再是那個年少輕狂的少年。
一、前言
數(shù)組的搜索比較方便，可以直接用下標，但刪除和插入就比較麻煩；
鏈表與之相反，刪除和插入元素很快，但查找比較慢；
此時，二叉樹應(yīng)運而生，二叉樹既有鏈表的好處，也有數(shù)組的好處，在處理大批量的動態(tài)數(shù)據(jù)時比較好用，是一種折中的選擇。
文件系統(tǒng)和數(shù)據(jù)庫系統(tǒng)一般都是采用樹（特別是B樹）的數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)，主要為排序和檢索的效率。
二叉樹是一種最基本最典型的排序樹，用于教學和研究樹的特性，本身很少在實際中進行應(yīng)用，因為缺點太明顯，就像冒泡排序一樣，因為效率問題并不實用，但也是我們必須會的。
二、二叉樹缺點
1、順序存儲可能會浪費空間（在非完全二叉樹的時候），但是讀取某個指定的結(jié)點的時候效率比較高O(0)；
2、鏈式存儲相對于二叉樹，浪費空間較少，但是讀取某個結(jié)點的時候效率偏低O(nlogn)。
滿二叉樹：
在一顆二叉樹中，如果所有分支結(jié)點都有左子結(jié)點和右子結(jié)點，并且葉結(jié)點都集中在二叉樹的最底層，這樣的二叉樹稱為滿二叉樹。
完全二叉樹：
若二叉樹中最多只有最下面兩層的結(jié)點，而且相差只有1級，并且最下面一層的葉結(jié)點都依次排列在該層的最左邊位置，則這樣的二叉樹稱為完全二叉樹。
三、遍歷與結(jié)點刪除
二叉樹是一種非常重要的數(shù)據(jù)結(jié)構(gòu)，非常多的數(shù)據(jù)結(jié)構(gòu)都是基于二叉樹的基礎(chǔ)演變而來的。對于二叉樹有深度遍歷和廣度遍歷，深度遍歷有前序、中序以及后序三種遍歷方法，廣度遍歷即我們尋常所說的層次遍歷。由于樹的定義本身就是遞歸定義，因此采用遞歸的方法實現(xiàn)樹的三種遍歷。
對于一段代碼來說，可讀性有時候要比代碼本身的效率要重要的多。
1、四種基本的遍歷思想
- 前序遍歷：根結(jié)點 -->左子樹-->右子樹；
- 中序遍歷：左子樹 -->根結(jié)點-->右子樹；
- 后續(xù)遍歷：左子樹 -->右子樹-->根結(jié)點；
- 層次遍歷：僅僅需按成次遍歷即可；
2、自定義二叉樹
3、代碼實現(xiàn)
（1）girlNode
package com.guor.tree;
public class GirlNode {
private int no;
private String name;
private GirlNode left; //默認null
private GirlNode right; //默認null
//1、如果leftType == 0表示指向的是左子樹，如果 leftType == 1則表示指向的是前驅(qū)結(jié)點
//2、如果rightType == 0表示指向的是右子樹，如果 rightType == 1則表示指向的是后繼結(jié)點
private int leftType;
private int rightType;
public int getLeftType() {
return leftType;
}
public void setLeftType(int leftType) {
this.leftType = leftType;
}
public int getRightType() {
return rightType;
}
public void setRightType(int rightType) {
this.rightType = rightType;
}
public GirlNode(int no, String name) {
this.no = no;
this.name = name;
}
public int getNo() {
return no;
}
public void setNo(int no) {
this.no = no;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public GirlNode getLeft() {
return left;
}
public void setLeft(GirlNode left) {
this.left = left;
}
public GirlNode getRight() {
return right;
}
public void setRight(GirlNode right) {
this.right = right;
}
@Override
public String toString() {
return "GirlNode [no=" + no + ", name=" + name + "]";
}
//前序遍歷
public void preOrder() {
System.out.println(this);//先輸出父節(jié)點
//遞歸向左子樹前序遍歷
if(this.left != null) {
this.left.preOrder();
}
//遞歸向右子樹前序遍歷
if(this.right != null) {
this.right.preOrder();
}
}
//中序遍歷
public void midOrder() {
//遞歸向左子樹中序遍歷
if(this.left != null) {
this.left.midOrder();
}
System.out.println(this);//輸出父節(jié)點
//遞歸向右子樹前序遍歷
if(this.right != null) {
this.right.midOrder();
}
}
//后序遍歷
public void postOrder() {
//遞歸向左子樹后序遍歷
if(this.left != null) {
this.left.postOrder();
}
//遞歸向右子樹前序遍歷
if(this.right != null) {
this.right.postOrder();
}
System.out.println(this);//輸出父節(jié)點
}
//遞歸刪除結(jié)點
//1.如果刪除的節(jié)點是葉子節(jié)點，則刪除該節(jié)點
//2.如果刪除的節(jié)點是非葉子節(jié)點，則刪除該子樹
public void delNode(int no) {
//思路
/*
* 1. 因為我們的二叉樹是單向的，所以我們是判斷當前結(jié)點的子結(jié)點是否需要刪除結(jié)點，而不能去判斷當前這個結(jié)點是不是需要刪除結(jié)點.
2. 如果當前結(jié)點的左子結(jié)點不為空，并且左子結(jié)點 就是要刪除結(jié)點，就將this.left = null; 并且就返回(結(jié)束遞歸刪除)
3. 如果當前結(jié)點的右子結(jié)點不為空，并且右子結(jié)點 就是要刪除結(jié)點，就將this.right= null ;并且就返回(結(jié)束遞歸刪除)
4. 如果第2和第3步?jīng)]有刪除結(jié)點，那么我們就需要向左子樹進行遞歸刪除
5. 如果第4步也沒有刪除結(jié)點，則應(yīng)當向右子樹進行遞歸刪除.
*/
//2. 如果當前結(jié)點的左子結(jié)點不為空，并且左子結(jié)點 就是要刪除結(jié)點，就將this.left = null; 并且就返回(結(jié)束遞歸刪除)
if(this.left != null && this.left.no == no) {
this.left = null;
return;
}
//3.如果當前結(jié)點的右子結(jié)點不為空，并且右子結(jié)點 就是要刪除結(jié)點，就將this.right= null ;并且就返回(結(jié)束遞歸刪除)
if(this.right != null && this.right.no == no) {
this.right = null;
return;
}
//4.我們就需要向左子樹進行遞歸刪除
if(this.left != null) {
this.left.delNode(no);
}
//5.則應(yīng)當向右子樹進行遞歸刪除
if(this.right != null) {
this.right.delNode(no);
}
}
}
（2）二叉樹測試
package com.guor.tree;
public class BinaryTreeTest {
public static void main(String[] args) {
//創(chuàng)建一個二叉樹
BinaryTree binaryTree = new BinaryTree();
//創(chuàng)建結(jié)點
HeroNode root = new HeroNode(1, "比比東");
HeroNode node2 = new HeroNode(2, "云韻");
HeroNode node3 = new HeroNode(3, "美杜莎");
HeroNode node4 = new HeroNode(4, "納蘭嫣然");
HeroNode node5 = new HeroNode(5, "雅妃");
root.setLeft(node2);
root.setRight(node3);
node3.setLeft(node4);
node3.setRight(node5);
binaryTree.setRoot(root);
System.out.println("前序遍歷");
binaryTree.preOrder();
System.out.println("中序遍歷");
binaryTree.midOrder();
System.out.println("后序遍歷");
binaryTree.postOrder();
binaryTree.delNode(3);
System.out.println("刪除結(jié)點3，前序遍歷");
binaryTree.preOrder();
}
}
//定義BinaryTree 二叉樹
class BinaryTree {
private HeroNode root;
public HeroNode getRoot() {
return root;
}
public void setRoot(HeroNode root) {
this.root = root;
}
//前序遍歷
public void preOrder() {
if(this.root != null) {
this.root.preOrder();
}else {
System.out.println("二叉樹為空，不能遍歷");
}
}
//中序遍歷
public void midOrder() {
if(this.root != null) {
this.root.midOrder();
}else {
System.out.println("二叉樹為空，無法遍歷");
}
}
//后序遍歷
public void postOrder() {
if(this.root != null) {
this.root.postOrder();
}else {
System.out.println("二叉樹為空，無法遍歷");
}
}
//刪除結(jié)點
public void delNode(int no) {
if(root != null) {
//如果只有一個root結(jié)點, 這里立即判斷root是不是就是要刪除結(jié)點
if(root.getNo() == no) {
root = null;
} else {
//遞歸刪除
root.delNode(no);
}
}else{
System.out.println("空樹，不能刪除~");
}
}
}
（3）控制臺輸出
四、先看一個問題
將數(shù)列{1,3,6,8,10,14}構(gòu)建成一顆二叉樹。
問題分析：
- 當我們對上面的二叉樹進行中序遍歷時，數(shù)列為{8,3,10,1,6,14}。
- 但是6,8,10,14這幾個節(jié)點的左右指針，并沒有完全的利用上。
- 如果我們希望充分的利用各個節(jié)點的左右指針，讓各個節(jié)點可以指向自己的前后節(jié)點，要怎么辦？
- 解決方案 --> 線索化二叉樹
五、線索化二叉樹
1、n個節(jié)點的二叉樹鏈表總含有n+1（公式2n-(n-1)=n+1）個空指針域。利用二叉樹表中的空指針域，存放指向該節(jié)點在某種遍歷次序下的前驅(qū)和后繼節(jié)點的指針（這種附加的指針稱為“線索”）
2、這種加上了線索的二叉樹稱為線索鏈表，相應(yīng)的二叉樹稱為線索二叉樹（Threaded BinaryTree）。根據(jù)線索性質(zhì)的不同，線索二叉樹可分為前序線索二叉樹、中序線索二叉樹和后序線索二叉樹三種。
3、一個節(jié)點的前一個節(jié)點，稱為前驅(qū)節(jié)點
4、一個節(jié)點的后一個節(jié)點，稱為后繼節(jié)點
說明：當線索化二叉樹后，Node節(jié)點的屬性left和right，有如下情況：
- left指向的是左子樹，也可能指向的前驅(qū)節(jié)點，比如①節(jié)點left指向的左子樹，而⑩節(jié)點的left指向的就是前驅(qū)節(jié)點。
- right指向的是右子樹，也可能是指向后繼節(jié)點，比如①節(jié)點right指向的是右子樹，而⑩節(jié)點的right指向的是后繼節(jié)點。
六、線索化二叉樹代碼實例
1、線索化二叉樹
package com.guor.tree;
//定義ThreadBinaryTree，實現(xiàn)了線索化功能的二叉樹
public class ThreadedBinaryTree {
private HeroNode root;
//為了實現(xiàn)線索化，需要創(chuàng)建指向當前結(jié)點的前驅(qū)結(jié)點的指針
//在遞歸進行線索化時，pre總是保留前一個結(jié)點
private HeroNode pre = null;
public HeroNode getRoot() {
return root;
}
public void setRoot(HeroNode root) {
this.root = root;
}
//重載threadedNodes方法
public void threadedNodes(){
this.threadedNodes(root);
}
/**
* 編寫對二叉樹進行中序線索化的方法
* @param node 當前需要線索化的結(jié)點
*/
public void threadedNodes(HeroNode node){
//如果node==null，不能線索化
if(node == null){
return;
}
//1、先線索化左子樹
threadedNodes(node.getLeft());
//2、線索化當前結(jié)點
//處理當前結(jié)點的前驅(qū)結(jié)點
//以8為例來理解
//8結(jié)點的.left = null，8結(jié)點的.leftType = 1
if(node.getLeft() == null){
//讓當前結(jié)點的左指針指向前驅(qū)結(jié)點
node.setLeft(pre);
//修改當前結(jié)點的左指針的類型，指向前驅(qū)結(jié)點
node.setLeftType(1);
}
//處理后繼結(jié)點
if(pre != null && pre.getRight() == null){
//讓當前結(jié)點的右指針指向當前結(jié)點
pre.setRight(node);
//修改當前結(jié)點的右指針的類型=
pre.setRightType(1);
}
//每處理一個結(jié)點后，讓當前結(jié)點是下一個結(jié)點的前驅(qū)結(jié)點
pre = node;
//3、線索化右子樹
threadedNodes(node.getRight());
}
//前序遍歷
public void preOrder() {
if(this.root != null) {
this.root.preOrder();
}else {
System.out.println("二叉樹為空，不能遍歷");
}
}
//中序遍歷
public void midOrder() {
if(this.root != null) {
this.root.midOrder();
}else {
System.out.println("二叉樹為空，無法遍歷");
}
}
//后序遍歷
public void postOrder() {
if(this.root != null) {
this.root.postOrder();
}else {
System.out.println("二叉樹為空，無法遍歷");
}
}
//刪除結(jié)點
public void delNode(int no) {
if(root != null) {
//如果只有一個root結(jié)點, 這里立即判斷root是不是就是要刪除結(jié)點
if(root.getNo() == no) {
root = null;
} else {
//遞歸刪除
root.delNode(no);
}
}else{
System.out.println("空樹，不能刪除~");
}
}
}
2、測試
package com.guor.tree;
public class ThreadedBinaryTreeTest {
public static void main(String[] args) {
//測試中序線索二叉樹的功能
HeroNode root = new HeroNode(1,"比比東");
HeroNode node2 = new HeroNode(3,"云韻");
HeroNode node3 = new HeroNode(6,"納蘭嫣然");
HeroNode node4 = new HeroNode(8,"雅妃");
HeroNode node5 = new HeroNode(10,"千仞雪");
HeroNode node6 = new HeroNode(14,"美杜莎");
//二叉樹，后面我們要遞歸創(chuàng)建，現(xiàn)在簡單處理使用手動創(chuàng)建
root.setLeft(node2);
root.setRight(node3);
node2.setLeft(node4);
node2.setRight(node5);
node3.setLeft(node6);
//測試中序線索化
ThreadedBinaryTree threadedBinaryTree = new ThreadedBinaryTree();
threadedBinaryTree.setRoot(root);
threadedBinaryTree.threadedNodes();
//以10號節(jié)點測試
HeroNode leftNode = node5.getLeft();
System.out.println("10號結(jié)點的前驅(qū)結(jié)點是："+leftNode);//應(yīng)該是3號
HeroNode rightNode = node5.getRight();
System.out.println("10號結(jié)點的后繼結(jié)點是："+rightNode);//應(yīng)該是1號
}
}
3、控制臺輸出
七、遍歷線索化二叉樹
說明：對前面的中序線索化的二叉樹，進行遍歷
分析：因為線索化后，各個結(jié)點指向有變化，因此原來的遍歷方式不能使用，這時需要使用心得方式遍歷線索化二叉樹，各個結(jié)點可以通過線型方式遍歷，因此無需使用遞歸方式，這樣也提高了遍歷的效率。遍歷的次序應(yīng)當和中序遍歷保持一致。
1、代碼實例
/**
* 遍歷線索化二叉樹的方法
*/
public void threadedList(){
//定義一個變量，存儲當前遍歷的結(jié)點，從root開始
HeroNode node = root;
while (node != null){
//循環(huán)找到leftType == 1的結(jié)點，第一個找到就是8結(jié)點
//后面隨著遍歷而變化，因為當leftType==1時，說明該結(jié)點是按照線索化處理后的有效結(jié)點
while(node.getLeftType() == 0){
node = node.getLeft();
}
//打印當前結(jié)點
System.out.println(node);
//如果當前結(jié)點的右指針指向的是后繼結(jié)點，就一直輸出
while(node.getRightType() == 1){
//獲取當前結(jié)點的后繼結(jié)點
node = node.getRight();
System.out.println(node);
}
//替換這個遍歷的結(jié)點
node = node.getRight();
}
}
2、控制臺輸出
八、大頂堆和小頂堆圖解說明
1、堆排序基本介紹
- 堆排序是利用堆這種數(shù)據(jù)結(jié)構(gòu)而設(shè)計的一種排序算法，堆排序是一種選擇排序，它的最壞，最好，平均時間復雜度均為線性對數(shù)階，它也是不穩(wěn)定排序。
- 堆是具有以下特性的完全二叉樹：每個結(jié)點的值都大于或等于其左右子結(jié)點的值，稱為大頂堆，注意：沒有要求結(jié)點的左子結(jié)點值和右子結(jié)點值的大小關(guān)系。
- 每個結(jié)點的值都小于或等于其左右子結(jié)點的值，稱為小頂堆。
2、大頂堆舉例說明
我們對堆中的結(jié)點按層進行編號，映射到數(shù)組中就是下面這一個樣子
大頂堆特點：
arr[i]>=ar[2*i+1]&&arr[i]>=arr[2*i+2]//i對應(yīng)第幾個結(jié)點，i從0開始編號
3、小頂堆距離說明
小頂堆特點：
arr[i]<=arr[2*i+1]&&arr[i]<=arr[2*i+2]//i對應(yīng)第幾個結(jié)點，i從0開始編號
4、一般升序采用大頂堆，降序采用小頂堆
堆排序基本思想
- 將待排序序列構(gòu)成一個大頂堆
- 此時，整個序列的最大值就是堆頂?shù)母?jié)點
- 將其與末尾元素進行交換，此時末尾就為最大值
- 然后將剩余n-1個元素重新構(gòu)造成一個堆，這樣會得到n個元素的次小值。如此反復執(zhí)行，便能得到一個有序序列了。
九、堆排序思路和步驟解析
1、將無序二叉樹調(diào)整為大頂堆
（1）原始的數(shù)組[4,6,8,5,9]
（2）此時從最后一個非葉子結(jié)點開始（第一個非葉子結(jié)點arr.length/2-1=5/2-1=1，也就是6結(jié)點），從左至右，從上至下進行調(diào)整。
（3）再找到第二個非葉子結(jié)點，由于[4，9，8]中9最大，所以4和9交換。
4、此時，交換之后導致[4，5，6]結(jié)構(gòu)混亂了，繼續(xù)調(diào)整，交換4和6。
此時，我們就講一個無序結(jié)構(gòu)的二叉樹調(diào)整為了一個大頂堆。
2、將堆頂元素與末尾元素進行交換
使末尾元素最大。然后繼續(xù)調(diào)整堆，再講堆頂元素與末尾元素交換，得到第二大元素。如此反復進行交換、重建、交換。
3、重新調(diào)整結(jié)構(gòu)
使其繼續(xù)滿足堆定義，然后繼續(xù)交換堆頂元素與當前末尾元素，反復執(zhí)行調(diào)整+交換步驟，直到整個序列有序。
再將堆頂?shù)?與末尾元素5交換，得到第二大元素8
然后繼續(xù)進行調(diào)整，交換，最后變成：
簡單總結(jié)一下堆排序的基本思路：
- 將無序序列構(gòu)建成一個堆，根據(jù)升序降序需求選擇大頂堆或小頂堆；
- 將堆頂元素與末尾元素交換，將最大元素交換至數(shù)組末端；
- 重新調(diào)整結(jié)構(gòu)，使其滿足堆定義，然后繼續(xù)交換堆頂元素與當前末尾元素，反復執(zhí)行調(diào)整+交換步驟，直到整個序列有序。
十、堆排序代碼實例
1、堆排序代碼
package com.guor.tree;
import java.util.Arrays;
public class HeapSort {
public static void main(String[] args) {
//要求將數(shù)組進行升序排序
int arr[] = {4,6,8,5,9};
heapSort(arr);
}
public static void heapSort(int arr[]){
int temp = 0;
System.out.println("堆排序。");
//分步完成
//adjustHeap(arr,1,arr.length);
//System.out.println("第一次調(diào)整："+ Arrays.toString(arr));//{4,9,8,5,6}
//adjustHeap(arr,0,arr.length);
//System.out.println("第二次調(diào)整："+ Arrays.toString(arr));//{9,6,8,5,4}
//完成最終代碼
//將無序序列構(gòu)建成一個堆，根據(jù)升序降序需求選擇大頂堆或小頂堆
//arr.length/2-1為葉子結(jié)點個數(shù)
for(int i = arr.length/2-1;i>=0;i--){
adjustHeap(arr, i, arr.length);
}
System.out.println("調(diào)整為大頂堆："+ Arrays.toString(arr));//大頂堆{9,6,8,5,4}
//第二步：將堆頂元素與末尾元素進行交換，使末尾元素最大。然后繼續(xù)調(diào)整堆，再講堆頂元素與末尾元素交換，得到第二大元素。如此反復進行交換、重建、交換。
//第三步：重新調(diào)整結(jié)構(gòu)，使其繼續(xù)滿足堆定義，然后繼續(xù)交換堆頂元素與當前末尾元素，反復執(zhí)行調(diào)整+交換步驟，直到整個序列有序。
for(int j = arr.length - 1;j > 0; j--){
//交換
temp=arr[j];
arr[j]= arr[0];
arr[0] = temp;
adjustHeap(arr, 0, j);
}
System.out.println("最終有序序列："+ Arrays.toString(arr));//大頂堆{4,5,6,8,9}
}
/**
* 功能：完成將以i為葉子節(jié)點的樹調(diào)整為大頂堆
* @demo int arr[] = {4,6,8,5,9};i = 1 --> adjustHeap --> {4,9,8,5,6}
* 如果再調(diào)用adjustHeap，傳入i=0 --> 大頂堆{9,6,8,5,4}
* @param arr 待調(diào)整的數(shù)組
* @param i 表示非葉子結(jié)點在數(shù)組中的索引
* @param length 表示對多少個元素進行繼續(xù)調(diào)整，length逐漸減少
*/
public static void adjustHeap(int arr[], int i, int length){
//取出當前元素的值，保存為臨時變量
int temp = arr[i];
//1、k = i * 2 + 1 ,k是i結(jié)點的左子結(jié)點
for(int k = i * 2 + 1; k < length; k = k * 2 + 1){
//左子結(jié)點的值小于右子結(jié)點的值
if(k+1<length && arr[k] < arr[k+1]){
k++;//k指向右子結(jié)點
}
//如果子結(jié)點大于父節(jié)點
if(arr[k] > temp){
arr[i] = arr[k];//將較大的值賦給當前結(jié)點
i = k;//i指向k,繼續(xù)循環(huán)比較
}else{
break;
}
}
//當for循環(huán)結(jié)束后，我們已經(jīng)將以i為父節(jié)點的樹的最大值，放在了最頂，完成局部大頂堆
arr[i] = temp;//將temp值放到調(diào)整后的位置
}
}
2、堆排序控制臺輸出
3、堆排序性能測試
因為堆排序的時間復雜度是線性對數(shù)階，所以堆排序是非?？斓?，性能相當強悍，拿1000萬條數(shù)據(jù)進行排序測試一下，let‘s go！
public static void main(String[] args) {
//模擬測試1000萬條數(shù)據(jù)
int[] arr = new int[10000000];
for(int i = 0; i< 10000000; i++){
arr[i] = (int)(Math.random() * 10000000);
}
long start = new Date().getTime();
heapSort(arr);
long end = new Date().getTime();
System.out.println("1000萬條數(shù)據(jù)，堆排序耗時："+(end-start)+"ms");
}
4、性能測試控制臺輸出
十一、赫夫曼樹
1、基本介紹
（1）給定n個權(quán)值作為n個葉子結(jié)點，構(gòu)造一顆二叉樹，若該樹的帶權(quán)路徑長度wpl達到最小，稱這樣的二叉樹為最優(yōu)二叉樹，也稱為赫夫曼樹。
（2）赫夫曼樹是帶權(quán)路徑長度最短的樹，權(quán)重較大的結(jié)點離根較近。
2、赫夫曼樹幾個重要概念和舉例說明
（1）路徑和路徑長度
在一棵樹中，從一個結(jié)點往下可以達到的孩子或?qū)O子結(jié)點之間的通路，稱為路徑。通路中分支的數(shù)目稱為路徑長度。若規(guī)定根結(jié)點的層數(shù)為1，則從根結(jié)點到第L層結(jié)點的路徑長度為L-1。
（2）結(jié)點的權(quán)及帶權(quán)路徑長度
若將樹中結(jié)點賦給一個有著某種意義的數(shù)值，則這個數(shù)值稱為該結(jié)點的權(quán)。結(jié)點的帶權(quán)路徑長度為：從根結(jié)點到該結(jié)點之間的路徑長度與該結(jié)點的權(quán)的乘積。
（3）樹的帶權(quán)路徑長度
樹的帶權(quán)路徑長度規(guī)定為所有葉子結(jié)點的帶權(quán)路徑長度之和，為WPL（weighted path length），權(quán)重越大的結(jié)點離根結(jié)點越近的二叉樹才是最優(yōu)二叉樹。
（4）WPL最小的就是赫夫曼樹。
3、赫夫曼樹創(chuàng)建思路
- 從小到大進行排序，將每一個數(shù)據(jù)，每個數(shù)據(jù)都是一個結(jié)點，每個結(jié)點可以看成是一顆最簡單的二叉樹
- 取出根結(jié)點權(quán)重最小的兩顆二叉樹
- 組成一顆新的二叉樹，該新的二叉樹的根結(jié)點的權(quán)值是前面兩顆二叉樹根結(jié)點權(quán)值的和
- 再將這顆新的二叉樹，以根結(jié)點的權(quán)值大小再次排序，不斷重復1-2-3-4的步驟，直到數(shù)列中，所有的數(shù)據(jù)都被處理，就得到一顆赫夫曼樹
4、赫夫曼樹代碼實例
（1）Node
package com.guor.huffmantree;
public class Node implements Comparable<Node>{
int value;//結(jié)點權(quán)值
Node left;//指向左子結(jié)點
Node right;//指向右子結(jié)點
public Node(int value){
this.value = value;
}
@Override
public String toString(){
return "Node [value="+value+"]";
}
@Override
public int compareTo(Node o) {
//表示從小到大排序
return this.value - o.value;
}
//寫一個前序遍歷
public void preOrder(){
System.out.println(this);
if(this.left != null){
this.left.preOrder();
}
if(this.right != null){
this.right.preOrder();
}
}
}
（2）創(chuàng)建赫夫曼樹HuffmanTree
package com.guor.huffmantree;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class HuffmanTree {
public static void main(String[] args) {
int[] arr = {13,7,8,3,29,6,1};
Node root = createHuffmanTree(arr);
//測試
preOrder(root);
}
//編寫一個前序遍歷的方法
public static void preOrder(Node root){
if(root != null){
root.preOrder();
}else {
System.out.println("空樹不能遍歷.");
}
}
//創(chuàng)建赫夫曼樹的方法
public static Node createHuffmanTree(int[] arr){
List<Node> nodeList = new ArrayList<>();
for(int value : arr){
nodeList.add(new Node(value));
}
//處理的過程是一個循環(huán)的過程
while (nodeList.size() > 1){
//從小到大排序
Collections.sort(nodeList);
System.out.println("nodes="+nodeList);
//取出根結(jié)點權(quán)值最小的兩顆二叉樹
//1、取出權(quán)值最小的結(jié)點
Node leftNode = nodeList.get(0);
//2、取出權(quán)值第二小的結(jié)點
Node rightNode = nodeList.get(1);
//3、構(gòu)建一顆新的二叉樹
Node parent = new Node(leftNode.value + rightNode.value);
parent.left = leftNode;
parent.right = rightNode;
//4、從list中刪除處理過的二叉樹
nodeList.remove(leftNode);
nodeList.remove(rightNode);
//5、將parent加入list
nodeList.add(parent);
}
//返回赫夫曼樹的root結(jié)點
return nodeList.get(0);
}
}
（3）控制臺輸出
到此這篇關(guān)于詳解二叉樹，2萬字帶你進入算法領(lǐng)域的文章就介紹到這了,更多相關(guān)java二叉樹內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
Gson中@JsonAdater注解的幾種方式總結(jié)
這篇文章主要介紹了Gson中@JsonAdater注解的幾種方式，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-08-08
本文主要介紹了MyBatis-Plus?分頁查詢的實現(xiàn)示例，文中通過示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-03-03
這篇文章主要介紹了Java中的RPC框架Dubbo原理和機制詳解,Dubbo 是一款Java RPC框架,致力于提供高性能的 RPC 遠程服務(wù)調(diào)用方案,作為主流的微服務(wù)框架之一,Dubbo 為開發(fā)人員帶來了非常多的便利,需要的朋友可以參考下2024-01-01
這篇文章主要介紹了BaseMapper接口的使用方法,本文通過示例代碼給大家介紹的非常詳細,對大家的學習或工作具有一定的參考借鑒價值,需要的朋友參考下吧2023-12-12
SpringBoot升級3.2報錯Invalid value type for
這篇文章給大家介紹了SpringBoot升級3.2報錯Invalid value type for attribute ‘factoryBeanObjectType‘: java.lang.String的解決方案,文中有詳細的原因分析,需要的朋友可以參考下2023-12-12
這篇文章主要為大家詳細介紹了Java組件javabean用戶登錄實例，內(nèi)容有用戶登錄，注冊和退出等，感興趣的小伙伴們可以參考一下2016-05-05
這篇文章主要介紹了mybatis查詢結(jié)果返回至實體類的示例代碼，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2020-07-07
這篇文章主要介紹了java之swing實現(xiàn)復選框的方法,實例分析了java基于圖形界面復選框的實現(xiàn)技巧,具有一定參考借鑒價值,需要的朋友可以參考下2015-09-09
SpringMVC @ControllerAdvice使用場景
這篇文章主要介紹了SpringMVC @ControllerAdvice使用場景,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2019-11-11
基于Java實現(xiàn)PDF文本旋轉(zhuǎn)傾斜
這篇文章主要介紹了基于Java實現(xiàn)PDF文本旋轉(zhuǎn)傾斜,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2020-05-05