二分搜尋樹
今天七夕，然後我再公司宿舍寫代碼！！！好吧~我承認我酸了，不想進行講解，我就是将今天的事記錄下，而且也不知道咋回事，回來倒頭就睡，可能是算法太耗費腦子了吧，也不知道是因為算法還是情人節鬧的～反正就是特麼蔫吧了一整天，現在的時間是2019年8月7日23:09:19,代碼你們粘過去也運作不了，因為裡面用到了我自己寫的隊列Queue
package com.myTree;
import com.xsh.April_Month23Day_Queue.CommonQueue;
import com.xsh.April_Month23Day_Queue.Queue;
/**
*
* @author lenovo
*
* 二分搜尋樹
*
*/
public class BST<E extends Comparable> {
// Node 節點
private class Node<E extends Comparable>{
// 節點的值
private E value;
// 左子節點
private Node left;
// 右子節點
private Node right;
public Node(E value) {
this.value = value;
this.left = null;
this.right = null;
}
public E getValue() {
return value;
}
public void setValue(E value) {
this.value = value;
}
public Node getLeft() {
return left;
}
public void setLeft(Node left) {
this.left = left;
}
public Node getRight() {
return right;
}
public void setRight(Node right) {
this.right = right;
}
}
// 根節點
private Node root;
// 節點的個數
private int size;
// 預設構造函數
public BST() {
this.root = null;
this.size = 0;
}
// 添加構造節點 ---> 對外暴露方法
public void add(E value) {
// 進一步深化 疊代算法
if (root == null) {
root = new Node(value);
return;
}
add(root,value);
}
// 内部實際實作算法
private void add(Node node,E value) {
// 遞歸終止條件
if (value.compareTo(node.value) < 0 && node.left == null) {
size++;
node.left = new Node(value);
} else if(value.compareTo(node.value) > 0 && node.right == null) {
size++;
node.right = new Node(value);
}
// 遞歸條件
if (value.compareTo(node.value) < 0) {
add(node.left,value);
} else if(value.compareTo(node.value) > 0) {
add(node.right,value);
}
}
// 判斷特定節點的值是否存在 --- 對外暴露方法
public boolean isExist(E value) {
if (root == null) return false;
return isExist(root,value);
}
// 内部真正實作的方法
private boolean isExist(Node node,E value) {
if (value.compareTo(node.value) == 0) {
return true;
} else if (value.compareTo(node.value) < 0 && node.left == null) {
return false;
} else if(value.compareTo(node.value) > 0 && node.right == null) {
return false;
}
if (value.compareTo(node.value) < 0) {
return isExist(node.left,value);
} else{ //(value.compareTo(node.value) > 0)
return isExist(node.right,value);
}
}
// 前序周遊 --- 又稱根序周遊 --- 根左右
public void preOrder() {
if (root == null) throw new IllegalArgumentException("二分搜尋樹為NULL");
preOrder(root);
}
// 内部真正實作 -- 前序周遊
private void preOrder(Node root) {
if (root == null)
return;
System.out.println(root.value);
preOrder(root.left);
preOrder(root.right);
}
// 後序周遊 --- 又稱後根周遊 --- 左右根 --- 對外暴露實作的方法
public void afterOrder() {
if (root == null) throw new IllegalArgumentException("目前二分搜尋樹為NULL");
afterOrder(root);
}
// 内部真正實作 -- 後序周遊
private void afterOrder(Node node) {
if (node == null) return;
afterOrder(node.left);
afterOrder(node.right);
System.out.println(node.value);
}
// 中序周遊 --- 又叫做中根周遊 --- 左根右 --- 對外暴露實作的方法
public void midOrder() {
if (root == null) throw new IllegalArgumentException("二叉樹為NULL");
midOrder(root);
}
// 内部真正實作 -- 中序周遊
private void midOrder(Node node) {
if (node == null) return;
midOrder(node.left);
System.out.println(node.value);
midOrder(node.right);
}
// 查找該二叉樹的最小值 -- 對外暴露的方法
public E min() {
if (root == null) throw new IllegalArgumentException("目前二叉樹為NULL");
Node node = min(root);
return (E) node.value;
}
// 内部真正實作 -- 查找二叉樹的最小值
private Node min(Node node) {
if (node.left == null)
return node;
return min(node.left);
}
// 查找二叉樹的最大值 -- 對外暴露的方法
public E max() {
if (root == null) throw new IllegalArgumentException("目前二叉樹為NULL");
Node node = max(root);
return (E) node.value;
}
// 内部真正實作 -- 查找二叉樹的最大值
private Node max(Node node) {
if(node.right == null) return node;
return max(node.right);
}
// 層序周遊 -- 一層一層來,這個跟前面的操作有很大的差別，這個是廣度優先算法
// bsf --- Breadth First Search 廣度優先算法
public void bfsOrder() {
if(root == null) throw new IllegalArgumentException("目前二叉樹為NULL");
bfsOrder(root);
}
// 層序周遊 -- 一層一層來,這個跟前面的操作有很大的差別，這個是廣度優先算法
// bsf --- Breadth First Search 廣度優先算法
private void bfsOrder(Node node) {
// 建立一個隊列
Queue queue = new CommonQueue();
queue.enqueue(root);
while (queue != null) {
Node curNode = (Node) queue.dequeue();
System.out.print(curNode.value + " ");
if (curNode.left != null)
queue.enqueue(curNode.left);
if (curNode.right != null)
queue.enqueue(curNode.right);
}
}
// 從二分蘇所述中删除最小值所在的節點，傳回最小值
public E removeMin() {
E ret = min();
// BEGIN
root = removeMin(root);
// END
return ret;
}
// 删除以node為根的二分搜尋樹中的最小節點
// 傳回删除節點後新的二分搜尋樹的根
private Node removeMin(Node node) {
if (node.left == null) {
Node rightNode = node.right;
node.right = null;
size--;
return rightNode;
}
// 留存疑問
node.left = removeMin(node.left);
return node;
}
// 從二分搜尋樹中删除最大值所在節點
public E removeMax(){
E ret = max();
// BEGIN
// END
return ret;
}
// 删除掉以node為根的二分搜尋樹中的最大節點
// 傳回删除節點後新的二分搜尋樹的根
private Node removeMax(Node node){
if (node.right == null) {
Node leftNode = node.left;
node.left = null;
size--;
return leftNode;
}
node.right = removeMax(node.right);
return node;
}
// 判斷目前二分搜尋樹是否存在其他元素
public boolean isEmpty() {
return size == 0;
}
// 從二分搜尋樹中删除元素為e的
public void remove(E e) {
root = remove(root,e);
}
// 删除以node為根的二分搜尋樹中值為e的節點，遞歸算法
// 傳回删除節點後新的二分搜尋樹的根
public Node remove(Node node,E e) {
// 目前二分搜尋樹為NULL，是以要删除的元素不存在 --- 傳回null
if (node == null) return null;
// 這裡面需要再紙上看一下過程
if (e.compareTo(node.value) < 0) {
node.left = remove(node.left,e);
return node;
} else if(e.compareTo(node.value) > 0) {
node.right = remove(node.right,e);
return node;
} else { // e == node.e
// 待删除節點左子樹為空的情況
if (node.left == null) {
Node rightNode = node.right;
node.right = null;
size --;
return rightNode;
}
// 待删除節點右子樹為空的情況
if (node.right == null) {
Node leftNode = node.left;
node.left = null;
size --;
return leftNode;
}
// 待删除節點左右子樹均不為空的情況
// 找到比待删除節點大的最小節點，即待删除節點右子樹的組消極诶單
// 用這個節點頂替待删除節點的位置
/* 後繼節點，有大用 */
Node successor = min(node.right);
successor.right = removeMin(node.right);
size++;
successor.left = node.left;
node.left = node.right = null;
size--;
return successor;
}
}
}
睡了睡了，明年的這個節日可不能這個樣子了。
![樹的基本概念(定義、基本術語、性質)[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)