圖文詳解Java資料結構與演算法
- WBOY轉載
- 2022-03-21 17:35:112349瀏覽
本篇文章為大家帶來了關於java的相關知識，其中主要介紹了java程式碼實作、註解解析和演算法分析等相關問題，圖文詳解希望對大家有幫助。
推薦學習：《java學習教學》
第1章資料結構與演算法基礎概述
# 1.1 資料結構與演算法的重要性
演算法是程式的靈魂，優秀的程式可以在大量資料運算時，依然保持高速運算
-
資料結構與演算法的關係：
- 程式= 資料結構演算法
- 資料結構是演算法的基礎, 換言之，想要學好演算法，需要把資料結構學到位。
資料結構與演算法學習大綱
1.2 資料結構概述
- 資料結構可以簡單的理解為資料與資料之間所存在的一些關係，資料的結構分為資料的儲存結構和資料的邏輯結構。
邏輯結構
- #集合結構：資料元素同屬於一個集合，他們之間是並列關係，無其他的關係；可以理解為中學時期學習的集合，在一個範圍之內，有很多的元素，元素間沒有什麼關係
- 線性結構：元素之間存在一對一的關係；可以理解為每個學生對應一個學號，學號與姓名就是線性結構
- 樹形結構：元素之間存在一對多的關係，可以簡單理解為家庭族譜一樣，一代接一代
- 圖形結構：元素之間存在多對多的關係，每一個元素可能對應多個元素，或被多個元素對應，網狀圖
儲存結構
- #順序儲存結構：就是將資料進行連續的存儲，我們可以將它比喻成學校食堂打飯排隊一樣，一個接著一個；
- 鍊式存儲結構：不是按照順序存儲的，後一個進來的數字只需要將他的地址告訴前一個節點，前一個節點中就存放了它後面那個數的地址，所以最後一個數的存儲地址就是為null；可以將這種結構比喻成商場吃飯叫號，上面的號碼比喻成是地址，你可以之後後面的位址是什麼，上面的其他內容就是該節點的內容；
-
區別：
- 順序儲存的特點是查詢快，插入或刪除慢
- 鍊式儲存的特點是查詢慢，插入或刪除快
#1.3 演算法概述
- 相同問題不同解決方法
- 透過時間與空間複雜度判斷演算法的優劣
- 演算法沒有最好的，只有最適合的，學習演算法是為了累積學習思路，掌握學習思路，不是為了解決某個問題去記住某種演算法；對於時間複雜度與空間複雜度，現在大多數開發情況下，我們都在使用以空間換時間，耗費更多的內存，來保證擁有更快的速度。
-
各排序演算法複雜度及穩定性：
#如何理解「大O記法」
#對於演算法進行特別具體的細緻分析雖然很好，但在實踐中的實際價值有限。對於演算法的時間性質和空間性質，最重要的是其數量級和趨勢，這些是分析演算法效率的主要部分。而計量演算法基本操作數量的規模函數中那些常數因子可以忽略不計。例如，可以認為 3n^2 和 100n^2 屬於同一個量級，如果兩個演算法處理同樣規模實例的代價分別為這兩個函數，就認為它們的效率“差不多”，都為n^2級。
時間複雜度
一個演算法花費的時間與演算法中語句的執行次數成正比例，哪個演算法中語句執行次數多,它花費時間就多。演算法中的語句執行次數稱為語句頻度或時間頻度,記為T(n)。 n 稱為問題的規模，當 n 不斷變化時，時間頻率T(n)也會不斷變化。但有時我們想知道它改變時呈現什麼規律。為此，我們引入時間複雜度概念。
一般情況下，演算法中基本運算重複執行的次數是問題規模n 的某個函數,以T(n)表示，若有某個輔助函數f(n) ，使得當n 趨近於無究大時，T(n)/f(n)的極限值為不等於零的常數，則稱f(n)是T(n)的同數量級函數。記作T(n)=O(f(n))，稱O(f(n))為演算法的漸進時間複雜度，簡稱時間複雜度。
有時候，演算法中基本操作重複執行的次數還隨問題的輸入資料集不同而不同,如在冒泡排序中，輸入資料有序而無序，結果是不一樣的。此時，我們計算平均值。
時間複雜度基本計算規則：
- 基本運算，即只有常數項，認為其時間複雜度為O(1)
- 順序結構，時間複雜度依加法計算
- 循環結構，時間複雜度依乘法計算
- 分支結構，時間複雜度取最大值
- 判斷演算法的效率時，往往只需要關注操作數量的最高次項，其它次要項和常數項可以忽略
- 在沒有特殊說明時，我們所分析的演算法的時間複雜度都是指最壞時間複雜度
常用時間複雜度：
-
注意：經常將log2n（以2為底的對數）簡寫成logn
常見時間複雜度之間的關係：
-
所以時間消耗由小到大為：
O(1 )
案例1：
count = 0; (1) for(i = 0;i
- 語句（1）執行1次
- 語句（2）執行n次
- 語句（3）執行n^2次
- 語句（4）執行n^2次
-
時間複雜度為：
T(n) = 1 n n^2 n^2 = O(n^2)
#案例2：
a = 1; (1) b = 2; (2) for(int i = 1;i
- 語句（1）、（2）執行1次
- 語句（3）執行n次
- 語句（4）、（5）、（6）執行n次
-
時間複雜度為：
T(n) = 1 1 4n = o(n)
案例3：
i = 1; (1)while(i<n i><ul>
<li>語句（1）的頻度是1</li>
<li>設語句（2）的頻度是<code>f(n)</code>，則<code>2f(n),取最大值<code>f(n) = log2n</code></code>
</li>
<li>
<strong>時間複雜度為</strong>：<code>T(n) = O(log2n)</code>
</li>
</ul>
<h3>空間複雜度</h3>
<ul>
<li><p>演算法的空間複雜度計算公式：<code>S(n) = 0( f(n) )</code>，其中n 為輸入規模，<code>f(n)</code>為語句關於n 所佔儲存空間的函數</p></li>
<li>
<p>一個演算法在電腦記憶體上所佔用的儲存空間，包括三個面向</p>
<ul>
<li>#儲存演算法本身所佔用的儲存空間</li>
<li>演算法的輸入輸出資料所佔用的儲存空間</li>
<li>演算法在運行過程中暫時佔用的儲存空間</li>
</ul>
</li>
</ul>
<p><strong>案例</strong>：指定的陣列進行反轉，並返回反轉的內容</p>
<p>解法一：</p>
<pre class="brush:php;toolbar:false">public static int[] reverse1(int[] arr) {
int n = arr.length; //申请4个字节
int temp; //申请4个字节
for (int start = 0, end = n - 1; start
-
#空間複雜度為：
S(n) = 4 4 = O(8) = O(1)
解二：
public static int[] reverse2(int[] arr) {
int n = arr.length; //申请4个字节
int[] temp = new int[n]; //申请n*4个字节+数组自身头信息开销24个字节
for (int i = n - 1; i >= 0; i--) {
temp[n - 1 - i] = arr[i];
}
return temp;}
-
空間複雜度為：
S( n) = 4 4n 24 = O(n 28) = O(n)
根據大O推導法則，演算法一的空間複雜度為0(1),演算法二的空間複雜度為0(n)，所以從空間佔用的角度來講，演算法一要優於演算法二。
由於java中有記憶體垃圾回收機制，並且jvm對程式的記憶體佔用也有最佳化(例如即時編譯) , 我們無法精確的評估一個java程式的記憶體佔用情況，但是了解了java的基本記憶體佔用，使我們可以對java程式的記憶體佔用情況進行估算。
由於現在的電腦裝置記憶體一般都比較大，基本上個人電腦都是4G起步，大的可以達到32G ，所以記憶體佔用一般情況下並不是我們演算法的瓶頸，普通情況下直接說複雜度，預設為演算法的時間複雜度。
但是，如果你做的程式是嵌入式開發，尤其是一些感測器裝置上的內建程式,由於這些裝置的記憶體很小, 一般為幾kb，這個時候對演算法的空間複雜度就有要求了，但是一般做java開發的，基本上都是伺服器開發, 一般不存在這樣的問題。
第2章 数组
2.1 数组概念
数组是一种线性表数据结构，它用一组连续的内存空间，来存储一组具有相同类型的数据。这里我们要抽取出三个跟数组相关的关键词：线性表，连续内存空间，相同数据类型；数组具有连续的内存空间，存储相同类型的数据，正是该特性使得数组具有一个特性：随机访问。但是有利有弊，这个特性虽然使得访问数组边得非常容易，但是也使得数组插入和删除操作会变得很低效，插入和删除数据后为了保证连续性,要做很多数据搬迁工作。
查找数组中的方法有两种：
- 线性查找：线性查找就是简单的查找数组中的元素
- 二分法查找：二分法查找要求目标数组必须是有序的。
2.2 无序数组
- 实现类：
public class MyArray {
//声明一个数组
private long[] arr;
//有效数据的长度
private int elements;
//无参构造函数，默认长度为50
public MyArray(){
arr = new long[50];
}
public MyArray(int maxsize){
arr = new long[maxsize];
}
//添加数据
public void insert(long value){
arr[elements] = value;
elements++;
}
//显示数据
public void display(){
System.out.print("[");
for(int i = 0;i = elements || index = elements || index = elements || index
-
优点：插入快（时间复杂度为：
O(1)）、如果知道下标，可以很快存储 -
缺点：查询慢（时间复杂度为：
O(n)）、删除慢
2.3 有序数组
- 实现类：
public class MyOrderArray {
private long[] arr;
private int elements;
public MyOrderArray(){
arr = new long[50];
}
public MyOrderArray(int maxsize){
arr = new long[maxsize];
}
//添加数据
public void insert(int value){
int i;
for(i = 0;i value){
break;
}
}
for(int j = elements;j > i;j--){
arr[j] = arr[j -1];
}
arr[i] = value;
elements++;
}
//删除数据
public void delete(int index){
if(index >=elements || index = elements || index = elements || index pow){
return -1;
}else{
if(arr[middle] > value){
//待查询的数在左边,右指针重新改变指向
pow = middle-1;
}else{
//带查询的数在右边，左指针重新改变指向
low = middle +1;
}
}
}
}}
-
优点：查询快（时间复杂度为：
O(logn)） -
缺点：增删慢（时间复杂度为：
O(n)）
第三章 栈
3.1 栈概念
栈（stack），有些地方称为堆栈，是一种容器，可存入数据元素、访问元素、删除元素，它的特点在于只能允许在容器的一端（称为栈顶端指标，英语：top）进行加入数据（英语：push）和输出数据（英语：pop）的运算。没有了位置概念，保证任何时候可以访问、删除的元素都是此前最后存入的那个元素，确定了一种默认的访问顺序。
由于栈数据结构只允许在一端进行操作，因而按照后进先出的原理运作。
栈可以用顺序表实现，也可以用链表实现。
3.2 栈的操作
- Stack() 创建一个新的空栈
- push(element) 添加一个新的元素element到栈顶
- pop() 取出栈顶元素
- peek() 返回栈顶元素
- is_empty() 判断栈是否为空
- size() 返回栈的元素个数
实现类：
package mystack;public class MyStack {
//栈的底层使用数组来存储数据
//private int[] elements;
int[] elements; //测试时使用
public MyStack() {
elements = new int[0];
}
//添加元素
public void push(int element) {
//创建一个新的数组
int[] newArr = new int[elements.length + 1];
//把原数组中的元素复制到新数组中
for (int i = 0; i <p><strong>测试类</strong>：</p><pre class="brush:php;toolbar:false">package mystack;public class Demo {
public static void main(String[] args) {
MyStack ms = new MyStack();
//添加元素
ms.push(9);
ms.push(8);
ms.push(7);
//取出栈顶元素// System.out.println(ms.pop()); //7// System.out.println(ms.pop()); //8// System.out.println(ms.pop()); //9
//查看栈顶元素
System.out.println(ms.peek()); //7
System.out.println(ms.peek()); //7
//查看栈中元素个数
System.out.println(ms.size()); //3
}}第4章 队列
4.1 队列概念
队列（Queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。
队列是一种先进先出的（First In First Out）的线性表，简称FIFO。允许插入的一端为队尾，允许删除的一端为队头。队列不允许在中间部位进行操作！假设队列是q=（a1，a2，……，an），那么a1就是队头元素，而an是队尾元素。这样我们就可以删除时，总是从a1开始，而插入时，总是在队列最后。这也比较符合我们通常生活中的习惯，排在第一个的优先出列，最后来的当然排在队伍最后。
同栈一样，队列也可以用顺序表或者链表实现。
4.2 队列的操作
- Queue() 创建一个空的队列
- enqueue(element) 往队列中添加一个element元素
- dequeue() 从队列头部删除一个元素
- is_empty() 判断一个队列是否为空
- size() 返回队列的大小
实现类：
public class MyQueue {
int[] elements;
public MyQueue() {
elements = new int[0];
}
//入队
public void enqueue(int element) {
//创建一个新的数组
int[] newArr = new int[elements.length + 1];
//把原数组中的元素复制到新数组中
for (int i = 0; i <p><strong>测试类</strong>：</p><pre class="brush:php;toolbar:false">public class Demo {
public static void main(String[] args) {
MyQueue mq = new MyQueue();
//入队
mq.enqueue(1);
mq.enqueue(2);
mq.enqueue(3);
//出队
System.out.println(mq.dequeue()); //1
System.out.println(mq.dequeue()); //2
System.out.println(mq.dequeue()); //3
}}第5章 链表
5.1 单链表
单链表概念
单链表也叫单向链表，是链表中最简单的一种形式，它的每个节点包含两个域，一个信息域（元素域）和一个链接域。这个链接指向链表中的下一个节点，而最后一个节点的链接域则指向一个空值。
- 表元素域data用来存放具体的数据。
- 链接域next用来存放下一个节点的位置
单链表操作
- is_empty() 链表是否为空
- length() 链表长度
- travel() 遍历整个链表
- add(item) 链表头部添加元素
- append(item) 链表尾部添加元素
- insert(pos, item) 指定位置添加元素
- remove(item) 删除节点
- search(item) 查找节点是否存在
实现类：
//一个节点public class Node {
//节点内容
int data;
//下一个节点
Node next;
public Node(int data) {
this.data = data;
}
//为节点追加节点
public Node append(Node node) {
//当前节点
Node currentNode = this;
//循环向后找
while (true) {
//取出下一个节点
Node nextNode = currentNode.next();
//如果下一个节点为null，当前节点已经是最后一个节点
if (nextNode == null) {
break;
}
//赋给当前节点，无线向后找
currentNode = nextNode;
}
//把需要追加的节点，追加为找到的当前节点（最后一个节点）的下一个节点
currentNode.next = node;
return this;
}
//显示所有节点信息
public void show() {
Node currentNode = this;
while (true) {
System.out.print(currentNode.data + " ");
//取出下一个节点
currentNode = currentNode.next;
//如果是最后一个节点
if (currentNode == null) {
break;
}
}
System.out.println();
}
//插入一个节点作为当前节点的下一个节点
public void after(Node node) {
//取出下一个节点，作为下下一个节点
Node nextNext = next;
//把新节点作为当前节点的下一个节点
this.next = node;
//把下下一个节点设置为新节点的下一个节点
node.next = nextNext;
}
//删除下一个节点
public void removeNode() {
//取出下下一个节点
Node newNext = next.next;
//把下下一个节点设置为当前节点的下一个节点
this.next = newNext;
}
//获取下一个节点
public Node next() {
return this.next;
}
//获取节点中的数据
public int getData() {
return this.data;
}
//判断节点是否为最后一个节点
public boolean isLast() {
return next == null;
}}
测试类：
public class Demo {
public static void main(String[] args) {
//创建节点
Node n1 = new Node(1);
Node n2 = new Node(2);
Node n3 = new Node(3);
//追加节点
n1.append(n2).append(n3);
//取出下一个节点数据
System.out.println(n1.next().next().getData()); //3
//判断节点是否为最后一个节点
System.out.println(n1.isLast()); //false
System.out.println(n1.next().next().isLast()); //true
//显示所有节点信息
n1.show(); //1 2 3
//删除一个节点// n1.next.removeNode();// n1.show(); //1 2
//插入一个新节点
n1.next.after(new Node(0));
n1.show(); //1 2 0 3
}}
5.2 循环链表
循环链表概念
单链表的一个变形是单向循环链表，链表中最后一个节点的 next 域不再为 None，而是指向链表的头节点。
循环链表操作
实现类：
//表示一个节点public class LoopNode {
//节点内容
int data;
//下一个节点
LoopNode next = this; //与单链表的区别，追加了一个this，当只有一个节点时指向自己
public LoopNode(int data) {
this.data = data;
}
//插入一个节点
public void after(LoopNode node) {
LoopNode afterNode = this.next;
this.next = node;
node.next = afterNode;
}
//删除一个节点
public void removeNext() {
LoopNode newNode = this.next.next;
this.next = newNode;
}
//获取下一个节点
public LoopNode next() {
return this.next;
}
//获取节点中的数据
public int getData() {
return this.data;
}}
测试类：
public class Demo {
public static void main(String[] args) {
//创建节点
LoopNode n1 = new LoopNode(1);
LoopNode n2 = new LoopNode(2);
LoopNode n3 = new LoopNode(3);
LoopNode n4 = new LoopNode(4);
//增加节点
n1.after(n2);
n2.after(n3);
n3.after(n4);
System.out.println(n1.next().getData()); //2
System.out.println(n2.next().getData()); //3
System.out.println(n3.next().getData()); //4
System.out.println(n4.next().getData()); //1
}}
5.3 双向循环链表
双向循环链表概念
在双向链表中有两个指针域，一个是指向前驱结点的prev，一个是指向后继结点的next指针
双向循环链表操作
实现类：
public class DoubleNode {
//上一个节点
DoubleNode pre = this;
//下一个节点
DoubleNode next = this;
//节点数据
int data;
public DoubleNode(int data) {
this.data = data;
}
//增加节点
public void after(DoubleNode node) {
//原来的下一个节点
DoubleNode nextNext = next;
//新节点作为当前节点的下一个节点
this.next = node;
//当前节点作为新节点的前一个节点
node.pre = this;
//原来的下一个节点作为新节点的下一个节点
node.next = nextNext;
//原来的下一个节点的上一个节点为新节点
nextNext.pre = node;
}
//获取下一个节点
public DoubleNode getNext() {
return this.next;
}
//获取上一个节点
public DoubleNode getPre() {
return this.pre;
}
//获取数据
public int getData() {
return this.data;
}}
测试类：
public class Demo {
public static void main(String[] args) {
//创建节点
DoubleNode n1 = new DoubleNode(1);
DoubleNode n2 = new DoubleNode(2);
DoubleNode n3 = new DoubleNode(3);
//追加节点
n1.after(n2);
n2.after(n3);
//查看上一个，自己，下一个节点内容
System.out.println(n2.getPre().getData()); //1
System.out.println(n2.getData()); //2
System.out.println(n2.getNext().getData()); //3
System.out.println(n1.getPre().getData()); //3
System.out.println(n3.getNext().getData()); //1
}}
第6章 树结构基础
6.1 为什么要使用树结构
线性结构中不论是数组还是链表，他们都存在着诟病；比如查找某个数必须从头开始查，消耗较多的时间。使用树结构，在插入和查找的性能上相对都会比线性结构要好
6.2 树结构基本概念
示意图
1、根节点：最顶上的唯一的一个；如：A
2、双亲节点：子节点的父节点就叫做双亲节点；如A是B、C、D的双亲节点，B是E、F的双亲节点
3、子节点：双亲节点所产生的节点就是子节点
4、路径：从根节点到目标节点所走的路程叫做路径；如A要访问F，路径为A-B-F
5、节点的度：有多少个子节点就有多少的度（最下面的度一定为0，所以是叶子节点）
6、节点的权：在节点中所存的数字
7、叶子节点：没有子节点的节点，就是没有下一代的节点；如：E、F、C、G
8、子树：在整棵树中将一部分看成也是一棵树，即使只有一个节点也是一棵树，不过这个树是在整个大树职中的，包含的关系
9、层：就是族谱中有多少代的人；如：A是1，B、C、D是2，E、F、G是3
10、树的高度：树的最大的层数：就是层数中的最大值
11、森林：多个树组成的集合
6.3 树的种类
无序树：树中任意节点的子节点之间没有顺序关系，这种树称为无序树，也称为自由树；
有序树：树中任意节点的子节点之间有顺序关系，这种树称为有序树；
-
二叉树：每个节点最多含有两个子树的树称为二叉树；
- 完全二叉树：对于一颗二叉树，假设其深度为d(d>1)。除了第d层外，其它各层的节点数目均已达最大值，且第d层所有节点从左向右连续地紧密排列，这样的二叉树被称为完全二叉树，其中满二叉树的定义是所有叶节点都在最底层的完全二叉树;
- 平衡二叉树（AVL树）：当且仅当任何节点的两棵子树的高度差不大于1的二叉树；
- 排序二叉树（二叉查找树（英语：Binary Search Tree），也称二叉搜索树、有序二叉树）；
- 霍夫曼树（用于信息编码）：带权路径最短的二叉树称为哈夫曼树或最优二叉树；
- B树：一种对读写操作进行优化的自平衡的二叉查找树，能够保持数据有序，拥有多余两个子树。
6.4 树的存储与表示
顺序存储：将数据结构存储在固定的数组中，然在遍历速度上有一定的优势，但因所占空间比较大，是非主流二叉树。二叉树通常以链式存储。
链式存储：
由于对节点的个数无法掌握，常见树的存储表示都转换成二叉树进行处理，子节点个数最多为2
6.5 常见的一些树的应用场景
1、xml，html等，那么编写这些东西的解析器的时候，不可避免用到树
2、路由协议就是使用了树的算法
3、mysql数据库索引
4、文件系统的目录结构
5、所以很多经典的AI算法其实都是树搜索，此外机器学习中的decision tree也是树结构
第7章 二叉树大全
7.1 二叉树的定义
任何一个节点的子节点数量不超过 2，那就是二叉树；二叉树的子节点分为左节点和右节点，不能颠倒位置
7.2 二叉树的性质(特性)
性质1：在二叉树的第i层上至多有2^(i-1)个结点（i>0）
性质2：深度为k的二叉树至多有2^k - 1个结点（k>0）
性质3：对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1;
性质4：具有n个结点的完全二叉树的深度必为 log2(n+1)
性质5：对完全二叉树，若从上至下、从左至右编号，则编号为i 的结点，其左孩子编号必为2i，其右孩子编号必为2i＋1；其双亲的编号必为i/2（i＝1 时为根,除外）
7.3 满二叉树与完全二叉树
满二叉树： 所有叶子结点都集中在二叉树的最下面一层上，而且结点总数为：2^n-1 (n为层数 / 高度）
完全二叉树： 所有的叶子节点都在最后一层或者倒数第二层，且最后一层叶子节点在左边连续，倒数第二层在右边连续（满二叉树也是属于完全二叉树）（从上往下，从左往右能挨着数满）
7.4 链式存储的二叉树
创建二叉树：首先需要一个树的类，还需要另一个类用来存放节点，设置节点；将节点放入树中，就形成了二叉树；（节点中需要权值，左子树，右子树，并且都能对他们的值进行设置）。
树的遍历：
-
先序遍历：根节点，左节点，右节点（如果节点有子树，先从左往右遍历子树，再遍历兄弟节点）
先序遍历结果为：A B D H I E J C F K G
-
中序遍历：左节点，根节点，右节点（中序遍历可以看成，二叉树每个节点，垂直方向投影下来（可以理解为每个节点从最左边开始垂直掉到地上），然后从左往右数）
中遍历结果为：H D I B E J A F K C G
-
后序遍历：左节点，右节点，根节点
后序遍历结果：H I D J E B K F G C A
-
层次遍历：从上往下，从左往右
层次遍历结果：A B C D E F G H I J K
查找节点：先对树进行一次遍历，然后找出要找的那个数；因为有三种排序方法，所以查找节点也分为先序查找，中序查找，后序查找；
删除节点：由于链式存储，不能找到要删的数直接删除，需要找到他的父节点，然后将指向该数设置为null；所以需要一个变量来指向父节点，找到数后，再断开连接。
代码实现：
- 树类
public class BinaryTree {
TreeNode root;
//设置根节点
public void setRoot(TreeNode root) {
this.root = root;
}
//获取根节点
public TreeNode getRoot() {
return root;
}
//先序遍历
public void frontShow() {
if (root != null) {
root.frontShow();
}
}
//中序遍历
public void middleShow() {
if (root != null) {
root.middleShow();
}
}
//后序遍历
public void afterShow() {
if (root != null) {
root.afterShow();
}
}
//先序查找
public TreeNode frontSearch(int i) {
return root.frontSearch(i);
}
//删除一个子树
public void delete(int i) {
if (root.value == i) {
root = null;
} else {
root.delete(i);
}
}}
- 节点类
public class TreeNode {
//节点的权
int value;
//左儿子
TreeNode leftNode;
//右儿子
TreeNode rightNode;
public TreeNode(int value) {
this.value = value;
}
//设置左儿子
public void setLeftNode(TreeNode leftNode) {
this.leftNode = leftNode;
}
//设置右儿子
public void setRightNode(TreeNode rightNode) {
this.rightNode = rightNode;
}
//先序遍历
public void frontShow() {
//先遍历当前节点的值
System.out.print(value + " ");
//左节点
if (leftNode != null) {
leftNode.frontShow(); //递归思想
}
//右节点
if (rightNode != null) {
rightNode.frontShow();
}
}
//中序遍历
public void middleShow() {
//左节点
if (leftNode != null) {
leftNode.middleShow(); //递归思想
}
//先遍历当前节点的值
System.out.print(value + " ");
//右节点
if (rightNode != null) {
rightNode.middleShow();
}
}
//后续遍历
public void afterShow() {
//左节点
if (leftNode != null) {
leftNode.afterShow(); //递归思想
}
//右节点
if (rightNode != null) {
rightNode.afterShow();
}
//先遍历当前节点的值
System.out.print(value + " ");
}
//先序查找
public TreeNode frontSearch(int i) {
TreeNode target = null;
//对比当前节点的值
if (this.value == i) {
return this;
//当前节点不是要查找的节点
} else {
//查找左儿子
if (leftNode != null) {
//查找的话t赋值给target，查不到target还是null
target = leftNode.frontSearch(i);
}
//如果target不为空，说明在左儿子中已经找到
if (target != null) {
return target;
}
//如果左儿子没有查到，再查找右儿子
if (rightNode != null) {
target = rightNode.frontSearch(i);
}
}
return target;
}
//删除一个子树
public void delete(int i) {
TreeNode parent = this;
//判断左儿子
if (parent.leftNode != null && parent.leftNode.value == i) {
parent.leftNode = null;
return;
}
//判断右儿子
if (parent.rightNode != null && parent.rightNode.value == i) {
parent.rightNode = null;
return;
}
//如果都不是，递归检查并删除左儿子
parent = leftNode;
if (parent != null) {
parent.delete(i);
}
//递归检查并删除右儿子
parent = rightNode;
if (parent != null) {
parent.delete(i);
}
}}
- 测试类
public class Demo {
public static void main(String[] args) {
//创建一棵树
BinaryTree binaryTree = new BinaryTree();
//创建一个根节点
TreeNode root = new TreeNode(1);
//把根节点赋给树
binaryTree.setRoot(root);
//创建左,右节点
TreeNode rootLeft = new TreeNode(2);
TreeNode rootRight = new TreeNode(3);
//把新建的节点设置为根节点的子节点
root.setLeftNode(rootLeft);
root.setRightNode(rootRight);
//为第二层的左节点创建两个子节点
rootLeft.setLeftNode(new TreeNode(4));
rootLeft.setRightNode(new TreeNode(5));
//为第二层的右节点创建两个子节点
rootRight.setLeftNode(new TreeNode(6));
rootRight.setRightNode(new TreeNode(7));
//先序遍历
binaryTree.frontShow(); //1 2 4 5 3 6 7
System.out.println();
//中序遍历
binaryTree.middleShow(); //4 2 5 1 6 3 7
System.out.println();
//后序遍历
binaryTree.afterShow(); //4 5 2 6 7 3 1
System.out.println();
//先序查找
TreeNode result = binaryTree.frontSearch(5);
System.out.println(result); //binarytree.TreeNode@1b6d3586
//删除一个子树
binaryTree.delete(2);
binaryTree.frontShow(); //1 3 6 7 ，2和他的子节点被删除了
}}
7.5 顺序存储的二叉树
概述：顺序存储使用数组的形式实现；由于非完全二叉树会导致数组中出现空缺，有的位置不能填上数字，所以顺序存储二叉树通常情况下只考虑完全二叉树
原理： 顺序存储在数组中是按照第一层第二层一次往下存储的，遍历方式也有先序遍历、中序遍历、后续遍历
性质：
- 第n个元素的左子节点是：2*n+1；
- 第n个元素的右子节点是：2*n+2；
- 第n个元素的父节点是：（n-1)/2
代码实现：
- 树类
public class ArrayBinaryTree {
int[] data;
public ArrayBinaryTree(int[] data) {
this.data = data;
}
//重载先序遍历方法，不用每次传参数了,保证每次从头开始
public void frontShow() {
frontShow(0);
}
//先序遍历
public void frontShow(int index) {
if (data == null || data.length == 0) {
return;
}
//先遍历当前节点的内容
System.out.print(data[index] + " ");
//处理左子树：2*index+1
if (2 * index + 1
- 测试类
public class Demo {
public static void main(String[] args) {
int[] data = {1,2,3,4,5,6,7};
ArrayBinaryTree tree = new ArrayBinaryTree(data);
//先序遍历
tree.frontShow(); //1 2 4 5 3 6 7
}}
7.6 线索二叉树(Threaded BinaryTree)
为什么使用线索二叉树？
当用二叉链表作为二叉树的存储结构时，可以很方便的找到某个结点的左右孩子；但一般情况下，无法直接找到该结点在某种遍历序列中的前驱和后继结点
原理：n个结点的二叉链表中含有n+1(2n-(n-1)=n+1个空指针域。利用二叉链表中的空指针域，存放指向结点在某种遍历次序下的前驱和后继结点的指针。
例如：某个结点的左孩子为空，则将空的左孩子指针域改为指向其前驱；如果某个结点的右孩子为空，则将空的右孩子指针域改为指向其后继（这种附加的指针称为"线索"）
代码实现：
- 树类
public class ThreadedBinaryTree {
ThreadedNode root;
//用于临时存储前驱节点
ThreadedNode pre = null;
//设置根节点
public void setRoot(ThreadedNode root) {
this.root = root;
}
//中序线索化二叉树
public void threadNodes() {
threadNodes(root);
}
public void threadNodes(ThreadedNode node) {
//当前节点如果为null，直接返回
if (node == null) {
return;
}
//处理左子树
threadNodes(node.leftNode);
//处理前驱节点
if (node.leftNode == null) {
//让当前节点的左指针指向前驱节点
node.leftNode = pre;
//改变当前节点左指针类型
node.leftType = 1;
}
//处理前驱的右指针，如果前驱节点的右指针是null（没有右子树）
if (pre != null && pre.rightNode == null) {
//让前驱节点的右指针指向当前节点
pre.rightNode = node;
//改变前驱节点的右指针类型
pre.rightType = 1;
}
//每处理一个节点，当前节点是下一个节点的前驱节点
pre = node;
//处理右子树
threadNodes(node.rightNode);
}
//遍历线索二叉树
public void threadIterate() {
//用于临时存储当前遍历节点
ThreadedNode node = root;
while (node != null) {
//循环找到最开始的节点
while (node.leftType == 0) {
node = node.leftNode;
}
//打印当前节点的值
System.out.print(node.value + " ");
//如果当前节点的右指针指向的是后继节点，可能后继节点还有后继节点
while (node.rightType == 1) {
node = node.rightNode;
System.out.print(node.value + " ");
}
//替换遍历的节点
node = node.rightNode;
}
}
//获取根节点
public ThreadedNode getRoot() {
return root;
}
//先序遍历
public void frontShow() {
if (root != null) {
root.frontShow();
}
}
//中序遍历
public void middleShow() {
if (root != null) {
root.middleShow();
}
}
//后序遍历
public void afterShow() {
if (root != null) {
root.afterShow();
}
}
//先序查找
public ThreadedNode frontSearch(int i) {
return root.frontSearch(i);
}
//删除一个子树
public void delete(int i) {
if (root.value == i) {
root = null;
} else {
root.delete(i);
}
}}
- 节点类
public class ThreadedNode {
//节点的权
int value;
//左儿子
ThreadedNode leftNode;
//右儿子
ThreadedNode rightNode;
//标识指针类型,1表示指向上一个节点，0
int leftType;
int rightType;
public ThreadedNode(int value) {
this.value = value;
}
//设置左儿子
public void setLeftNode(ThreadedNode leftNode) {
this.leftNode = leftNode;
}
//设置右儿子
public void setRightNode(ThreadedNode rightNode) {
this.rightNode = rightNode;
}
//先序遍历
public void frontShow() {
//先遍历当前节点的值
System.out.print(value + " ");
//左节点
if (leftNode != null) {
leftNode.frontShow(); //递归思想
}
//右节点
if (rightNode != null) {
rightNode.frontShow();
}
}
//中序遍历
public void middleShow() {
//左节点
if (leftNode != null) {
leftNode.middleShow(); //递归思想
}
//先遍历当前节点的值
System.out.print(value + " ");
//右节点
if (rightNode != null) {
rightNode.middleShow();
}
}
//后续遍历
public void afterShow() {
//左节点
if (leftNode != null) {
leftNode.afterShow(); //递归思想
}
//右节点
if (rightNode != null) {
rightNode.afterShow();
}
//先遍历当前节点的值
System.out.print(value + " ");
}
//先序查找
public ThreadedNode frontSearch(int i) {
ThreadedNode target = null;
//对比当前节点的值
if (this.value == i) {
return this;
//当前节点不是要查找的节点
} else {
//查找左儿子
if (leftNode != null) {
//查找的话t赋值给target，查不到target还是null
target = leftNode.frontSearch(i);
}
//如果target不为空，说明在左儿子中已经找到
if (target != null) {
return target;
}
//如果左儿子没有查到，再查找右儿子
if (rightNode != null) {
target = rightNode.frontSearch(i);
}
}
return target;
}
//删除一个子树
public void delete(int i) {
ThreadedNode parent = this;
//判断左儿子
if (parent.leftNode != null && parent.leftNode.value == i) {
parent.leftNode = null;
return;
}
//判断右儿子
if (parent.rightNode != null && parent.rightNode.value == i) {
parent.rightNode = null;
return;
}
//如果都不是，递归检查并删除左儿子
parent = leftNode;
if (parent != null) {
parent.delete(i);
}
//递归检查并删除右儿子
parent = rightNode;
if (parent != null) {
parent.delete(i);
}
}}
- 测试类
public class Demo {
public static void main(String[] args) {
//创建一棵树
ThreadedBinaryTree binaryTree = new ThreadedBinaryTree();
//创建一个根节点
ThreadedNode root = new ThreadedNode(1);
//把根节点赋给树
binaryTree.setRoot(root);
//创建左,右节点
ThreadedNode rootLeft = new ThreadedNode(2);
ThreadedNode rootRight = new ThreadedNode(3);
//把新建的节点设置为根节点的子节点
root.setLeftNode(rootLeft);
root.setRightNode(rootRight);
//为第二层的左节点创建两个子节点
rootLeft.setLeftNode(new ThreadedNode(4));
ThreadedNode fiveNode = new ThreadedNode(5);
rootLeft.setRightNode(fiveNode);
//为第二层的右节点创建两个子节点
rootRight.setLeftNode(new ThreadedNode(6));
rootRight.setRightNode(new ThreadedNode(7));
//中序遍历
binaryTree.middleShow(); //4 2 5 1 6 3 7
System.out.println();
//中序线索化二叉树
binaryTree.threadNodes();// //获取5的后继节点// ThreadedNode afterFive = fiveNode.rightNode;// System.out.println(afterFive.value); //1
binaryTree.threadIterate(); //4 2 5 1 6 3 7
}}
7.7 二叉排序树（Binary Sort Tree）
无序序列：
二叉排序树图解：
概述：二叉排序树（Binary Sort Tree）也叫二叉查找树或者是一颗空树，对于二叉树中的任何一个非叶子节点，要求左子节点比当前节点值小，右子节点比当前节点值大
特点：
- 查找性能与插入删除性能都适中还不错
- 中序遍历的结果刚好是从大到小
创建二叉排序树原理：其实就是不断地插入节点，然后进行比较。
删除节点
- 删除叶子节点，只需要找到父节点，将父节点与他的连接断开即可
- 删除有一个子节点的就需要将他的子节点换到他现在的位置
- 删除有两个子节点的节点，需要使用他的前驱节点或者后继节点进行替换，就是左子树最右下方的数（最大的那个）或右子树最左边的树（最小的数）；即离节点值最接近的值；（还要注解要去判断这个值有没有右节点，有就要将右节点移上来）
代码实现：
- 树类
public class BinarySortTree {
Node root;
//添加节点
public void add(Node node) {
//如果是一颗空树
if (root == null) {
root = node;
} else {
root.add(node);
}
}
//中序遍历
public void middleShow() {
if (root != null) {
root.middleShow(root);
}
}
//查找节点
public Node search(int value) {
if (root == null) {
return null;
}
return root.search(value);
}
//查找父节点
public Node searchParent(int value) {
if (root == null) {
return null;
}
return root.searchParent(value);
}
//删除节点
public void delete(int value) {
if (root == null) {
return;
} else {
//找到这个节点
Node target = search(value);
//如果没有这个节点
if (target == null) {
return;
}
//找到他的父节点
Node parent = searchParent(value);
//要删除的节点是叶子节点
if (target.left == null && target.left == null) {
//要删除的节点是父节点的左子节点
if (parent.left.value == value) {
parent.left = null;
}
//要删除的节点是父节点的右子节点
else {
parent.right = null;
}
}
//要删除的节点有两个子节点的情况
else if (target.left != null && target.right != null) {
//删除右子树中值最小的节点，并且获取到值
int min = deletMin(target.right);
//替换目标节点中的值
target.value = min;
}
//要删除的节点有一个左子节点或右子节点
else {
//有左子节点
if (target.left != null) {
//要删除的节点是父节点的左子节点
if (parent.left.value == value) {
parent.left = target.left;
}
//要删除的节点是父节点的右子节点
else {
parent.right = target.left;
}
}
//有右子节点
else {
//要删除的节点是父节点的左子节点
if (parent.left.value == value) {
parent.left = target.right;
}
//要删除的节点是父节点的右子节点
else {
parent.right = target.right;
}
}
}
}
}
//删除一棵树中最小的节点
private int deletMin(Node node) {
Node target = node;
//递归向左找最小值
while (target.left != null) {
target = target.left;
}
//删除最小的节点
delete(target.value);
return target.value;
}}
- 节点类
public class Node {
int value;
Node left;
Node right;
public Node(int value) {
this.value = value;
}
//向子树中添加节点
public void add(Node node) {
if (node == null) {
return;
}
/*判断传入的节点的值比当前紫薯的根节点的值大还是小*/
//添加的节点比当前节点更小(传给左节点）
if (node.value value && this.left != null) {
return this.left.searchParent(value);
} else if (this.value
- 测试类
public class Demo {
public static void main(String[] args) {
int[] arr = {8, 3, 10, 1, 6, 14, 4, 7, 13};
//创建一颗二叉排序树
BinarySortTree bst = new BinarySortTree();
//循环添加/* for(int i=0;i<h2>7.8 平衡二叉树（ Balanced Binary Tree）</h2><h3>为什么使用平衡二叉树？</h3><p>平衡二叉树（Balanced Binary Tree）又被称为AVL树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。这个方案很好的解决了二叉查找树退化成链表的问题，把插入，查找，删除的时间复杂度最好情况和最坏情况都维持在<code>O(logN)</code>。但是频繁旋转会使插入和删除牺牲掉<code>O(logN)</code>左右的时间，不过相对二叉查找树来说，时间上稳定了很多。</p><p>二叉排序树插入 {1,2,3,4,5,6} 这种数据结果如下图所示：<br><img src="https://img.php.cn/upload/article/000/000/067/3ecfcc25f4c8b7a56d063b2b27bace0c-23.png" alt="圖文詳解Java資料結構與演算法"><br> 平衡二叉树插入 {1,2,3,4,5,6} 这种数据结果如下图所示：<br><img src="https://img.php.cn/upload/article/000/000/067/3ecfcc25f4c8b7a56d063b2b27bace0c-24.png" alt="圖文詳解Java資料結構與演算法"></p><h3>如何判断平衡二叉树？</h3>
- 1、是二叉排序树
- 2、任何一个节点的左子树或者右子树都是平衡二叉树（左右高度差小于等于 1）
（1）下图不是平衡二叉树，因为它不是二叉排序树违反第 1 条件
（2）下图不是平衡二叉树，因为有节点子树高度差大于 1 违法第 2 条件（5的左子树为0，右子树为2）
（3）下图是平衡二叉树，因为符合 1、2 条件
相关概念
平衡因子 BF
- 定義：左子樹和右子樹高度差
- 計算：
左子樹高度- 右子樹高度的值 - 別名：簡稱BF（Balance Factor）
- 一般來說BF 的絕對值大於1，,平衡樹二叉樹就失衡，需要旋轉修正
##最小不平衡子樹
- 距離插入節點最近的，且BF 的絕對值大於1 的節點為根節點的子樹。
- 旋轉修正只需要修正最小不平衡子樹即可
- #範例如下圖所示：
##旋轉方式
:左旋:
舊根節點為新根節點的左子樹- 新根節點的左子樹（如果存在）為舊根節點的右子樹
- 右旋：
舊根節點為新根節點的右子樹
- 新根節點的右子樹（如果存在）為舊根節點的左子樹
：
左左型：插入左小孩的左子樹，右旋- 右右型：插入右小孩的右子樹，左旋
- 左右型：插入左孩子的右子樹，先左旋，再右旋
- 右左型：插入右孩子的左子樹，先右旋，再左旋
-
：第三個節點（1）插入的時候，
BF(3) = 2， BF(2) = 1，右旋，根節點順時針旋轉
#右右型
：第三個節點（3）插入的時候，
，RR 型失衡，左旋，根節點逆時針旋轉
左右型
：第三個節點（3）插入的時候，
LR 型失衡，先左旋再右旋
右左型
：第三個節點（1）插入的時候，
RL 型失衡，先右旋再左旋
#實例
（1）、依序插入3、2、1 插入第三個點1 的時候
BF(3)=2 BF(2)=1，LL 型失衡，對最小不平衡樹{3,2,1}進行右旋
- 新根節點（節點2）的右子樹（這裡沒有右子樹）為舊根節點的左子樹
-
（2）依序插入4 ，5 插入5 點的時候
，RR 型失衡，對最小不平衡樹{3,4,5} 進行左旋
- 新根節點（節點4）的左子樹（這裡沒有左子樹）為舊根節點的右子樹
-
（3）插入4 ，5 插入5 點的時候
，RR 型失衡對最小不平衡樹{1,2 ,4}進行左旋
-
##新根節點（節點4）的左子樹（節點3）為舊根節點的右子樹
-
（4）插入7 節點的時候 BF(5)=- 2, BF(6)=-1
- 旧根节点（节点 5）为新根节点（节点 6）的左子树
- 新根节点的左子树（这里没有）为旧根节点的右子树
（5）依次插入 10 ，9 。插入 9 点的时候 BF(10) = 1，BF(7) = -2，RL 型失衡，对先右旋再左旋，右子树先右旋
- 旧根节点（节点 10）为新根节点（节点 9）的右子树
- 新根节点（节点 9）的右子树（这里没有右子树）为旧根节点的左子树
最小不平衡子树再左旋： - 旧根节点（节点 7）为新根节点（节点 9）的左子树
- 新根节点（节点 9）的左子树（这里没有左子树）为旧根节点的右子树
代码实现
- 节点类
public class Node {
int value;
Node left;
Node right;
public Node(int value) {
this.value = value;
}
//获取当前节点高度
public int height() {
return Math.max(left == null ? 0 : left.height(), right == null ? 0 : right.height()) + 1;
}
//获取左子树高度
public int leftHeight() {
if (left == null) {
return 0;
}
return left.height();
}
//获取右子树高度
public int rightHeight() {
if (right == null) {
return 0;
}
return right.height();
}
//向子树中添加节点
public void add(Node node) {
if (node == null) {
return;
}
/*判断传入的节点的值比当前紫薯的根节点的值大还是小*/
//添加的节点比当前节点更小(传给左节点）
if (node.value = 2) {
//双旋转，当左子树左边高度小于左子树右边高度时
if (left != null && left.leftHeight() value && this.left != null) {
return this.left.searchParent(value);
} else if (this.value
- 测试类
public class Demo {
public static void main(String[] args) {
int[] arr = {1,2,3,4,5,6};
//创建一颗二叉排序树
BinarySortTree bst = new BinarySortTree();
//循环添加
for (int i : arr) {
bst.add(new Node(i));
}
//查看高度
System.out.println(bst.root.height()); //3
//查看节点值
System.out.println(bst.root.value); //根节点为4
System.out.println(bst.root.left.value); //左子节点为2
System.out.println(bst.root.right.value); //右子节点为5
}}
第8章 赫夫曼树
8.1 赫夫曼树概述
HuffmanTree因为翻译不同所以有其他的名字：赫夫曼树、霍夫曼树、哈夫曼树
赫夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的路径长度是从树根到每一结点的路径长度之和，记为WPL=（W1L1+W2L2+W3L3+…+WnLn），N个权值Wi（i=1,2,…n）构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li（i=1,2,…n）。可以证明赫夫曼树的WPL是最小的。
8.2 赫夫曼树定义
路径： 路径是指从一个节点到另一个节点的分支序列。
路径长度： 指从一个节点到另一个结点所经过的分支数目。 如下图：从根节点到a的分支数目为2
树的路径长度： 树中所有结点的路径长度之和为树的路径长度PL。 如下图：PL为10
节点的权： 给树的每个结点赋予一个具有某种实际意义的实数，我们称该实数为这个结点的权。如下图：7、5、2、4
带权路径长度： 从树根到某一结点的路径长度与该节点的权的乘积，叫做该结点的带权路径长度。如下图：A的带权路径长度为2*7=14
树的带权路径长度（WPL）： 树的带权路径长度为树中所有叶子节点的带权路径长度之和
最优二叉树：权值最大的节点离跟节点越近的二叉树，所得WPL值最小，就是最优二叉树。如下图：（b）
- （a）
WPL=9*2+4*2+5*2+2*2=40 - （b）
WPL=9*1+5*2+4*3+2*3=37 - （c）
WPL=4*1+2*2+5*3+9*3=50
8.3 构造赫夫曼树步骤
对于数组{5,29,7,8,14,23,3,11}，我们把它构造成赫夫曼树
第一步：使用数组中所有元素创建若干个二叉树，这些值作为节点的权值（只有一个节点）。
第二步：将这些节点按照权值的大小进行排序。
第三步：取出权值最小的两个节点，并创建一个新的节点作为这两个节点的父节点，这个父节点的权值为两个子节点的权值之和。将这两个节点分别赋给父节点的左右节点
第四步：删除这两个节点，将父节点添加进集合里
第五步：重复第二步到第四步，直到集合中只剩一个元素，结束循环
8.4 代码实现
- 节点类
//接口实现排序功能public class Node implements Comparable<node> {
int value;
Node left;
Node right;
public Node(int value) {
this.value = value;
}
@Override
public int compareTo(Node o) {
return -(this.value - o.value); //集合倒叙，从大到小
}
@Override
public String toString() {
return "Node value=" + value ;
}}</node>
- 测试类
import java.util.ArrayList;import java.util.Collections;import java.util.List;public class Demo {
public static void main(String[] args) {
int[] arr = {5, 29, 7, 8, 14, 23, 3, 11};
Node node = createHuffmanTree(arr);
System.out.println(node); //Node value=100
}
//创建赫夫曼树
public static Node createHuffmanTree(int[] arr) {
//使用数组中所有元素创建若干个二叉树（只有一个节点）
List<node> nodes = new ArrayList();
for (int value : arr) {
nodes.add(new Node(value));
}
//循环处理
while (nodes.size() > 1) {
//排序
Collections.sort(nodes);
//取出最小的两个二叉树（集合为倒叙，从大到小）
Node left = nodes.get(nodes.size() - 1); //权值最小
Node right = nodes.get(nodes.size() - 2); //权值次小
//创建一个新的二叉树
Node parent = new Node(left.value + right.value);
//删除原来的两个节点
nodes.remove(left);
nodes.remove(right);
//新的二叉树放入原来的二叉树集合中
nodes.add(parent);
//打印结果
System.out.println(nodes);
}
return nodes.get(0);
}}</node>
- 循环次数结果
[Node value=29, Node value=23, Node value=14, Node value=11, Node value=8, Node value=7, Node value=8][Node value=29, Node value=23, Node value=14, Node value=11, Node value=8, Node value=15][Node value=29, Node value=23, Node value=15, Node value=14, Node value=19][Node value=29, Node value=23, Node value=19, Node value=29][Node value=29, Node value=29, Node value=42][Node value=42, Node value=58][Node value=100]Node value=100Process finished with exit code 0
第9章 多路查找树（2-3树、2-3-4树、B树、B+树）
9.1 为什么使用多路查找树
二叉树存在的问题
二叉树需要加载到内存的，如果二叉树的节点少，没有什么问题，但是如果二叉树的节点很多(比如1亿)， 就存在如下问题:
问题1：在构建二叉树时，需要多次进行I/O操作(海量数据存在数据库或文件中)，节点海量，构建二叉树时，
速度有影响.问题2：节点海量，也会造成二叉树的
高度很大，会降低操作速度.
解决上述问题 —> 多叉树
多路查找树
- 1、在二叉树中，每个节点有数据项，最多有两个子节点。如果允许每个节点可以有
更多的数据项和更多的子节点，就是多叉树（multiway tree） - 2、后面我们讲解的"2-3树"，"2-3-4树"就是多叉树，多叉树通过
重新组织节点，减少树的高度，能对二叉树进行优化。 - 3、举例说明(下面2-3树就是一颗多叉树)
9.2 2-3树
2-3树定义
- 所有叶子节点都要在同一层
- 二节点要么有两个子节点，要么没有节点
- 三节点要么没有节点，要么有三个子节点
- 不能出现节点不满的情况
2-3树插入的操作
插入原理：
对于2-3树的插入来说，与平衡二叉树相同，插入操作一定是发生在叶子节点上，并且节点的插入和删除都有可能导致不平衡的情况发生，在插入和删除节点时也是需要动态维持平衡的，但维持平衡的策略和AVL树是不一样的。
AVL树向下添加节点之后通过旋转来恢复平衡，而2-3树是通过节点向上分裂来维持平衡的，也就是说2-3树插入元素的过程中层级是向上增加的，因此不会导致叶子节点不在同一层级的现象发生，也就不需要旋转了。
三种插入情况：
1）对于空树，插入一个2节点即可；
2）插入节点到一个2节点的叶子上。由于本身就只有一个元素，所以只需要将其升级为3节点即可（如：插入3）。
3）插入节点到一个3节点的叶子上。因为3节点本身最大容量，因此需要拆分，且将树中两元素或者插入元素的三者中选择其一向上移动一层。
分为三种情况：
- 升级父节点（插入5）
- 升级根节点（插入11）
- 增加树高度（插入2，从下往上拆）
2-3树删除的操作
删除原理：2-3树的删除也分为三种情况，与插入相反。
三种删除情况：
1）所刪元素位於一個3節點的葉子節點上，直接刪除，不會影響樹狀結構（如：刪除9）
2）所刪元素位於一個2節點上，直接刪除，破壞樹結構
分為四種情況：
此節點雙親也是2節點，且擁有3節點的右孩子（如：刪除1）
此節點的雙親是2節點，它右孩子也是2節點（如：刪除4）
此節點的雙親是3節點（如：刪除10）
目前樹是滿二元樹，降低樹高（如：刪除8）
3）所刪元素位於非葉子的分支節點。此時依樹中序遍歷得到此元素的前驅或後續元素，補位
兩種情況：
- 分支節點是2節點（如：刪除4）
- 分支節點是3節點（如：刪除12）
#9.3 2-3-4樹
##2 -3-4樹是2-3樹的擴展，包括了4 節點的使用，一個4 節點包含小中大三個元素和四個孩子（或沒有孩子）2-3-4樹的插入操作1）如果待插入的節點不是4 節點，則直接插入即可2）如果待插入的節點是4 節點，則先把新節點暫時插入進去變成5 個節點，然後對5 個節點進行向上分裂、合併，5 個節點分裂成兩個2 節點（5 個節點最小的元素、5 個節點第二個元素）、1個3 個節點（5 個節點後兩個元素），然後將分裂之後的第2個2 節點向上合併到父節點中，然後把父節點作為插入元素之後的當前節點，重複（1）、（2）步驟，直到滿足2-3-4樹的定義性質
B樹的資料結構為內外存的資料互動所準備的。當要處理的資料很大時，無法一次全部裝入記憶體。這時對B樹調整，使得B樹的階數與硬碟儲存的頁面大小相符。例如一棵B樹的階為1001（即1個節點包含1000個關鍵字），高度為2（從0開始），它可以儲存超過10億個關鍵字（1001x1001x1000 1001x1000 1000）,只要讓根節點持久的保留在記憶體中，那麼在這顆樹上，尋找某一個關鍵字至多需要兩次硬碟的讀取即可。
對於n個關鍵字的m階B樹，最壞情況查找次數計算
第一層至少1個節點，第二層至少2個節點，由於除根節點外每個分支節點至少有⌈m/2⌉棵子樹，則第三層至少有2x⌈m/2⌉個節點。 。 。這樣第k 1層至少有2x(⌈m/2⌉)^(k-1),實際上，k 1層的節點就是葉子節點。若m階B樹有n個關鍵字，那麼當你找到葉子節點，其實也等於找不成功的節點為n 1，因此
n 1>=2x(⌈m/2⌉)^(k -1),即
在含有n個關鍵字的B樹上尋找時，從根節點到關鍵字節點的路徑上涉及的節點數不超多
9.5 B 樹
B 樹可以說是B樹的升級版，相對於B樹來說B 樹更充分的利用了節點的空間，讓查詢速度更加穩定，其速度完全接近二分法查找。大部分檔案系統和資料均採用B 樹來實現索引結構。
下圖B樹，我們要遍歷它，假設每個節點都屬於硬碟的不同頁面，我們為了中序遍歷所有的元素，頁面2-頁面1-頁面3-頁面1-頁面4 -頁1-頁面5，頁面1遍歷了3次，而且我們每經過節點遍歷時，都會對節點中的元素進行一次遍歷
B 樹是應檔案系統所需而出的一種B樹的變形樹，在B樹中，每一個元素樹中只出現一次，而B 樹中，出現在分支節點中的元素會被當作他們在該分支節點位置的中序後繼者（葉子節點）中再次列出。另外，每一個葉子節點都會保存一個指向後一葉節點的指標。
下圖就是B 樹，灰色關鍵字，在根節點出現，在葉子節點中再次列出
一棵m階的B 樹和m階的B樹的差異在於：
- 有n棵子樹的非葉節點中包含有n個關鍵字（B樹中是n-1個關鍵字），但每個關鍵字不保存數據，只用來保存葉子節點相同關鍵字的索引，所有數據都保存在葉子節點。 （此處，對於非葉節點的m顆子樹和n個關鍵字的關係，mysql的索引結構似乎是m=n 1，而不是上面的m=n）
- 所有的非葉節點元素都同時存在於子節點，在子節點元素中是最大（或最小）元素。
- 所有的葉子節點包含全部關鍵字的信息，及指向含這些關鍵字所指向的具體磁碟記錄的指針data，並且每一個葉子節點帶有指向下一個相鄰的葉節點指針，形成鍊錶
9.6 總結
B樹的非葉節點會儲存關鍵字及其對應的資料位址，B 樹的非葉節點只存關鍵字索引，不會存特定的資料位址，因此B 樹的一個節點相比B樹能儲存更多的索引元素，一次性讀入記憶體的需要尋找的關鍵字也就越多，B 樹的高度更小，相對IO讀寫次數就降低了。
B樹的查詢效率並不穩定，最好的情況只查詢一次（根節點），最壞情況是查找到葉子節點，而B 樹由於非葉節點不存資料位址，而只是葉子節點中關鍵字的索引。所有查詢都要查找到葉子節點才算命中，查詢效率比較穩定。這對於sql語句的最佳化是非常有幫助的。
B 樹所有葉子節點形成有序鍊錶，只需要去遍歷葉子節點就可以實現整棵樹的遍歷。方便資料的範圍查詢，而B樹不支援這樣的操作或說效率太低。
現代資料庫和檔案系統的索引表大部分是使用B 樹來實現的，但並不是全部
第10章圖結構
10.1 圖的基本概念
圖（Graph）是一種複雜的非線性結構，在圖結構中，每個元素都可以有零個或多個前驅，也可以有零個或多個後繼，也就是說，元素之間的關係是任意的。
常用術語：
| 術語 | 意義 |
|---|---|
| #頂點 | 圖中的某個結點 |
| 邊 | 頂點之間連線 |
| 相鄰頂點 | 由同一條邊連接在一起的頂點 |
| 度 | 一個頂點的相鄰頂點個數 |
| 由一個頂點到另一個頂點的路線，且沒有重複經過頂點 | |
| 出發點和結束點都是同一個頂點 | |
| 圖中所有的邊都沒有方向 | |
| 圖中所有的邊都有方向 | |
| 圖中的邊沒有權重值 | |
| 圖中的邊帶有一定的權重值 |
图中的 0 表示该顶点无法通向另一个顶点，相反 1 就表示该顶点能通向另一个顶点
那么我们需要进行n-1次冒泡过程，每次对应的比较次数如下图所示：
同时，我们对堆中的结点按层进行编号，将这种逻辑结构映射到数组中就是下面这个样子
该数组从逻辑上讲就是一个堆结构，我们用简单的公式来描述一下堆的定义就是：
4）这时，交换导致了子根[4,5,6]结构混乱，继续调整，[4,5,6]中6最大，交换4和6。
此时，我们就将一个无需序列构造成了一个大顶堆
以上是圖文詳解Java資料結構與演算法的詳細內容。更多資訊請關注PHP中文網其他相關文章！