二叉查找樹擁有如下特性：
- 若左子樹不空切揭，則左子樹上所有結點的值均小于或等于它的根結點的值妈倔；
- 若右子樹不空及志，則右子樹上所有結點的值均大于或等于它的根結點的值攒读；
- 左朵诫、右子樹也分別為二叉查找樹；
package com.zhuke.datastruct;
import com.alibaba.fastjson.JSON;
import java.util.*;
import java.util.concurrent.atomic.AtomicInteger;
/**
* Created by ZHUKE on 2017/9/6.
*/
public class BSTUtils<T extends Comparable<T>> {
public static void main(String[] args) throws InterruptedException {
BSTUtils<Integer> BST = new BSTUtils<>();
BinaryNode<Integer> rootTree = null;
rootTree = BST.insert(100, rootTree);
rootTree = BST.insert(80, rootTree);
rootTree = BST.insert(120, rootTree);
rootTree = BST.insert(90, rootTree);
rootTree = BST.insert(85, rootTree);
rootTree = BST.insert(95, rootTree);
rootTree = BST.insert(110, rootTree);
rootTree = BST.insert(150, rootTree);
rootTree = BST.insert(115, rootTree);
rootTree = BST.insert(180, rootTree);
rootTree = BST.insert(140, rootTree);
BSTUtils<Integer> BST1 = new BSTUtils<>();
BinaryNode<Integer> rootTree1 = null;
rootTree1 = BST1.insertNoRecursive(-1, rootTree1);
rootTree1 = BST1.insertNoRecursive(31, rootTree1);
rootTree1 = BST1.insertNoRecursive(81, rootTree1);
rootTree1 = BST1.insertNoRecursive(-36, rootTree1);
rootTree1 = BST1.insertNoRecursive(188, rootTree1);
rootTree1 = BST1.insertNoRecursive(-2, rootTree1);
rootTree1 = BST1.insertNoRecursive(9, rootTree1);
System.out.println("Search result = " + BST.search(100, rootTree).data);
System.out.println("Search with no recursive result = " + BST.searchNoRecursive(100, rootTree).data);
System.out.println("BST max value = " + BST.findMax(rootTree).data);
System.out.println("BST min value = " + BST.findMin(rootTree).data);
System.out.println("BST with no recursive max value = " + BST.findMaxNoRecursive(rootTree).data);
System.out.println("BST with no recursive min value = " + BST.findMinNoRecursive(rootTree).data);
ArrayList<Integer> preOrderResult = new ArrayList<>();
BST.preOrderTraversal(rootTree, preOrderResult);
System.out.println("PreOrder traversal result = " + JSON.toJSONString(preOrderResult));
preOrderResult.clear();
BST.preOrderTraversalNoRecursive(rootTree, preOrderResult);
System.out.println("PreOrder traversal with no recursive result = " + JSON.toJSONString(preOrderResult));
ArrayList<Integer> inOrderResult = new ArrayList<>();
BST.inOrderTraversal(rootTree, inOrderResult);
System.out.println("InOrder traversal result = " + JSON.toJSONString(inOrderResult));
inOrderResult.clear();
BST.inOrderTraversalNoRecursive(rootTree, inOrderResult);
System.out.println("InOrder traversal with no recursive result = " + JSON.toJSONString(inOrderResult));
ArrayList<Integer> postOrderResult = new ArrayList<>();
BST.postOrderTraversal(rootTree, postOrderResult);
System.out.println("PostOrder traversal result = " + JSON.toJSONString(postOrderResult));
postOrderResult.clear();
BST.postOrderTraversalNoRecursive(rootTree, postOrderResult);
System.out.println("PostOrder traversal with no recursive result = " + JSON.toJSONString(postOrderResult));
ArrayList<Integer> breadthResult = new ArrayList<>();
BST.breadthTraversal(rootTree, breadthResult);
System.out.println("Breadth traversal result = " + JSON.toJSONString(breadthResult));
BST.delete(120, rootTree);
Thread.sleep(Integer.MAX_VALUE);
}
/**
* 在BST中插入一個數(shù)據(jù)值為data的節(jié)點
*
* @param data 數(shù)據(jù)值
* @param tree 根節(jié)點
* @return 插入了一個數(shù)據(jù)值為data的BST根節(jié)點
*/
public BinaryNode<T> insert(T data, BinaryNode<T> tree) {
if (tree == null) {
tree = new BinaryNode<>(data, null, null, null);
return tree;
}
int compareResult = data.compareTo(tree.data);
if (compareResult < 0) {
tree.leftNode = insert(data, tree.leftNode);
tree.leftNode.parentNode = tree;
} else if (compareResult > 0) {
tree.rightNode = insert(data, tree.rightNode);
tree.rightNode.parentNode = tree;
} else {
tree.count.incrementAndGet();
return tree;
}
return tree;
}
/**
* 使用非遞歸方式薄扁，在BST中插入一個數(shù)據(jù)值為data的節(jié)點
*
* @param data 數(shù)據(jù)值
* @param tree 根節(jié)點
* @return 插入了一個數(shù)據(jù)值為data的BST根節(jié)點
*/
public BinaryNode<T> insertNoRecursive(T data, BinaryNode<T> tree) {
if (tree == null) {
tree = new BinaryNode<>(data, null, null, null);
return tree;
}
int compareResult = data.compareTo(tree.data);
if (compareResult == 0) {
tree.count.incrementAndGet();
return tree;
} else {
BinaryNode<T> targetInsertLocation = compareResult > 0 ? tree.rightNode : tree.leftNode;
if (targetInsertLocation == null) {
if (compareResult > 0) {
tree.rightNode = new BinaryNode<>(data, null, null, tree);
} else {
tree.leftNode = new BinaryNode<>(data, null, null, tree);
}
return tree;
}
//循環(huán)遍歷到樹的末端節(jié)點剪返，判斷處理插入的正確位置
while (true) {
compareResult = data.compareTo(targetInsertLocation.data);
if (compareResult == 0) {
targetInsertLocation.count.incrementAndGet();
return tree;
} else {
if (compareResult > 0) {
if (targetInsertLocation.rightNode != null) {
targetInsertLocation = targetInsertLocation.rightNode;
} else {
targetInsertLocation.rightNode = new BinaryNode<>(data, null, null, targetInsertLocation);
return tree;
}
} else {
if (targetInsertLocation.leftNode != null) {
targetInsertLocation = targetInsertLocation.leftNode;
} else {
targetInsertLocation.leftNode = new BinaryNode<>(data, null, null, targetInsertLocation);
return tree;
}
}
}
}
}
}
/**
* 刪除節(jié)點值為data的節(jié)點
*
* @param data 數(shù)據(jù)值
* @param tree 根節(jié)點
* @return 刪除節(jié)點值為data后的BST
*/
public BinaryNode<T> delete(T data, BinaryNode<T> tree) {
BinaryNode<T> searchedNode = search(data, tree);
if (searchedNode == null) {
return tree;
}
//葉子節(jié)點废累，直接刪除
if (searchedNode.leftNode == null && searchedNode.rightNode == null) {
int parentLeftCompareResult = searchedNode.parentNode.leftNode.data.compareTo(data);
searchedNode.parentNode = null;
if (searchedNode.count.decrementAndGet() == 0) {
//只有一個元素，直接刪除關聯(lián)關系
if (parentLeftCompareResult == 0) {
searchedNode.leftNode = null;
} else {
searchedNode.rightNode = null;
}
}
} else if (searchedNode.leftNode != null && searchedNode.rightNode != null) {//同時有左子樹和右子樹
//找到替代被刪除節(jié)點的節(jié)點脱盲，該節(jié)點需要比被刪除節(jié)點的左子樹都大邑滨，比右子樹都小
//被刪除節(jié)點的右子樹的最小值，滿足上述要求钱反，而且該節(jié)點一定是葉子節(jié)點
BinaryNode<T> replacedNode = findMin(searchedNode.rightNode);
searchedNode.data = replacedNode.data;
//替換完成后掖看，直接刪除
replacedNode.parentNode.leftNode = null;
replacedNode.parentNode = null;
} else {
/*只有左子樹或右子樹*/
if (searchedNode.leftNode != null) {
//只有左子樹，將左子樹和父結點相連接
int searchedNodeCompareToParentNode = searchedNode.data.compareTo(searchedNode.parentNode.data);
if (searchedNodeCompareToParentNode > 0) {
//被刪除的節(jié)點為父結點的右節(jié)點
searchedNode.parentNode.rightNode = searchedNode.leftNode;
} else {
searchedNode.parentNode.leftNode = searchedNode.leftNode;
}
} else {
//只有右子樹面哥，將右子樹和父節(jié)點想相連接
int searchedNodeCompareToParentNode = searchedNode.data.compareTo(searchedNode.parentNode.data);
if (searchedNodeCompareToParentNode > 0) {
//被刪除的節(jié)點為父結點的右節(jié)點
searchedNode.parentNode.rightNode = searchedNode.rightNode;
} else {
searchedNode.parentNode.leftNode = searchedNode.rightNode;
}
}
}
return tree;
}
/**
* 查找指定值在BST中的所在節(jié)點
*
* @param data 數(shù)據(jù)值
* @param tree 根節(jié)點
* @return 節(jié)點值為data的節(jié)點
*/
public BinaryNode<T> search(T data, BinaryNode<T> tree) {
if (tree == null) {
return null;
}
int compareResult = data.compareTo(tree.data);
if (compareResult > 0) {
return search(data, tree.rightNode);
} else if (compareResult < 0) {
return search(data, tree.leftNode);
} else {
return tree;
}
}
/**
* 非遞歸方式哎壳，查找指定值在BST中的所在節(jié)點
*
* @param data 數(shù)據(jù)值
* @param tree 根節(jié)點
* @return 節(jié)點值為data的節(jié)點
*/
public BinaryNode<T> searchNoRecursive(T data, BinaryNode<T> tree) {
if (tree == null) {
return null;
}
int compareResult = data.compareTo(tree.data);
if (compareResult == 0) {
return tree;
} else {
BinaryNode<T> targetNodeLocation = compareResult > 0 ? tree.rightNode : tree.leftNode;
//遍歷查找樹的各層節(jié)點
while (targetNodeLocation != null) {
compareResult = data.compareTo(targetNodeLocation.data);
if (compareResult == 0) {
return targetNodeLocation;
} else {
targetNodeLocation = (compareResult > 0 ? targetNodeLocation.rightNode : targetNodeLocation.leftNode);
}
}
return null;
}
}
/**
* 查找BST的最小值
*
* @param tree 根節(jié)點
* @return BST中的最小值
*/
public BinaryNode<T> findMin(BinaryNode<T> tree) {
if (tree == null) {
return null;
}
if (tree.leftNode == null) {
return tree;
} else {
return findMin(tree.leftNode);
}
}
public BinaryNode<T> findMinNoRecursive(BinaryNode<T> tree) {
if (tree == null) {
return null;
}
if (tree.leftNode == null) {
return tree;
} else {
BinaryNode<T> targetNodeLocation = tree.leftNode;
while (true) {
if (targetNodeLocation.leftNode == null) {
return targetNodeLocation;
} else {
targetNodeLocation = targetNodeLocation.leftNode;
}
}
}
}
/**
* 查找BST的最大值
*
* @param tree 根節(jié)點
* @return BST中的最大值
*/
public BinaryNode<T> findMax(BinaryNode<T> tree) {
if (tree == null) {
return null;
}
if (tree.rightNode == null) {
return tree;
} else {
return findMax(tree.rightNode);
}
}
public BinaryNode<T> findMaxNoRecursive(BinaryNode<T> tree) {
if (tree == null) {
return null;
}
if (tree.rightNode == null) {
return tree;
} else {
BinaryNode<T> targetNodeLocation = tree.rightNode;
while (true) {
if (targetNodeLocation.rightNode == null) {
return targetNodeLocation;
} else {
targetNodeLocation = targetNodeLocation.rightNode;
}
}
}
}
/**
* 前序遍歷BST
*
* @param tree BST根節(jié)點
* @param traversalResult 遍歷結果
*/
public void preOrderTraversal(BinaryNode<T> tree, List<T> traversalResult) {
if (tree != null) {
addTraversalToResultList(tree, traversalResult);
preOrderTraversal(tree.leftNode, traversalResult);
preOrderTraversal(tree.rightNode, traversalResult);
}
}
/**
* 非遞歸方式前序遍歷BST
*
* @param tree BST根節(jié)點
* @param traversalResult 遍歷結果
*/
public void preOrderTraversalNoRecursive(BinaryNode<T> tree, List<T> traversalResult) {
if (tree != null) {
//使用一個棧，暫存訪問左右子樹的順序
Stack<BinaryNode<T>> stack = new Stack<>();
BinaryNode<T> node = tree;
while (node != null || !stack.isEmpty()) {
//首先訪問根節(jié)點尚卫，并將根節(jié)點入棧归榕，因為需要通過根節(jié)點進入相應的左右子樹
while (node != null) {
addTraversalToResultList(node.clone(), traversalResult);
stack.push(node);
node = node.leftNode;
}
//上面的循環(huán)全部訪問左子樹的所有根節(jié)點，直到BST的最左下角吱涉，此時情況如下
/*
x top_node
/ / \
top_node node=null right_node
/ \
node=null null
*/
//因此無論何種情況都需要出棧刹泄，因為此時top_node的根節(jié)點和左葉子節(jié)點都已經(jīng)完全訪問，
// 所以按照相同步驟遍歷訪問其右子樹
if (!stack.isEmpty()) {
node = stack.pop();
node = node.rightNode;
}
}
}
}
/**
* 中序遍歷BST
*
* @param tree BST根節(jié)點
* @param traversalResult 遍歷結果
*/
public void inOrderTraversal(BinaryNode<T> tree, List<T> traversalResult) {
if (tree != null) {
inOrderTraversal(tree.leftNode, traversalResult);
addTraversalToResultList(tree, traversalResult);
inOrderTraversal(tree.rightNode, traversalResult);
}
}
/**
* 非遞歸方式中序遍歷BST
*
* @param tree BST根節(jié)點
* @param traversalResult 遍歷結果
*/
public void inOrderTraversalNoRecursive(BinaryNode<T> tree, List<T> traversalResult) {
if (tree != null) {
//使用一個棧怎爵，暫存訪問左右子樹的順序
Stack<BinaryNode<T>> stack = new Stack<>();
BinaryNode<T> node = tree;
while (node != null || !stack.isEmpty()) {
//一直遍歷到左子樹最左下角特石，邊遍歷邊保存根節(jié)點到棧中
//需要借助保存的根節(jié)點進入右節(jié)點的遍歷過程
while (node != null) {
stack.push(node);
node = node.leftNode;
}
//此時位于棧頂?shù)脑赜腥缦聝煞N情況，無論哪種情況都應將棧頂節(jié)點出棧鳖链，訪問該節(jié)點
/*
x top_node
/ / \
top_node node=null right_node
/ \
node=null null
*/
// 此時可以進行訪問棧頂元素
if (!stack.isEmpty()) {
node = stack.pop();
addTraversalToResultList(node.clone(), traversalResult);
//如果訪問節(jié)點的根節(jié)點有右子樹县匠，則進行上層循環(huán)，中序遍歷訪問右子樹的節(jié)點
node = node.rightNode;
}
}
}
}
/**
* 后序遍歷BST
*
* @param tree BST根節(jié)點
* @param traversalResult 遍歷結果
*/
public void postOrderTraversal(BinaryNode<T> tree, List<T> traversalResult) {
if (tree != null) {
postOrderTraversal(tree.leftNode, traversalResult);
postOrderTraversal(tree.rightNode, traversalResult);
addTraversalToResultList(tree, traversalResult);
}
}
/**
* 非遞歸方式撒轮，后序遍歷BST
*
* @param tree BST根節(jié)點
* @param traversalResult 遍歷結果
*/
public void postOrderTraversalNoRecursive(BinaryNode<T> tree, List<T> traversalResult) {
if (tree != null) {
//記錄原BST的左右子樹訪問順序
Stack<BinaryNode<T>> stack = new Stack<>();
//記錄后續(xù)遍歷的遍歷順序
Stack<BinaryNode<T>> output = new Stack<>();
stack.push(tree);
while (!stack.isEmpty()) {
BinaryNode<T> pop = stack.pop();
//將根節(jié)點首先入棧到output棧底乞旦，根節(jié)點最后訪問
output.push(pop);
if (pop.leftNode != null) {
//leftNode節(jié)點先入棧stack，后入output棧题山，符合left-right-root的訪問順序
stack.push(pop.leftNode);
}
if (pop.rightNode != null) {
//right節(jié)點后入棧stack兰粉，先入output棧，符合left-right-root的訪問順序
stack.push(pop.rightNode);
}
}
while (!output.isEmpty()) {
addTraversalToResultList(output.pop(), traversalResult);
}
}
}
/**
* 廣度優(yōu)先遍歷
*
* @param tree BST
* @param traversalResult 遍歷結果
*/
public void breadthTraversal(BinaryNode<T> tree, List<T> traversalResult) {
Queue<BinaryNode<T>> queue = new LinkedList<>();
queue.add(tree);
while (!queue.isEmpty()) {
BinaryNode<T> node = queue.remove();
addTraversalToResultList(node, traversalResult);
if (node.leftNode != null) {
queue.add(node.leftNode);
}
if (node.rightNode != null) {
queue.add(node.rightNode);
}
}
}
/**
* 對二叉排序樹進行升序排序顶瞳，即是對BST進行中序遍歷的結果
*
* @param tree 根節(jié)點
* @param sortedData 升序排序的結果
*/
public void sort(BinaryNode<T> tree, List<T> sortedData) {
inOrderTraversal(tree, sortedData);
}
private void addTraversalToResultList(BinaryNode<T> node, List<T> traversalResult) {
for (int i = 0; i < node.count.intValue(); i++) {
traversalResult.add(node.data);
}
}
}
/**
* 二叉查找樹的節(jié)點數(shù)據(jù)結構
*
* @param <T> 數(shù)據(jù)節(jié)點的類型玖姑，必須實現(xiàn)Comparable接口
*/
class BinaryNode<T extends Comparable<T>> {
/**
* 數(shù)據(jù)類型
*/
T data;
/**
* 左節(jié)點
*/
BinaryNode<T> leftNode;
/**
* 右節(jié)點
*/
BinaryNode<T> rightNode;
/**
* 父節(jié)點
*/
BinaryNode<T> parentNode;
/**
* 數(shù)據(jù)data出現(xiàn)的次數(shù)，
* 用于支持BST可以插入相同data的值慨菱，
* 以便節(jié)點數(shù)據(jù)值的比較
*/
AtomicInteger count;
public BinaryNode(T data) {
this.data = data;
}
public BinaryNode(T data, BinaryNode<T> leftNode, BinaryNode<T> rightNode, BinaryNode<T> parentNode) {
this.data = data;
this.leftNode = leftNode;
this.rightNode = rightNode;
this.parentNode = parentNode;
this.count = new AtomicInteger(1);
}
@Override
protected BinaryNode<T> clone() {
BinaryNode<T> clonedNode = new BinaryNode<>(this.data, null, null, null);
clonedNode.count = new AtomicInteger(this.count.intValue());
return clonedNode;
}
}
