二叉查找树，字排序树，号搜索树，嘛，总之都是一个东西。
定义
二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：
（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
（3）左、右子树也分别为二叉排序树；
（4）没有键值相等的节点。
这么整齐的格式一看就是百度百科粘贴过来的。
一些分析
从名字可知，它能给元素排序，因为元素都是有序的，所以搜索特别方便，搜索效率一般情况下远胜链表和顺序表，但是还得看这个树的平衡程度，时间复杂度在O(Log2n)和O(n)之间。
查找二叉树按中序遍历得到的一定是有序数组，可以用这一点来验证我们写的查找二叉树是否合格。
所谓排序，必然是建立在元素可比较大小的基础上，所以这里面能放的元素，必然实现了Comparable接口。
插入元素的实现
如果没有根节点，那直接当作根节点，否则从根节点开始比较大小，目标节点值大于元素，则向左走，反之向右走。
删除元素的实现
删除元素，其实无非就是断开这个节点和外界的关系，再给他找个替代品补位，这个替代品在大小关系上需要满足查找二叉树的性质。根据查找二叉树的性质，对于任意节点p都有p左侧的元素全部小于p右侧的元素，所以如果要删除节点p，有两种选择：
1.用其左子树中最大的元素补位。
2.用其右子树中最小的元素补位。
当他同时有左右子树时，无论选哪种都行，如果只有一种那就没得选了。如果没有，那就省力气了。
什么？你问他的父节点怎么办？嗯，替代品当然直接继承了这种关系。
但是这里有一点需要特别注意，替代品继承他的关系时可以导致某个关系的消失，这种情况只会发生在替代品跟他本来就有直接关系时，所以我们在替换的时候判断一下即可，如果出现这种情况，会导致替代品节点根这个关系的目标节点是同一个（引用相等），这一块我的具体代码里有标注。
最后，别忘了如果要删除的元素是根节点，需要把根节点置空。
具体实现
这一篇直接用代码收尾了，代码经过了我的大(ji)量(ci)测试，暂时没发现什么问题。如果哪位朋友觉得有问题欢迎随时交流。
/**
* 二叉查找树
* Created by sylva on 2018/12/9.
*/
public class BinarySearchTree<T extends Comparable<T>> {
public static class Node<T extends Comparable<T>>{
private T data;
private Node<T> parent;
private Node<T> leftChild;
private Node<T> rightChild;
private Node(T data) {
this.data = data;
}
public T getData() {
return data;
}
public Node<T> getParent() {
return parent;
}
public Node<T> getLeftChild() {
return leftChild;
}
public Node<T> getRightChild() {
return rightChild;
}
}
private Node<T> root;
private int size;
public int size() {
return size;
}
public Node<T> getRoot() {
return root;
}
/**
* 放入元素
* @param data 元素值
* @return 是否重复，true代表已经有这个元素
* */
public boolean put(T data){
Node<T> node = new Node<>(data);
if(root == null){
size++;
root = node;
return false;
}
Node<T> start = root;
Node<T> prev = null;
while(start != null){
prev = start;
if(start.data.compareTo(data) == 0){
return true;
}else if(start.data.compareTo(data) > 0){
start = start.leftChild;
}else{
start = start.rightChild;
}
}
size++;
node.parent = prev;
if(prev.data.compareTo(data) > 0){
prev.leftChild = node;
return false;
}else{
prev.rightChild = node;
return false;
}
}
/**
* 删除数据
* @param data 要删除的数据
* @return true代表有这个数据而且已经删除，false代表没有这个数据
* */
public boolean remove(T data){
Node<T> node = find(data);
if(node == null)
return false;
//如果有右子树
if(node.rightChild != null) {
Node<T> right = node.rightChild;
Node<T> minInRight = findMinNode(right);
replaceNode(node, minInRight);
}else if(node.leftChild != null){
//如果只有左子树
Node<T> left = node.leftChild;
Node<T> maxInLeft = findMaxNode(left);
replaceNode(node, maxInLeft);
}else{
//断子绝孙
replaceNode(node, null);
}
size--;
return true;
}
/**
* 查找（查找二叉树）中最小的节点
* @param root 根节点
* */
private Node<T> findMinNode(Node root){
for(; root.leftChild != null; root = root.leftChild){
}
return root;
}
/**
* 查找（查找二叉树）中最大的节点
* @param root 根节点
* */
private Node<T> findMaxNode(Node root){
for(; root.rightChild != null; root = root.rightChild){
}
return root;
}
/**
* 把老节点替换成新节点（这真是一个悲伤的故事）
* @param node 老节点
* @param newNode 新节点
* */
private void replaceNode(Node node, Node newNode){
//原节点的关系就是父节点和左右子
Node parent = node.parent;
Node leftChild = node.leftChild;
Node rightChild = node.rightChild;
//让他六亲不认
node.parent = null;
node.leftChild = null;
node.rightChild = null;
//如果他爸活着，他爸心里新节点已经代替了他的位置
if(parent != null) {
if (parent.data.compareTo(node.data) > 0) {
parent.leftChild = newNode;
} else {
parent.rightChild = newNode;
}
}
//如果小儿子活着，小儿子把新节点当成爸爸
if(leftChild != null) {
leftChild.parent = newNode;
}
//如果大儿子活着，大儿子也抛弃了他
if(rightChild != null) {
rightChild.parent = newNode;
}
//新节点要么是叶子，要么只有左子或右子
Node nParent = newNode.parent;
Node nLeft = newNode.leftChild;
Node nRight = newNode.rightChild;
Node toLink = nLeft == null ? nRight : nLeft;
if(nParent.data.compareTo(newNode.data) > 0){
nParent.leftChild = toLink;
if(toLink != null)
toLink.parent = nParent;
}else{
nParent.rightChild = toLink;
if(toLink != null)
toLink.parent = nParent;
}
//如果新节点活着，让新节点承认这些关系
if(newNode != null){
//以下三个if是用来判断上文提到的替代品节点根关系目标节点相同的情况
//这种情况直接放弃继承这种关系
if(newNode != parent)
newNode.parent = parent;
if(newNode != leftChild)
newNode.leftChild = leftChild;
if(newNode != rightChild)
newNode.rightChild = rightChild;
}
//root其实是个跟树本身无关的外部引用，前面已经把新节点的关系处理完毕
//这里只需要把外部引用指向新节点即可
if(node == root){
root = newNode;
}
}
/**
* 孤立一个节点，断开它跟外界的关系
* @param node 被孤立的节点
* */
private void isolateNode(Node node){
replaceNode(node, null);
}
private Node<T> find(T data){
Node<T> result = root;
while(result != null){
int compareResult = result.data.compareTo(data);
if(compareResult == 0){
return result;
}else if(compareResult > 0){
result = result.leftChild;
}else{
result = result.rightChild;
}
}
return result;
}
/**
* 中序遍历
* @param root 相对根节点
* */
public void ldrTraverse(Node root){
if(root == null)
return;
ldrTraverse(root.leftChild);
System.out.print(root.data + " ");
ldrTraverse(root.rightChild);
}
@Test
public void test(){
BinarySearchTree<Integer> bst = new BinarySearchTree<>();
// int[] arr = new int[20];
int[] arr = new int[]{1, 63, 49, 8, 58, 73, 21, 74, 70, 4, 72, 41, 71, 82, 40, 89};
Random random = new Random();
for (int i = 0; i < arr.length; i++) {
// arr[i] = random.nextInt(99);
bst.put(arr[i]);
}
Arrays.sort(arr);
println(String.format("数组长度：%s，树长度：%s", arr.length, bst.size()));
println("数组：" + Arrays.toString(arr));
print("树：");
bst.ldrTraverse(bst.root);
println("");
for (int num : arr) {
println("删除数字：" + num);
bst.remove(num);
println("删除后二叉树内容：");
bst.ldrTraverse(bst.root);
println(String.format("数组长度：%s，树长度：%s", arr.length, bst.size()));
println("");
bst.put(num);
println("再放回去后二叉树内容：");
bst.ldrTraverse(bst.root);
println("");
}
}
private void println(String str){
System.out.println(str);
}
private void print(String str){
System.out.print(str);
}
}
网友评论