文章目錄
-
-
- 一、堆排序
-
- 1、堆排序基本介紹
- 2、堆排序基本思想
- 3、堆排序步驟圖解說明
- 4、堆排序代碼實作
- 二、哈夫曼樹
-
- 1、基本介紹
- 2、哈夫曼樹幾個重要概念和舉例說明
- 3、哈夫曼樹建立思路圖解
- 三、二叉排序樹
-
- 1、二叉排序樹介紹
- 2、二叉排序樹建立和周遊
- 3、二叉排序樹的删除
- 4、二叉排序樹删除結點的代碼實作
- 四、平衡二叉樹(AVL樹)
-
- 1、基本介紹
- 2、應用案例 - 單旋轉（左旋轉）
- 3、應用案例 - 單旋轉（右旋轉）
- 4、應用案例 - 雙旋轉
-
一、堆排序
1、堆排序基本介紹
- 堆排序是利用堆這種資料結構而設計的一種排序算法，堆排序是一種選擇排序，它的最壞，最好，平均時間複雜度均為O(nlogn)，它也是不穩定排序。
- 堆是具有以下性質的完全二叉樹：每個結點的值都大于或等于其左右孩子結點的值，稱為大頂堆，注意∶沒有要求結點的左孩子的值和右孩子的值的大小關系。
- 每個結點的值都小于或等于其左右孩子結點的值，稱為小頂堆。
- 大頂堆舉例說明
【樹結構】實際應用 —— 堆排序、哈夫曼樹、二叉排序樹、平衡二叉樹(AVL樹) - 小頂堆舉例說明
【樹結構】實際應用 —— 堆排序、哈夫曼樹、二叉排序樹、平衡二叉樹(AVL樹) - 一般升序采用大頂堆，降序采用小頂堆
2、堆排序基本思想
- 将待排序序列構造成一個大頂堆。
- 此時，整個序列的最大值就是堆頂的根節點。
- 将其與末尾元素進行交換，此時末尾就為最大值。
-
然後将剩餘 n-1 個元素重新構造成一個堆，這樣會得到 n 個元素的次小值。如此反複執行，便能得到一個有序
序列了。
可以看到在建構大頂堆的過程中，元素的個數逐漸減少，最後就得到一個有序序列了。
3、堆排序步驟圖解說明
要求：給你一個數組 { 4, 6, 8, 5, 9 }，要求使用堆排序法，将數組升序排序。
步驟一：構造初始堆。将給定無序序列構造成一個大頂堆(一般升序采用大頂堆，降序采用小頂堆)。
原始的數組 [ 4, 6, 8, 5, 9 ]
- 假設給定無序序列結構如下
【樹結構】實際應用 —— 堆排序、哈夫曼樹、二叉排序樹、平衡二叉樹(AVL樹) - 此時我們從最後一個非葉子結點開始(葉結點自然不用調整，第一個非葉子結點 arr.length/2-1=5/2-1=1，也就是 6 結點），從左至右，從下至上進行調整。
【樹結構】實際應用 —— 堆排序、哈夫曼樹、二叉排序樹、平衡二叉樹(AVL樹) - 找到第二個非葉節點 4，由于 [ 4, 9, 8 ] 中 9 元素最大，4 和 9 交換。
【樹結構】實際應用 —— 堆排序、哈夫曼樹、二叉排序樹、平衡二叉樹(AVL樹) - 這時，交換導緻了子根 [ 4, 5, 6 ] 結構混亂，繼續調整，[ 4, 5, 6 ]中 6 最大，交換 4 和 6。 此時，我們就将一個無序序列構造成了一個大頂堆。
【樹結構】實際應用 —— 堆排序、哈夫曼樹、二叉排序樹、平衡二叉樹(AVL樹)
步驟二：将堆頂元素與末尾元素進行交換，使末尾元素最大。然後繼續調整堆，再将堆頂元素與末尾元素交換，得到第二大元素。如此反複進行交換、重建、交換。
- 将堆頂元素 9 和末尾元素 4 進行交換
【樹結構】實際應用 —— 堆排序、哈夫曼樹、二叉排序樹、平衡二叉樹(AVL樹) - 重新調整結構，使其繼續滿足堆定義
【樹結構】實際應用 —— 堆排序、哈夫曼樹、二叉排序樹、平衡二叉樹(AVL樹) - 再将堆頂元素 8 與末尾元素 5 進行交換，得到第二大元素 8
【樹結構】實際應用 —— 堆排序、哈夫曼樹、二叉排序樹、平衡二叉樹(AVL樹) - 後續過程，繼續進行調整，交換，如此反複進行，最終使得整個序列有序
【樹結構】實際應用 —— 堆排序、哈夫曼樹、二叉排序樹、平衡二叉樹(AVL樹)
簡單總結下堆排序的基本思路：
- 将無序序列建構成一個堆，根據升序降序需求選擇大頂堆或小頂堆;
- 将堆頂元素與末尾元素交換，将最大元素"沉"到數組末端;
- 重新調整結構，使其滿足堆定義，然後繼續交換堆頂元素與目前末尾元素，反複執行調整、交換步驟， 直到整個序列有序。
4、堆排序代碼實作
要求：給一個數組 { 4, 6, 8, 5, 9 }，要求使用堆排序法，将數組升序排序。
說明：堆排序的速度非常快，在我的機器上 8百萬 資料平均 3 秒左右。O(nlogn)
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值放到調整後的位置
}
}
二、哈夫曼樹
1、基本介紹
- 給定 n 個權值作為 n 個葉子結點，構造一棵二叉樹，若該樹的帶權路徑長度(wpl)達到最小，稱這樣的二叉樹為最優二叉樹，也稱為哈夫曼樹(Huffman Tree)，還有的書翻譯為霍夫曼樹。
- 赫夫曼樹是帶權路徑長度最短的樹，權值較大的結點離根較近
2、哈夫曼樹幾個重要概念和舉例說明
- 路徑和路徑長度： 在一棵樹中，從一個結點往下可以達到的孩子或孫子結點之間的通路，稱為路徑。通路中分支的數目稱為路徑長度。若規定根結點的層數為 1，則從根結點到第 L 層結點的路徑長度為 L-1
- 結點的權及帶權路徑長度： 若将樹中結點賦給一個有着某種含義的數值，則這個數值稱為該結點的權
- 結點的帶權路徑長度： 從根結點到該結點之間的路徑長度與該結點的權的乘積
- 樹的帶權路徑長度： 樹的帶權路徑長度規定為所有葉子結點的帶權路徑長度之和，記為WPL(weighted pathlength) ，權值越大的結點離根結點越近的二叉樹才是最優二叉樹。
- WPL最小的就是赫夫曼樹
【樹結構】實際應用 —— 堆排序、哈夫曼樹、二叉排序樹、平衡二叉樹(AVL樹)
3、哈夫曼樹建立思路圖解
給一個數列 { 13, 7, 8, 3, 29, 6, 1}，要求轉成一顆哈夫曼樹。
構成赫夫曼樹的步驟：
- 從小到大進行排序，将每一個資料，每個資料都是一個節點，每個節點可以看成是一顆最簡單的二叉樹
- 取出根節點權值最小的兩顆二叉樹
- 組成一顆新的二叉樹，該新的二叉樹的根節點的權值是前面兩顆二叉樹根節點權值的和
- 再将這顆新的二叉樹，以根節點的權值大小再次排序，不斷重複 1-2-3-4 的步驟，直到數列中，所有的資料都被處理，就得到一顆赫夫曼樹
【樹結構】實際應用 —— 堆排序、哈夫曼樹、二叉排序樹、平衡二叉樹(AVL樹)
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;
}
}
三、二叉排序樹
1、二叉排序樹介紹
二叉排序樹：BST(Binary Sort(Search)Tree)，對于二叉排序樹的任何一個非葉子節點，要求左子節點的值比目前節點的值小，右子節點的值比目前節點的值大。
特别說明：如果有相同的值，可以将該節點放在左子節點或右子節點
在這裡插入圖檔描述
比如資料 ( 7, 3, 10, 12, 5, 1, 9 )，對應的二叉排序樹為：
2、二叉排序樹建立和周遊
一個數組建立成對應的二叉排序樹，并使用中序周遊二叉排序樹，比如：數組為 Array( 7, 3, 10, 12, 5, 1, 9 )，建立成對應的二叉排序樹為∶
3、二叉排序樹的删除
二叉排序樹的删除情況比較複雜，有下面三種情況需要考慮
- 删除葉子節點（比如: 2, 5, 9, 12)
- 删除隻有一顆子樹的節點(比如: 1)
- 删除有兩顆子樹的節點.(比如: 7, 3, 10)
- 操作的思路分析
第一種情況： 删除葉子節點（比如: 2, 5, 9, 12)
思路：
- 需求先去找到要删除的結點 targetNode
- 找到 targetNode 的父結點 parent
- 确定 targetNode 是 parent 的左子結點還是右子結點
-
根據前面的情況來對應删除
左子結點 parent.left = null;
右子結點 parent.right = null;
第二種情況： 删除隻有一顆子樹的節點 比如 1
思路：
- 需求先去找到要删除的結點 targetNode
- 找到 targetNode 的父結點 parent
- 确定 targetNode 的子結點是左子結點還是右子結點
- targetNode 是 parent 的左子結點還是右子結點
-
如果 targetNode 有左子結點
5.1 如果 targetNode 是 parent 的左子結點 parent.left = targetNode.left;
5.2 如果 targetNode 是 parent 的右子結點 parent.right = targetNode.left;
-
如果 targetNode 有右子結點
6.1 如果 targetNode 是 parent 的左子結點 parent.left = targetNode.right;
6.2 如果 targetNode 是 parent 的右子結點 parent.right = targetNode.right;
第三種情況： 删除有兩顆子樹的節點 (比如: 7, 3, 10 )
思路：
- 需求先去找到要删除的結點 targetNode
- 找到 targetNode 的父結點 parent
- 從 targetNode 的右子樹找到最小的結點
- 用一個臨時變量，将最小結點的值儲存
- 删除該最小結點
- targetNode.value = temp
4、二叉排序樹删除結點的代碼實作
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();
}
}
}
四、平衡二叉樹(AVL樹)
1、基本介紹
- 平衡二叉樹也叫平衡二叉搜尋樹(Self-balancing binary search tree)又被稱為 AVL 樹，可以保證查詢效率較高。
- 具有以下特點：它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過 1，并且左右兩個子樹都是一棵平衡二叉樹。平衡二叉樹的常用實作方法有紅黑樹、AVL、替罪羊樹、Treap、伸展樹等。
- 舉例說明
【樹結構】實際應用 —— 堆排序、哈夫曼樹、二叉排序樹、平衡二叉樹(AVL樹)
2、應用案例 - 單旋轉（左旋轉）
- 要求：給一個數列，建立出對應的平衡二叉樹，數列 { 4, 3, 6, 5, 7, 8 }
- 思路分析(示意圖)
【樹結構】實際應用 —— 堆排序、哈夫曼樹、二叉排序樹、平衡二叉樹(AVL樹)
//左旋轉方法
private void leftRotate() {
//建立新的結點，以目前根結點的值
Node newNode = new Node(value);
//把新的結點的左子樹設定成目前結點的左子樹
newNode.left = left;
//把新的結點的右子樹設定成帶你過去結點的右子樹的左子樹
newNode.right = right.left;
//把目前結點的值替換成右子結點的值
value = right.value;
//把目前結點的右子樹設定成目前結點右子樹的右子樹
right = right.right;
//把目前結點的左子樹(左子結點)設定成新的結點
left = newNode;
}
3、應用案例 - 單旋轉（右旋轉）
- 要求：給一個數列，建立出對應的平衡二叉樹，數列 { 10, 12, 8, 9, 7, 6 }
- 思路分析(示意圖)
【樹結構】實際應用 —— 堆排序、哈夫曼樹、二叉排序樹、平衡二叉樹(AVL樹)
//右旋轉
private void rightRotate() {
Node newNode = new Node(value);
newNode.right = right;
newNode.left = left.right;
value = left.value;
left = left.left;
right = newNode;
}
4、應用案例 - 雙旋轉
前面的兩個數列，進行單旋轉(即一次旋轉)就可以将非平衡二叉樹轉成平衡二叉樹，但是在某些情況下，單旋轉不能完成平衡二叉樹的轉換。比如數列
int [ ] arr = { 10, 11, 7, 6, 8, 9}; 運作原來的代碼可以看到，并沒有轉成AVL樹。
int [ ] arr = { 2, 1, 6, 5, 7, 3 }; 運作原來的代碼可以看到，并沒有轉成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();
}
}
}