資料結構之樹結構實際應用
一、堆排序
1.基本介紹
2.基本思想
3.代碼實作
package com.atguigu.tree;
import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;
public class HeapSort {
public static void main(String[] args) {
//要求将數組進行升序排序
//int arr[] = {4, 6, 8, 5, 9};
// 建立要給80000個的随機的數組
int[] arr = new int[8000000];
for (int i = 0; i < 8000000; i++) {
arr[i] = (int) (Math.random() * 8000000); // 生成一個[0, 8000000) 數
}
System.out.println("排序前");
Date data1 = new Date();
SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
String date1Str = simpleDateFormat.format(data1);
System.out.println("排序前的時間是=" + date1Str);
heapSort(arr);
Date data2 = new Date();
String date2Str = simpleDateFormat.format(data2);
System.out.println("排序前的時間是=" + date2Str);
//System.out.println("排序後=" + Arrays.toString(arr));
}
//編寫一個堆排序的方法
public static void heapSort(int arr[]) {
int temp = 0;
System.out.println("堆排序!!");
// //分步完成
// adjustHeap(arr, 1, arr.length);
// System.out.println("第一次" + Arrays.toString(arr)); // 4, 9, 8, 5, 6
//
// adjustHeap(arr, 0, arr.length);
// System.out.println("第2次" + Arrays.toString(arr)); // 9,6,8,5,4
//完成我們最終代碼
//将無序序列建構成一個堆，根據升序降序需求選擇大頂堆或小頂堆
for(int i = arr.length / 2 -1; i >=0; i--) {
adjustHeap(arr, i, arr.length);
}
/*
* 2).将堆頂元素與末尾元素交換，将最大元素"沉"到數組末端;
3).重新調整結構，使其滿足堆定義，然後繼續交換堆頂元素與目前末尾元素，反複執行調整+交換步驟，直到整個序列有序。
*/
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));
}
//将一個數組(二叉樹), 調整成一個大頂堆
/**
* 功能： 完成 将 以 i 對應的非葉子結點的樹調整成大頂堆
* 舉例 int arr[] = {4, 6, 8, 5, 9}; => i = 1 => adjustHeap => 得到 {4, 9, 8, 5, 6}
* 如果我們再次調用 adjustHeap 傳入的是 i = 0 => 得到 {4, 9, 8, 5, 6} => {9,6,8,5, 4}
* @param arr 待調整的數組
* @param i 表示非葉子結點在數組中索引
* @param lenght 表示對多少個元素繼續調整， length 是在逐漸的減少
*/
public static void adjustHeap(int arr[], int i, int lenght) {
int temp = arr[i];//先取出目前元素的值，儲存在臨時變量
//開始調整
//說明
//1. k = i * 2 + 1 k 是 i結點的左子結點
for(int k = i * 2 + 1; k < lenght; k = k * 2 + 1) {
if(k+1 < lenght && arr[k] < arr[k+1]) { //說明左子結點的值小于右子結點的值
k++; // k 指向右子結點
}
if(arr[k] > temp) { //如果子結點大于父結點
arr[i] = arr[k]; //把較大的值賦給目前結點
i = k; //!!! i 指向 k,繼續循環比較
} else {
break;//!
}
}
//當for 循環結束後，我們已經将以i 為父結點的樹的最大值，放在了 最頂(局部)
arr[i] = temp;//将temp值放到調整後的位置
}
}
二、赫夫曼樹
2.基本概念
3.建立思路
4.代碼實作
package com.atguigu.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("是空樹，不能周遊~~");
}
}
// 建立赫夫曼樹的方法
/**
*
* @param arr 需要建立成哈夫曼樹的數組
* @return 建立好後的赫夫曼樹的root結點
*/
public static Node createHuffmanTree(int[] arr) {
// 第一步為了操作友善
// 1. 周遊 arr 數組
// 2. 将arr的每個元素構成成一個Node
// 3. 将Node 放入到ArrayList中
List<Node> nodes = new ArrayList<Node>();
for (int value : arr) {
nodes.add(new Node(value));
}
//我們處理的過程是一個循環的過程
while(nodes.size() > 1) {
//排序 從小到大
Collections.sort(nodes);
System.out.println("nodes =" + nodes);
//取出根節點權值最小的兩顆二叉樹
//(1) 取出權值最小的結點（二叉樹）
Node leftNode = nodes.get(0);
//(2) 取出權值第二小的結點（二叉樹）
Node rightNode = nodes.get(1);
//(3)建構一顆新的二叉樹
Node parent = new Node(leftNode.value + rightNode.value);
parent.left = leftNode;
parent.right = rightNode;
//(4)從ArrayList删除處理過的二叉樹
nodes.remove(leftNode);
nodes.remove(rightNode);
//(5)将parent加入到nodes
nodes.add(parent);
}
//傳回哈夫曼樹的root結點
return nodes.get(0);
}
}
// 建立結點類
// 為了讓Node 對象持續排序Collections集合排序
// 讓Node 實作Comparable接口
class Node implements Comparable<Node> {
int value; // 結點權值
char c; //字元
Node left; // 指向左子結點
Node right; // 指向右子結點
//寫一個前序周遊
public void preOrder() {
System.out.println(this);
if(this.left != null) {
this.left.preOrder();
}
if(this.right != null) {
this.right.preOrder();
}
}
public Node(int value) {
this.value = value;
}
@Override
public String toString() {
return "Node [value=" + value + "]";
}
@Override
public int compareTo(Node o) {
// TODO Auto-generated method stub
// 表示從小到大排序
return this.value - o.value;
}
}
三、赫夫曼編碼
2.原理
3.資料壓縮
4.檔案壓縮
package com.atguigu.huffmancode;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.InputStream;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.OutputStream;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class HuffmanCode {
public static void main(String[] args) {
//測試壓縮檔案
// String srcFile = "d://Uninstall.xml";
// String dstFile = "d://Uninstall.zip";
//
// zipFile(srcFile, dstFile);
// System.out.println("壓縮檔案ok~~");
//測試解壓檔案
String zipFile = "d://Uninstall.zip";
String dstFile = "d://Uninstall2.xml";
unZipFile(zipFile, dstFile);
System.out.println("解壓成功!");
/*
String content = "i like like like java do you like a java";
byte[] contentBytes = content.getBytes();
System.out.println(contentBytes.length); //40
byte[] huffmanCodesBytes= huffmanZip(contentBytes);
System.out.println("壓縮後的結果是:" + Arrays.toString(huffmanCodesBytes) + " 長度= " + huffmanCodesBytes.length);
//測試一把byteToBitString方法
//System.out.println(byteToBitString((byte)1));
byte[] sourceBytes = decode(huffmanCodes, huffmanCodesBytes);
System.out.println("原來的字元串=" + new String(sourceBytes)); // "i like like like java do you like a java"
*/
//如何将 資料進行解壓(解碼)
//分步過程
/*
List<Node> nodes = getNodes(contentBytes);
System.out.println("nodes=" + nodes);
//測試一把，建立的赫夫曼樹
System.out.println("赫夫曼樹");
Node huffmanTreeRoot = createHuffmanTree(nodes);
System.out.println("前序周遊");
huffmanTreeRoot.preOrder();
//測試一把是否生成了對應的赫夫曼編碼
Map<Byte, String> huffmanCodes = getCodes(huffmanTreeRoot);
System.out.println("~生成的赫夫曼編碼表= " + huffmanCodes);
//測試
byte[] huffmanCodeBytes = zip(contentBytes, huffmanCodes);
System.out.println("huffmanCodeBytes=" + Arrays.toString(huffmanCodeBytes));//17
//發送huffmanCodeBytes 數組 */
}
//編寫一個方法，完成對壓縮檔案的解壓
/**
*
* @param zipFile 準備解壓的檔案
* @param dstFile 将檔案解壓到哪個路徑
*/
public static void unZipFile(String zipFile, String dstFile) {
//定義檔案輸入流
InputStream is = null;
//定義一個對象輸入流
ObjectInputStream ois = null;
//定義檔案的輸出流
OutputStream os = null;
try {
//建立檔案輸入流
is = new FileInputStream(zipFile);
//建立一個和 is關聯的對象輸入流
ois = new ObjectInputStream(is);
//讀取byte數組 huffmanBytes
byte[] huffmanBytes = (byte[])ois.readObject();
//讀取赫夫曼編碼表
Map<Byte,String> huffmanCodes = (Map<Byte,String>)ois.readObject();
//解碼
byte[] bytes = decode(huffmanCodes, huffmanBytes);
//将bytes 數組寫入到目标檔案
os = new FileOutputStream(dstFile);
//寫資料到 dstFile 檔案
os.write(bytes);
} catch (Exception e) {
// TODO: handle exception
System.out.println(e.getMessage());
} finally {
try {
os.close();
ois.close();
is.close();
} catch (Exception e2) {
// TODO: handle exception
System.out.println(e2.getMessage());
}
}
}
//編寫方法，将一個檔案進行壓縮
/**
*
* @param srcFile 你傳入的希望壓縮的檔案的全路徑
* @param dstFile 我們壓縮後将壓縮檔案放到哪個目錄
*/
public static void zipFile(String srcFile, String dstFile) {
//建立輸出流
OutputStream os = null;
ObjectOutputStream oos = null;
//建立檔案的輸入流
FileInputStream is = null;
try {
//建立檔案的輸入流
is = new FileInputStream(srcFile);
//建立一個和源檔案大小一樣的byte[]
byte[] b = new byte[is.available()];
//讀取檔案
is.read(b);
//直接對源檔案壓縮
byte[] huffmanBytes = huffmanZip(b);
//建立檔案的輸出流, 存放壓縮檔案
os = new FileOutputStream(dstFile);
//建立一個和檔案輸出流關聯的ObjectOutputStream
oos = new ObjectOutputStream(os);
//把 赫夫曼編碼後的位元組數組寫入壓縮檔案
oos.writeObject(huffmanBytes); //我們是把
//這裡我們以對象流的方式寫入 赫夫曼編碼，是為了以後我們恢複源檔案時使用
//注意一定要把赫夫曼編碼 寫入壓縮檔案
oos.writeObject(huffmanCodes);
}catch (Exception e) {
// TODO: handle exception
System.out.println(e.getMessage());
}finally {
try {
is.close();
oos.close();
os.close();
}catch (Exception e) {
// TODO: handle exception
System.out.println(e.getMessage());
}
}
}
//完成資料的解壓
//思路
//1. 将huffmanCodeBytes [-88, -65, -56, -65, -56, -65, -55, 77, -57, 6, -24, -14, -117, -4, -60, -90, 28]
// 重寫先轉成 赫夫曼編碼對應的二進制的字元串 "1010100010111..."
//2. 赫夫曼編碼對應的二進制的字元串 "1010100010111..." =》 對照 赫夫曼編碼 =》 "i like like like java do you like a java"
//編寫一個方法，完成對壓縮資料的解碼
/**
*
* @param huffmanCodes 赫夫曼編碼表 map
* @param huffmanBytes 赫夫曼編碼得到的位元組數組
* @return 就是原來的字元串對應的數組
*/
private static byte[] decode(Map<Byte,String> huffmanCodes, byte[] huffmanBytes) {
//1. 先得到 huffmanBytes 對應的 二進制的字元串 ， 形式 1010100010111...
StringBuilder stringBuilder = new StringBuilder();
//将byte數組轉成二進制的字元串
for(int i = 0; i < huffmanBytes.length; i++) {
byte b = huffmanBytes[i];
//判斷是不是最後一個位元組
boolean flag = (i == huffmanBytes.length - 1);
stringBuilder.append(byteToBitString(!flag, b));
}
//把字元串安裝指定的赫夫曼編碼進行解碼
//把赫夫曼編碼表進行調換，因為反向查詢 a->100 100->a
Map<String, Byte> map = new HashMap<String,Byte>();
for(Map.Entry<Byte, String> entry: huffmanCodes.entrySet()) {
map.put(entry.getValue(), entry.getKey());
}
//建立要給集合，存放byte
List<Byte> list = new ArrayList<>();
//i 可以了解成就是索引,掃描 stringBuilder
for(int i = 0; i < stringBuilder.length(); ) {
int count = 1; // 小的計數器
boolean flag = true;
Byte b = null;
while(flag) {
//1010100010111...
//遞增的取出 key 1
String key = stringBuilder.substring(i, i+count);//i 不動，讓count移動，指定比對到一個字元
b = map.get(key);
if(b == null) {//說明沒有比對到
count++;
}else {
//比對到
flag = false;
}
}
list.add(b);
i += count;//i 直接移動到 count
}
//當for循環結束後，我們list中就存放了所有的字元 "i like like like java do you like a java"
//把list 中的資料放入到byte[] 并傳回
byte b[] = new byte[list.size()];
for(int i = 0;i < b.length; i++) {
b[i] = list.get(i);
}
return b;
}
/**
* 将一個byte 轉成一個二進制的字元串, 如果看不懂，可以參考我講的Java基礎 二進制的原碼，反碼，補碼
* @param b 傳入的 byte
* @param flag 标志是否需要補高位如果是true ，表示需要補高位，如果是false表示不補, 如果是最後一個位元組，無需補高位
* @return 是該b 對應的二進制的字元串，（注意是按補碼傳回）
*/
private static String byteToBitString(boolean flag, byte b) {
//使用變量儲存 b
int temp = b; //将 b 轉成 int
//如果是正數我們還存在補高位
if(flag) {
temp |= 256; //按位與 256 1 0000 0000 | 0000 0001 => 1 0000 0001
}
String str = Integer.toBinaryString(temp); //傳回的是temp對應的二進制的補碼
if(flag) {
return str.substring(str.length() - 8);
} else {
return str;
}
}
//使用一個方法，将前面的方法封裝起來，便于我們的調用.
/**
*
* @param bytes 原始的字元串對應的位元組數組
* @return 是經過 赫夫曼編碼處理後的位元組數組(壓縮後的數組)
*/
private static byte[] huffmanZip(byte[] bytes) {
List<Node> nodes = getNodes(bytes);
//根據 nodes 建立的赫夫曼樹
Node huffmanTreeRoot = createHuffmanTree(nodes);
//對應的赫夫曼編碼(根據 赫夫曼樹)
Map<Byte, String> huffmanCodes = getCodes(huffmanTreeRoot);
//根據生成的赫夫曼編碼，壓縮得到壓縮後的赫夫曼編碼位元組數組
byte[] huffmanCodeBytes = zip(bytes, huffmanCodes);
return huffmanCodeBytes;
}
//編寫一個方法，将字元串對應的byte[] 數組，通過生成的赫夫曼編碼表，傳回一個赫夫曼編碼 壓縮後的byte[]
/**
*
* @param bytes 這時原始的字元串對應的 byte[]
* @param huffmanCodes 生成的赫夫曼編碼map
* @return 傳回赫夫曼編碼處理後的 byte[]
* 舉例： String content = "i like like like java do you like a java"; =》 byte[] contentBytes = content.getBytes();
* 傳回的是 字元串 "1010100010111111110010001011111111001000101111111100100101001101110001110000011011101000111100101000101111111100110001001010011011100"
* => 對應的 byte[] huffmanCodeBytes ，即 8位對應一個 byte,放入到 huffmanCodeBytes
* huffmanCodeBytes[0] = 10101000(補碼) => byte [推導 10101000=> 10101000 - 1 => 10100111(反碼)=> 11011000= -88 ]
* huffmanCodeBytes[1] = -88
*/
private static byte[] zip(byte[] bytes, Map<Byte, String> huffmanCodes) {
//1.利用 huffmanCodes 将 bytes 轉成 赫夫曼編碼對應的字元串
StringBuilder stringBuilder = new StringBuilder();
//周遊bytes 數組
for(byte b: bytes) {
stringBuilder.append(huffmanCodes.get(b));
}
//System.out.println("測試 stringBuilder~~~=" + stringBuilder.toString());
//将 "1010100010111111110..." 轉成 byte[]
//統計傳回 byte[] huffmanCodeBytes 長度
//一句話 int len = (stringBuilder.length() + 7) / 8;
int len;
if(stringBuilder.length() % 8 == 0) {
len = stringBuilder.length() / 8;
} else {
len = stringBuilder.length() / 8 + 1;
}
//建立 存儲壓縮後的 byte數組
byte[] huffmanCodeBytes = new byte[len];
int index = 0;//記錄是第幾個byte
for (int i = 0; i < stringBuilder.length(); i += 8) { //因為是每8位對應一個byte,是以步長 +8
String strByte;
if(i+8 > stringBuilder.length()) {//不夠8位
strByte = stringBuilder.substring(i);
}else{
strByte = stringBuilder.substring(i, i + 8);
}
//将strByte 轉成一個byte,放入到 huffmanCodeBytes
huffmanCodeBytes[index] = (byte)Integer.parseInt(strByte, 2);
index++;
}
return huffmanCodeBytes;
}
//生成赫夫曼樹對應的赫夫曼編碼
//思路:
//1. 将赫夫曼編碼表存放在 Map<Byte,String> 形式
// 生成的赫夫曼編碼表{32=01, 97=100, 100=11000, 117=11001, 101=1110, 118=11011, 105=101, 121=11010, 106=0010, 107=1111, 108=000, 111=0011}
static Map<Byte, String> huffmanCodes = new HashMap<Byte,String>();
//2. 在生成赫夫曼編碼表示，需要去拼接路徑, 定義一個StringBuilder 存儲某個葉子結點的路徑
static StringBuilder stringBuilder = new StringBuilder();
//為了調用友善，我們重載 getCodes
private static Map<Byte, String> getCodes(Node root) {
if(root == null) {
return null;
}
//處理root的左子樹
getCodes(root.left, "0", stringBuilder);
//處理root的右子樹
getCodes(root.right, "1", stringBuilder);
return huffmanCodes;
}
/**
* 功能：将傳入的node結點的所有葉子結點的赫夫曼編碼得到，并放入到huffmanCodes集合
* @param node 傳入結點
* @param code 路徑： 左子結點是 0, 右子結點 1
* @param stringBuilder 用于拼接路徑
*/
private static void getCodes(Node node, String code, StringBuilder stringBuilder) {
StringBuilder stringBuilder2 = new StringBuilder(stringBuilder);
//将code 加入到 stringBuilder2
stringBuilder2.append(code);
if(node != null) { //如果node == null不處理
//判斷目前node 是葉子結點還是非葉子結點
if(node.data == null) { //非葉子結點
//遞歸處理
//向左遞歸
getCodes(node.left, "0", stringBuilder2);
//向右遞歸
getCodes(node.right, "1", stringBuilder2);
} else { //說明是一個葉子結點
//就表示找到某個葉子結點的最後
huffmanCodes.put(node.data, stringBuilder2.toString());
}
}
}
//前序周遊的方法
private static void preOrder(Node root) {
if(root != null) {
root.preOrder();
}else {
System.out.println("赫夫曼樹為空");
}
}
/**
*
* @param bytes 接收位元組數組
* @return 傳回的就是 List 形式 [Node[date=97 ,weight = 5], Node[]date=32,weight = 9]......],
*/
private static List<Node> getNodes(byte[] bytes) {
//1建立一個ArrayList
ArrayList<Node> nodes = new ArrayList<Node>();
//周遊 bytes , 統計 每一個byte出現的次數->map[key,value]
Map<Byte, Integer> counts = new HashMap<>();
for (byte b : bytes) {
Integer count = counts.get(b);
if (count == null) { // Map還沒有這個字元資料,第一次
counts.put(b, 1);
} else {
counts.put(b, count + 1);
}
}
//把每一個鍵值對轉成一個Node 對象，并加入到nodes集合
//周遊map
for(Map.Entry<Byte, Integer> entry: counts.entrySet()) {
nodes.add(new Node(entry.getKey(), entry.getValue()));
}
return nodes;
}
//可以通過List 建立對應的赫夫曼樹
private static Node createHuffmanTree(List<Node> nodes) {
while(nodes.size() > 1) {
//排序, 從小到大
Collections.sort(nodes);
//取出第一顆最小的二叉樹
Node leftNode = nodes.get(0);
//取出第二顆最小的二叉樹
Node rightNode = nodes.get(1);
//建立一顆新的二叉樹,它的根節點 沒有data, 隻有權值
Node parent = new Node(null, leftNode.weight + rightNode.weight);
parent.left = leftNode;
parent.right = rightNode;
//将已經處理的兩顆二叉樹從nodes删除
nodes.remove(leftNode);
nodes.remove(rightNode);
//将新的二叉樹，加入到nodes
nodes.add(parent);
}
//nodes 最後的結點，就是赫夫曼樹的根結點
return nodes.get(0);
}
}
//建立Node ,待資料和權值
class Node implements Comparable<Node> {
Byte data; // 存放資料(字元)本身，比如'a' => 97 ' ' => 32
int weight; //權值, 表示字元出現的次數
Node left;//
Node right;
public Node(Byte data, int weight) {
this.data = data;
this.weight = weight;
}
@Override
public int compareTo(Node o) {
// 從小到大排序
return this.weight - o.weight;
}
public String toString() {
return "Node [data = " + data + " weight=" + weight + "]";
}
//前序周遊
public void preOrder() {
System.out.println(this);
if(this.left != null) {
this.left.preOrder();
}
if(this.right != null) {
this.right.preOrder();
}
}
}
四、二叉排序樹
1.需求
2.解決方案
3.二叉排序樹介紹
4.二叉排序樹建立和周遊
5.二叉排序樹的删除
package com.atguigu.binarysorttree;
public class BinarySortTreeDemo {
public static void main(String[] args) {
int[] arr = {7, 3, 10, 12, 5, 1, 9, 2};
BinarySortTree binarySortTree = new BinarySortTree();
//循環的添加結點到二叉排序樹
for(int i = 0; i< arr.length; i++) {
binarySortTree.add(new Node(arr[i]));
}
//中序周遊二叉排序樹
System.out.println("中序周遊二叉排序樹~");
binarySortTree.infixOrder(); // 1, 3, 5, 7, 9, 10, 12
//測試一下删除葉子結點
binarySortTree.delNode(12);
binarySortTree.delNode(5);
binarySortTree.delNode(10);
binarySortTree.delNode(2);
binarySortTree.delNode(3);
binarySortTree.delNode(9);
binarySortTree.delNode(1);
binarySortTree.delNode(7);
System.out.println("root=" + binarySortTree.getRoot());
System.out.println("删除結點後");
binarySortTree.infixOrder();
}
}
//建立二叉排序樹
class BinarySortTree {
private Node root;
public Node getRoot() {
return root;
}
//查找要删除的結點
public Node search(int value) {
if(root == null) {
return null;
} else {
return root.search(value);
}
}
//查找父結點
public Node searchParent(int value) {
if(root == null) {
return null;
} else {
return root.searchParent(value);
}
}
//編寫方法:
//1. 傳回的 以node 為根結點的二叉排序樹的最小結點的值
//2. 删除node 為根結點的二叉排序樹的最小結點
/**
*
* @param node 傳入的結點(當做二叉排序樹的根結點)
* @return 傳回的 以node 為根結點的二叉排序樹的最小結點的值
*/
public int delRightTreeMin(Node node) {
Node target = node;
//循環的查找左子節點，就會找到最小值
while(target.left != null) {
target = target.left;
}
//這時 target就指向了最小結點
//删除最小結點
delNode(target.value);
return target.value;
}
//删除結點
public void delNode(int value) {
if(root == null) {
return;
}else {
//1.需求先去找到要删除的結點 targetNode
Node targetNode = search(value);
//如果沒有找到要删除的結點
if(targetNode == null) {
return;
}
//如果我們發現目前這顆二叉排序樹隻有一個結點
if(root.left == null && root.right == null) {
root = null;
return;
}
//去找到targetNode的父結點
Node parent = searchParent(value);
//如果要删除的結點是葉子結點
if(targetNode.left == null && targetNode.right == null) {
//判斷targetNode 是父結點的左子結點，還是右子結點
if(parent.left != null && parent.left.value == value) { //是左子結點
parent.left = null;
} else if (parent.right != null && parent.right.value == value) {//是由子結點
parent.right = null;
}
} else if (targetNode.left != null && targetNode.right != null) { //删除有兩顆子樹的節點
int minVal = delRightTreeMin(targetNode.right);
targetNode.value = minVal;
} else { // 删除隻有一顆子樹的結點
//如果要删除的結點有左子結點
if(targetNode.left != null) {
if(parent != null) {
//如果 targetNode 是 parent 的左子結點
if(parent.left.value == value) {
parent.left = targetNode.left;
} else { // targetNode 是 parent 的右子結點
parent.right = targetNode.left;
}
} else {
root = targetNode.left;
}
} else { //如果要删除的結點有右子結點
if(parent != null) {
//如果 targetNode 是 parent 的左子結點
if(parent.left.value == value) {
parent.left = targetNode.right;
} else { //如果 targetNode 是 parent 的右子結點
parent.right = targetNode.right;
}
} else {
root = targetNode.right;
}
}
}
}
}
//添加結點的方法
public void add(Node node) {
if(root == null) {
root = node;//如果root為空則直接讓root指向node
} else {
root.add(node);
}
}
//中序周遊
public void infixOrder() {
if(root != null) {
root.infixOrder();
} else {
System.out.println("二叉排序樹為空，不能周遊");
}
}
}
//建立Node結點
class Node {
int value;
Node left;
Node right;
public Node(int value) {
this.value = value;
}
//查找要删除的結點
/**
*
* @param value 希望删除的結點的值
* @return 如果找到傳回該結點，否則傳回null
*/
public Node search(int value) {
if(value == this.value) { //找到就是該結點
return this;
} else if(value < this.value) {//如果查找的值小于目前結點，向左子樹遞歸查找
//如果左子結點為空
if(this.left == null) {
return null;
}
return this.left.search(value);
} else { //如果查找的值不小于目前結點，向右子樹遞歸查找
if(this.right == null) {
return null;
}
return this.right.search(value);
}
}
//查找要删除結點的父結點
/**
*
* @param value 要找到的結點的值
* @return 傳回的是要删除的結點的父結點，如果沒有就傳回null
*/
public Node searchParent(int value) {
//如果目前結點就是要删除的結點的父結點，就傳回
if((this.left != null && this.left.value == value) ||
(this.right != null && this.right.value == value)) {
return this;
} else {
//如果查找的值小于目前結點的值, 并且目前結點的左子結點不為空
if(value < this.value && this.left != null) {
return this.left.searchParent(value); //向左子樹遞歸查找
} else if (value >= this.value && this.right != null) {
return this.right.searchParent(value); //向右子樹遞歸查找
} else {
return null; // 沒有找到父結點
}
}
}
@Override
public String toString() {
return "Node [value=" + value + "]";
}
//添加結點的方法
//遞歸的形式添加結點，注意需要滿足二叉排序樹的要求
public void add(Node node) {
if(node == null) {
return;
}
//判斷傳入的結點的值，和目前子樹的根結點的值關系
if(node.value < this.value) {
//如果目前結點左子結點為null
if(this.left == null) {
this.left = node;
} else {
//遞歸的向左子樹添加
this.left.add(node);
}
} else { //添加的結點的值大于 目前結點的值
if(this.right == null) {
this.right = node;
} else {
//遞歸的向右子樹添加
this.right.add(node);
}
}
}
//中序周遊
public void infixOrder() {
if(this.left != null) {
this.left.infixOrder();
}
System.out.println(this);
if(this.right != null) {
this.right.infixOrder();
}
}
}
五、平衡二叉樹
1.二叉排序樹可能存在的問題
2.基本介紹
3.左旋轉
4.右旋轉
5.雙旋轉
package com.atguigu.avl;
public class AVLTreeDemo {
public static void main(String[] args) {
//int[] arr = {4,3,6,5,7,8};
//int[] arr = { 10, 12, 8, 9, 7, 6 };
int[] arr = { 10, 11, 7, 6, 8, 9 };
//建立一個 AVLTree對象
AVLTree avlTree = new AVLTree();
//添加結點
for(int i=0; i < arr.length; i++) {
avlTree.add(new Node(arr[i]));
}
//周遊
System.out.println("中序周遊");
avlTree.infixOrder();
System.out.println("在平衡處理~~");
System.out.println("樹的高度=" + avlTree.getRoot().height()); //3
System.out.println("樹的左子樹高度=" + avlTree.getRoot().leftHeight()); // 2
System.out.println("樹的右子樹高度=" + avlTree.getRoot().rightHeight()); // 2
System.out.println("目前的根結點=" + avlTree.getRoot());//8
}
}
// 建立AVLTree
class AVLTree {
private Node root;
public Node getRoot() {
return root;
}
// 查找要删除的結點
public Node search(int value) {
if (root == null) {
return null;
} else {
return root.search(value);
}
}
// 查找父結點
public Node searchParent(int value) {
if (root == null) {
return null;
} else {
return root.searchParent(value);
}
}
// 編寫方法:
// 1. 傳回的 以node 為根結點的二叉排序樹的最小結點的值
// 2. 删除node 為根結點的二叉排序樹的最小結點
/**
*
* @param node
* 傳入的結點(當做二叉排序樹的根結點)
* @return 傳回的 以node 為根結點的二叉排序樹的最小結點的值
*/
public int delRightTreeMin(Node node) {
Node target = node;
// 循環的查找左子節點，就會找到最小值
while (target.left != null) {
target = target.left;
}
// 這時 target就指向了最小結點
// 删除最小結點
delNode(target.value);
return target.value;
}
// 删除結點
public void delNode(int value) {
if (root == null) {
return;
} else {
// 1.需求先去找到要删除的結點 targetNode
Node targetNode = search(value);
// 如果沒有找到要删除的結點
if (targetNode == null) {
return;
}
// 如果我們發現目前這顆二叉排序樹隻有一個結點
if (root.left == null && root.right == null) {
root = null;
return;
}
// 去找到targetNode的父結點
Node parent = searchParent(value);
// 如果要删除的結點是葉子結點
if (targetNode.left == null && targetNode.right == null) {
// 判斷targetNode 是父結點的左子結點，還是右子結點
if (parent.left != null && parent.left.value == value) { // 是左子結點
parent.left = null;
} else if (parent.right != null && parent.right.value == value) {// 是由子結點
parent.right = null;
}
} else if (targetNode.left != null && targetNode.right != null) { // 删除有兩顆子樹的節點
int minVal = delRightTreeMin(targetNode.right);
targetNode.value = minVal;
} else { // 删除隻有一顆子樹的結點
// 如果要删除的結點有左子結點
if (targetNode.left != null) {
if (parent != null) {
// 如果 targetNode 是 parent 的左子結點
if (parent.left.value == value) {
parent.left = targetNode.left;
} else { // targetNode 是 parent 的右子結點
parent.right = targetNode.left;
}
} else {
root = targetNode.left;
}
} else { // 如果要删除的結點有右子結點
if (parent != null) {
// 如果 targetNode 是 parent 的左子結點
if (parent.left.value == value) {
parent.left = targetNode.right;
} else { // 如果 targetNode 是 parent 的右子結點
parent.right = targetNode.right;
}
} else {
root = targetNode.right;
}
}
}
}
}
// 添加結點的方法
public void add(Node node) {
if (root == null) {
root = node;// 如果root為空則直接讓root指向node
} else {
root.add(node);
}
}
// 中序周遊
public void infixOrder() {
if (root != null) {
root.infixOrder();
} else {
System.out.println("二叉排序樹為空，不能周遊");
}
}
}
// 建立Node結點
class Node {
int value;
Node left;
Node right;
public Node(int value) {
this.value = value;
}
// 傳回左子樹的高度
public int leftHeight() {
if (left == null) {
return 0;
}
return left.height();
}
// 傳回右子樹的高度
public int rightHeight() {
if (right == null) {
return 0;
}
return right.height();
}
// 傳回 以該結點為根結點的樹的高度
public int height() {
return Math.max(left == null ? 0 : left.height(), right == null ? 0 : right.height()) + 1;
}
//左旋轉方法
private void leftRotate() {
//建立新的結點，以目前根結點的值
Node newNode = new Node(value);
//把新的結點的左子樹設定成目前結點的左子樹
newNode.left = left;
//把新的結點的右子樹設定成帶你過去結點的右子樹的左子樹
newNode.right = right.left;
//把目前結點的值替換成右子結點的值
value = right.value;
//把目前結點的右子樹設定成目前結點右子樹的右子樹
right = right.right;
//把目前結點的左子樹(左子結點)設定成新的結點
left = newNode;
}
//右旋轉
private void rightRotate() {
Node newNode = new Node(value);
newNode.right = right;
newNode.left = left.right;
value = left.value;
left = left.left;
right = newNode;
}
// 查找要删除的結點
/**
*
* @param value
* 希望删除的結點的值
* @return 如果找到傳回該結點，否則傳回null
*/
public Node search(int value) {
if (value == this.value) { // 找到就是該結點
return this;
} else if (value < this.value) {// 如果查找的值小于目前結點，向左子樹遞歸查找
// 如果左子結點為空
if (this.left == null) {
return null;
}
return this.left.search(value);
} else { // 如果查找的值不小于目前結點，向右子樹遞歸查找
if (this.right == null) {
return null;
}
return this.right.search(value);
}
}
// 查找要删除結點的父結點
/**
*
* @param value
* 要找到的結點的值
* @return 傳回的是要删除的結點的父結點，如果沒有就傳回null
*/
public Node searchParent(int value) {
// 如果目前結點就是要删除的結點的父結點，就傳回
if ((this.left != null && this.left.value == value) || (this.right != null && this.right.value == value)) {
return this;
} else {
// 如果查找的值小于目前結點的值, 并且目前結點的左子結點不為空
if (value < this.value && this.left != null) {
return this.left.searchParent(value); // 向左子樹遞歸查找
} else if (value >= this.value && this.right != null) {
return this.right.searchParent(value); // 向右子樹遞歸查找
} else {
return null; // 沒有找到父結點
}
}
}
@Override
public String toString() {
return "Node [value=" + value + "]";
}
// 添加結點的方法
// 遞歸的形式添加結點，注意需要滿足二叉排序樹的要求
public void add(Node node) {
if (node == null) {
return;
}
// 判斷傳入的結點的值，和目前子樹的根結點的值關系
if (node.value < this.value) {
// 如果目前結點左子結點為null
if (this.left == null) {
this.left = node;
} else {
// 遞歸的向左子樹添加
this.left.add(node);
}
} else { // 添加的結點的值大于 目前結點的值
if (this.right == null) {
this.right = node;
} else {
// 遞歸的向右子樹添加
this.right.add(node);
}
}
//當添加完一個結點後，如果: (右子樹的高度-左子樹的高度) > 1 , 左旋轉
if(rightHeight() - leftHeight() > 1) {
//如果它的右子樹的左子樹的高度大于它的右子樹的右子樹的高度
if(right != null && right.leftHeight() > right.rightHeight()) {
//先對右子結點進行右旋轉
right.rightRotate();
//然後在對目前結點進行左旋轉
leftRotate(); //左旋轉..
} else {
//直接進行左旋轉即可
leftRotate();
}
return ; //必須要!!!
}
//當添加完一個結點後，如果 (左子樹的高度 - 右子樹的高度) > 1, 右旋轉
if(leftHeight() - rightHeight() > 1) {
//如果它的左子樹的右子樹高度大于它的左子樹的高度
if(left != null && left.rightHeight() > left.leftHeight()) {
//先對目前結點的左結點(左子樹)->左旋轉
left.leftRotate();
//再對目前結點進行右旋轉
rightRotate();
} else {
//直接進行右旋轉即可
rightRotate();
}
}
}
// 中序周遊
public void infixOrder() {
if (this.left != null) {
this.left.infixOrder();
}
System.out.println(this);
if (this.right != null) {
this.right.infixOrder();
}
}
}
六、多路查找樹
1.二叉樹的問題
2.多叉樹
3.B樹的基本介紹
4.2-3樹基本介紹
5.2-3樹應用案例
6.其他說明