二叉查找树拥有如下特性：
- 若左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值；
- 若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；
- 左、右子树也分别为二叉查找树；
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中插入一个数据值为data的节点
*
* @param data 数据值
* @param tree 根节点
* @return 插入了一个数据值为data的BST根节点
*/
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中插入一个数据值为data的节点
*
* @param data 数据值
* @param tree 根节点
* @return 插入了一个数据值为data的BST根节点
*/
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;
}
//循环遍历到树的末端节点，判断处理插入的正确位置
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;
}
}
}
}
}
}
/**
* 删除节点值为data的节点
*
* @param data 数据值
* @param tree 根节点
* @return 删除节点值为data后的BST
*/
public BinaryNode<T> delete(T data, BinaryNode<T> tree) {
BinaryNode<T> searchedNode = search(data, tree);
if (searchedNode == null) {
return tree;
}
//叶子节点，直接删除
if (searchedNode.leftNode == null && searchedNode.rightNode == null) {
int parentLeftCompareResult = searchedNode.parentNode.leftNode.data.compareTo(data);
searchedNode.parentNode = null;
if (searchedNode.count.decrementAndGet() == 0) {
//只有一个元素，直接删除关联关系
if (parentLeftCompareResult == 0) {
searchedNode.leftNode = null;
} else {
searchedNode.rightNode = null;
}
}
} else if (searchedNode.leftNode != null && searchedNode.rightNode != null) {//同时有左子树和右子树
//找到替代被删除节点的节点，该节点需要比被删除节点的左子树都大，比右子树都小
//被删除节点的右子树的最小值，满足上述要求，而且该节点一定是叶子节点
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) {
//被删除的节点为父结点的右节点
searchedNode.parentNode.rightNode = searchedNode.leftNode;
} else {
searchedNode.parentNode.leftNode = searchedNode.leftNode;
}
} else {
//只有右子树，将右子树和父节点想相连接
int searchedNodeCompareToParentNode = searchedNode.data.compareTo(searchedNode.parentNode.data);
if (searchedNodeCompareToParentNode > 0) {
//被删除的节点为父结点的右节点
searchedNode.parentNode.rightNode = searchedNode.rightNode;
} else {
searchedNode.parentNode.leftNode = searchedNode.rightNode;
}
}
}
return tree;
}
/**
* 查找指定值在BST中的所在节点
*
* @param data 数据值
* @param tree 根节点
* @return 节点值为data的节点
*/
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中的所在节点
*
* @param data 数据值
* @param tree 根节点
* @return 节点值为data的节点
*/
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;
//遍历查找树的各层节点
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 根节点
* @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 根节点
* @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根节点
* @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根节点
* @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()) {
//首先访问根节点，并将根节点入栈，因为需要通过根节点进入相应的左右子树
while (node != null) {
addTraversalToResultList(node.clone(), traversalResult);
stack.push(node);
node = node.leftNode;
}
//上面的循环全部访问左子树的所有根节点，直到BST的最左下角，此时情况如下
/*
x top_node
/ / \
top_node node=null right_node
/ \
node=null null
*/
//因此无论何种情况都需要出栈，因为此时top_node的根节点和左叶子节点都已经完全访问，
// 所以按照相同步骤遍历访问其右子树
if (!stack.isEmpty()) {
node = stack.pop();
node = node.rightNode;
}
}
}
}
/**
* 中序遍历BST
*
* @param tree BST根节点
* @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根节点
* @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()) {
//一直遍历到左子树最左下角，边遍历边保存根节点到栈中
//需要借助保存的根节点进入右节点的遍历过程
while (node != null) {
stack.push(node);
node = node.leftNode;
}
//此时位于栈顶的元素有如下两种情况，无论哪种情况都应将栈顶节点出栈，访问该节点
/*
x top_node
/ / \
top_node node=null right_node
/ \
node=null null
*/
// 此时可以进行访问栈顶元素
if (!stack.isEmpty()) {
node = stack.pop();
addTraversalToResultList(node.clone(), traversalResult);
//如果访问节点的根节点有右子树，则进行上层循环，中序遍历访问右子树的节点
node = node.rightNode;
}
}
}
}
/**
* 后序遍历BST
*
* @param tree BST根节点
* @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根节点
* @param traversalResult 遍历结果
*/
public void postOrderTraversalNoRecursive(BinaryNode<T> tree, List<T> traversalResult) {
if (tree != null) {
//记录原BST的左右子树访问顺序
Stack<BinaryNode<T>> stack = new Stack<>();
//记录后续遍历的遍历顺序
Stack<BinaryNode<T>> output = new Stack<>();
stack.push(tree);
while (!stack.isEmpty()) {
BinaryNode<T> pop = stack.pop();
//将根节点首先入栈到output栈底，根节点最后访问
output.push(pop);
if (pop.leftNode != null) {
//leftNode节点先入栈stack，后入output栈，符合left-right-root的访问顺序
stack.push(pop.leftNode);
}
if (pop.rightNode != null) {
//right节点后入栈stack，先入output栈，符合left-right-root的访问顺序
stack.push(pop.rightNode);
}
}
while (!output.isEmpty()) {
addTraversalToResultList(output.pop(), traversalResult);
}
}
}
/**
* 广度优先遍历
*
* @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 根节点
* @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);
}
}
}
/**
* 二叉查找树的节点数据结构
*
* @param <T> 数据节点的类型，必须实现Comparable接口
*/
class BinaryNode<T extends Comparable<T>> {
/**
* 数据类型
*/
T data;
/**
* 左节点
*/
BinaryNode<T> leftNode;
/**
* 右节点
*/
BinaryNode<T> rightNode;
/**
* 父节点
*/
BinaryNode<T> parentNode;
/**
* 数据data出现的次数，
* 用于支持BST可以插入相同data的值，
* 以便节点数据值的比较
*/
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;
}
}
