package com.learn.tree.demo2;

import java.util.LinkedList;
import java.util.Queue;

/**
* 二分查找樹BST（也叫二叉查找樹、二叉排序樹）的提出是為了提供查找效率，
* 之所以稱為二分查找樹，因為該二叉樹對應著二分查找算法，查找平均的時間復雜度為o(logn)，所以該數據結構的提出是為了提高查找效率。 定義
* 二分查找樹或者是一棵空樹，或者具有下列性質： 1.若它的左子樹不為空，則左子樹上所有結點的值均小于根結點的值；
* 2.若它的右子樹不為空，則右子樹上所有結點的值均大于根結點的值； 3.它的左右子樹均為二分查找樹。
*
*
* 具體實現:二叉樹的前序遍歷,中序遍歷，后序遍歷，層次遍歷 求二叉樹深度(根到節點-葉子節點最長路徑) 新增節點(沒有該鍵 則新增 有則添加) 刪除節點
*
* 注意:該二叉搜索樹的實現是沒有重復鍵值的
*
*/
public class BinaryTree<Key extends Comparable<Key>, Value> {
private Node root;// 二叉樹的根節點
private int count;// 二叉樹中的節點數

// 二叉樹的實例化 的構造器
public BinaryTree() {
root = null;// 初始化根節點
count = 0;
}

// 判斷該 二叉樹是否有節點
public boolean isEmpty() {
return count == 0;
}

// 該二叉樹的節點數
public int size() {
return count;
}

// 新增二叉樹的節點
public void insert(Key key, Value value) {
root = insert(root, key, value);
}

/**
* 插入節點的內部實現方法 采用遞歸的方法實現 二叉樹的插入操作 返回 新增節點的二叉樹的后根節點(為什么是根節點 注意遞歸后的的遞進，還有回退 )
*
* @param root
* 該二叉樹的根
* @param key
* @param value
*/
private Node insert(Node node, Key key, Value value) {
// 如果根節點的為空 ，則將新增的節點為 作為根節點
if (node == null) {
count++;
return new Node(key, value);
}
if (key.compareTo(node.key) > 0) {
node.right = insert(node.right, key, value);
} else if (key.compareTo(node.key) < 0) {
node.left = insert(node.left, key, value);
} else
node.value = value;
return node;
}

/**
* 獲得最小節點
*
* @param key
*/
public Node getMininum() {
Node node = mininum(root);
return node;
}

/**
* 獲得最小節點內部方法實現(沒有左節點)--->迭代法
*
* @param node
* @param key
* @return
*/
private Node mininum(Node node) {
Node parent = null;
while (node != null) {
parent = node;
node = node.left;
}
return parent;
}

/**
* 獲得最小節點內部方法實現(沒有左節點)-->遞歸法
*
* @param node
* @return
*/
private Node minimumD(Node node) {
if (node.left== null)
return node;
return minimumD(node.left);
}

/**
* 獲得的二叉樹的最大節點
*
* @param key
* @return
*/
public Node getMaxinum() {
Node node = maxinum(root);
return node;
}

/**
* 最大節點的內部實現(沒有右節點)--->迭代法
*
* @param node
* @param key
* @return
*/
private Node maxinum(Node node) {
Node parent = null;
while (node != null) {
parent = node;
node = node.right;
}
return parent;

}

/**
* 最大節點的內部實現(沒有右節點)--->遞歸法
*
* @param node
* @return
*/
private Node maxinumD(Node node) {
if (node.right== null)
return node;
return maxinum(node.right);
}

/**
* 刪除二叉搜索樹的最小節點
*
* @return
*/
public Node removeMin() {
if (root != null)
root = removeMin(root);
return root;
}

/**
* 刪除二叉搜索樹的最小節點(不同的結構體 或者實體類實現方法不同) 這里是單項關聯 過時將父節點的左節點 置為null,與左節點斷開關聯
* 返回刪除節點后新的二分搜索樹的根 ----------------------->遞歸法
*
* @param node
* @return
*/
private Node removeMin(Node node) {
if (node.left == null) {
final Node rightNode = node.right;
node.right = null;// let out gc
count--;
return rightNode;// 如果該節點有右節點，將該節點的 右節點 作為該
// 節點的父節點的左節點(于此同時也斷開了該節點與父節點的聯系)
}
// 遞歸調用左節點(直至左節點為空 刪除該節點)
node.left = removeMin(node.left);
return node;
}

/**
* 刪除二叉搜索樹的最小節點--->迭代法
*
* @param node
*/
private void removeMinNode(Node node) {
Node parentNode = null;
while (node != null) {
parentNode = node;
node = node.left;
}
final Node rightNode = node.right;
node.right = null;// let out gc
parentNode.left = rightNode;
count--;
}

/**
* 刪除二叉搜索樹的最大節點
*
* @return
*/
public Node removeMax() {
if (root != null)
root = removeMax(root);
return root;
}

/**
* 刪除二叉搜索樹的最大節點(不同的結構體 或者實體類實現方法不同) 這里是單項關聯 過時將父節點的右節點 置為null,與右節點斷開關聯
* 返回刪除最大節點后的二叉搜索樹的節點 ----------------------->遞歸法
*
* @param node
* @return
*/
private Node removeMax(Node node) {
if (node.right == null) {
final Node nodeLeft = node.left;
node.left = null;// let out gc
count--;
return nodeLeft;
}
node.right = removeMax(node.right);
return node;
}

/**
* 刪除二叉搜索樹的最大節點
*
* @param node
*/
private void removeMaxNode(Node node) {
Node parentNode = null;
while (node != null) {
parentNode = node;
node = node.right;
}
final Node nodeLeft = node.left;
node.left = null;// let out gc
node.right = nodeLeft;
count--;
}

/**
* 刪除二叉樹的節點 設p指向待刪除的結點，pre指向待刪除結點的父親，則刪除操作視如下情況而定：
* （1）若待刪除的結點是葉子結點，不妨設pre->right=p(即待刪除的結點為其父親結點的右孩子)，則直接刪除p，對應為：pre->right=
* NULL，delete p；
* （2）若待刪除的結點只有左子樹或右子樹，則只需將待刪除結點的父親與左孩子（或右孩子）連接起來，對應為，不妨設pre->right=p,
* 以待刪除結點僅有左子樹的情況為例（右子樹同理），對應為：pre->right=p->left，delete p；
* （3）若待刪除結點左右子樹都有，則執行如下步驟：
* 總體來說，整個線索是：找到右子樹的最小值結點-->連接斷開結點-->對最小值結點的上下文做善后工作。
*
* @param key
*/
public void remove(Key key) {
remove(root, key);
}

/**
* 刪除二叉樹的節點 內部實現 使用遞歸的方法 返回刪除后的二叉樹的根節點--迭代法 返回該節點
*
* @param node
* @param key
* @return
*/
private Node remove(Node node, Key key) {
Node parent = root;
while (node != null) {
if (key.compareTo(node.key) > 0) {
parent = node;
node = node.right;
} else if (key.compareTo(node.key) < 0) {
parent = node;
node = node.left;
} else
break;// 當鍵相等的時候 就查到該節點 此時node就是 要 刪除的節點,與parent 斷開關聯
}
if (node == null)
throw new RuntimeException("沒有該鍵" + key + "對應的節點!");
// 要刪除的左節點左節點不存在
if (node.left == null) {
final Node rihtNode = node.right;
if (node.key.compareTo(parent.key) > 0)
parent.right = rihtNode;
else
parent.left = rihtNode;
node.right = null;
count--;
return node;
}
// 要刪除的右節點不存在(其中左右都為null不用考慮,處理包含在其中)
if (node.right == null) {
final Node leftNode = node.left;
if (node.key.compareTo(parent.key) > 0)
parent.left = leftNode;
else
parent.right = leftNode;
node.left = null;
count--;
return node;
}
// 要刪除的左右節點都存在
if (node.right != null && node.left != null) {
// 找到該替換該節點的節點
Node successor = new Node(mininum(node.right));
successor.right = removeMin(node.right);
if (node.key.compareTo(parent.key) > 0)
parent.right = successor;
else
parent.left = successor;
successor.left = node.left;
node.left = null;// let out gc
node.right = null;// let out gc
return node;
}
return node;
}

/**
* 刪除節點------->遞歸法 返回刪除節點后二叉搜索樹的根節點
*
* @param node
* @param key
* @return
*/
private Node removeNode(Node node, Key key) {
if (node == null)
return node;
if (key.compareTo(node.key) > 0) {
node.right = removeNode(node.right, key);
return node;
} else if (key.compareTo(node.key) < 0) {
node.left = removeNode(node.left, key);
return node;
} else {
if (node.left == null) {
final Node rNode = node.right;
node.right = null;
count--;
return rNode;
}
if (node.right == null) {
final Node lNode = node.left;
node.left = null;
count--;
return lNode;
}
if (node.right != null && node.left != null) {
Node successor = new Node(mininum(node.right));
successor.right = removeMin(node.right);
successor.left = node.left;
node.left = null;
node.right = null;
return successor;
}
return node;
}
}

/**
* 通過鍵 key獲取節點
*
* @param key
* @return
*/
public Node node(Key key) {
Node node = node(root, key);
return node;
}

/**
* 用迭代法實現-通過鍵是獲取節點
*
* @param node
* @param key
* @return
*/
private Node node(Node node, Key key) {
while (node != null) {
if (key.compareTo(node.key) > 0)
node = node.right;
else if (key.compareTo(node.key) < 0)
node = node.left;
else
return node;
}
return null;
}

/**
* 判斷該鍵是否在 二叉搜索樹
*
* @param key
* @return
*/
public boolean contain(Key key) {
return contain(root, key);
}

/**
* 遞歸法
*
* @param node
* @param key
* @return
*/
private boolean contain(Node node, Key key) {
if (node == null)
return false;
if (key.compareTo(node.key) == 0)
return false;
else if (key.compareTo(node.key) > 0)
return contain(node.right, key);
else
return contain(node.left, key);
}

/**
* 前序遍歷(深度遍歷的一種) Traversal
*/
public void preOrder() {
if (root != null)
preOrder(root);
}

/**
* 滿足 根-->左--->右 (遞歸法)
*
* @param node
*/
private void preOrder(Node node) {
if (node != null)
return;
System.out.println("節點鍵的為:" + node.key + " 節點的值為:" + node.value);
preOrder(node.left);
preOrder(node.right);
}

/**
* 中序遍歷(深度遍歷的一種)Traversal 中序遍歷二叉搜索樹 滿足從小到大順序 (排序)
*/
public void inOrder() {
if (root != null)
inOrder(root);
}

/**
* 中序遍歷 --->遞歸法
*
* @param node
*/
private void inOrder(Node node) {
if (node == null)
return;
inOrder(node.left);
System.out.println("節點鍵的為:" + node.key + " 節點的值為:" + node.value);
inOrder(node.right);
}

/**
* 后序遍歷(深度遍歷的一種)Traversal
*/
public void postOrder() {
if (root != null)
postOrder(root);
}

/**
* 中序遍歷 --->遞歸法
*
* @param node
*/
private void postOrder(Node node) {
if (node == null)
return;
postOrder(node.left);
postOrder(node.right);
System.out.println("節點鍵的為:" + node.key + " 節點的值為:" + node.value);
}

/**
* 層序遍歷(廣度優先遍歷)
*
* @param node
*/
public void levelOrder() {
if (root != null)
levelOrder(root);
}

/**
* 利用隊列 (Queue)先進先出
*
* @param node
*/
private void levelOrder(Node node) {
Queue<Node> queue = new LinkedList<Node>();
queue.offer(node);
while (!queue.isEmpty()) {
Node element = queue.poll();
System.out.println("節點鍵的為:" + element.key + " 節點的值為:" + element.value);
if (element.left != null)
queue.offer(element.left);
if (element.right != null)
queue.offer(element.right);
}
}

/**
* 二叉樹的節點用一個內部類來實現
*
* @author caibixiang
*
*/
private class Node {
private Key key;// 鍵 (滿足根節點的鍵小于右節點中所有節點，大于左節點的中所有節點)
private Value value;// 值
private Node left;// 左節點
private Node right;// 又節點

private Node(Key key, Value value) {
this.key = key;
this.value = value;
this.left = null;
this.right = null;
}

private Node(Node node) {
this.key = node.key;
this.value = node.value;
this.left = node.left;
this.right = node.right;
}

}

public static void main(String[] args) {
int N = 100;
// 創建一個數組,包含[0....N]的所有的元素
Integer[] arr = new Integer[N];
for (int i = 0; i < N; i++)
arr[i] = new Integer(i);
// 打亂數組順序
for (int i = 0; i < N; i++) {
int pos = (int) (Math.random() * (i + 1));
Integer t = arr[pos];
arr[pos] = arr[i];
arr[i] = t;
}
// 由于我們實現的二分搜索樹不是平衡二叉樹
// 所以如果按照順序插入一組數據，我們的二分搜索樹會退化成為一個鏈表
// 平橫二叉樹的實現下一節來實現(avl樹)
BinaryTree<Integer, String> bst = new BinaryTree<Integer, String>();
for (int i = 0; i < N; i++)
bst.insert(new Integer(arr[i]), Integer.toString(arr[i]));
bst.inOrder();// 升序排列
bst.remove(5);
bst.remove(7);
bst.remove(71);
bst.remove(23);
bst.remove(34);
bst.remove(56);
System.out.println(bst.size());
bst.inOrder();// 升序排列

}

}

轉載于:https://www.cnblogs.com/caibixiang123/p/8244615.html

總結

以上是生活随笔為你收集整理的java-二分查找树的实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。