（满满的干货）java数据结构之二分搜索树
/**
* 写关于树的操作时还是应该多用递归，如树的遍历用递归写就方便的多
* 用循环则需要使用栈，而同理对于删除操作则需要删除下一个节点时如何
* 将将上一个节点的下一个节点为空。
* 你可能会想为什么不能直接将当前节点为空，因为这只是使得当前的节点为空，
* 而原本生成的对象仍然存在。所以用递归可以将其下一个节点找到赋给当前节点。
*/
/*
* 相比于链式结构树结构更难于理解一些，但我们要记住不论怎样修改树结构，
* 我们是在root这个根节点下进行的，对root进行修改，明白引用与root的含义
*/
public class BST<E extends Comparable<E>> {
private class Node{
public Node left ,right ;
public E e ;
public Node(E e) {
this.e = e ;
}
}
private Node root ;
private int size ;
public boolean isEmpty() {
return size == 0 ;
}
public int getSize() {
return size ;
}
public void add(E e) {
root = add(root , e) ;
}
private Node add(Node node , E e) {
if(node == null) {
size ++ ;
return new Node(e) ;
}
if(e.compareTo(node.e) > 0) {
node.right = add(node.right , e) ;
} else if(e.compareTo(node.e) < 0) {
node.left = add(node.left , e) ;
}
return node ;
}
public void preOrder() {
preOrder(root) ;
}
private void preOrder(Node node) {
if(node != null) {
System.out.println(node.e);
preOrder(node.left) ;
preOrder(node.right) ;
}
}
public void inOrder() {
inOrder(root) ;
}
private void inOrder(Node node) {
if(node != null) {
inOrder(node.left) ;
System.out.println(node.e);
inOrder(node.right) ;
}
}
public void postOrder() {
postOrder(root) ;
}
private void postOrder(Node node) {
if(node != null) {
postOrder(node.left) ;
postOrder(node.right) ;
System.out.println(node.e);
}
}
public E minElem() {
return minElem(root).e ;
}
private Node minElem(Node node) {
while(node.left != null) {
node = node.left ;
}
return node ;
}
public E maxElem() {
return maxElem(root).e ;
}
//此处是while语句
private Node maxElem(Node node) {
while(node.right != null) {
node = node.right ;
}
return node ;
}
/*
* 删除最小值
*/
public E removeMin() {
E ret = minElem() ;
root = removeMin(root) ;
return ret ;
}
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 e = maxElem() ;
root = removeMax(root) ;
return e ;
}
private Node removeMax(Node node) {
if(node.right == null) {
size -- ;
// Node leftNode = node.left ;
// return leftNode ;
node = node.left ;
return node ;
}
node.right = removeMax(node.right) ;
return node ;
}
/**
* 删除任意节点
*/
public void remove(E e) {
root = remove(root , e) ;
}
private Node remove(Node node , E e) {
if(node == null) {
return null ;
}
if(e.compareTo(node.e) > 0) {
node.right = remove(node.right , e) ;
return node ;
} else if(e.compareTo(node.e) < 0) {
node.left = remove(node.left , e) ;
return node ;
} else {
if(node.left == null) {
node = node.right ;
size -- ;
return node ;
}
if(node.right == null) {
node = node.left ;
size -- ;
return node ;
}
Node successor = minElem(node.right) ;
successor.right = removeMin(node.right) ;
successor.left = node.left ;
return successor ;
}
}
public E getFirst() {
return root.e ;
}
public static void main(String[] args) {
BST<Integer> bst = new BST<>() ;
bst.add(123);
bst.add(12);
bst.add(890);
bst.add(789);
bst.add(122);
bst.add(9);
bst.add(99999);
bst.add(88);
bst.add(12345);
// System.out.println("先序遍历：");
// bst.preOrder();
System.out.println("--------------------------");
System.out.println(bst.getFirst());
System.out.println("先序遍历");
bst.preOrder();
System.out.println("中序遍历：");
bst.inOrder();
System.out.println("后序遍历：");
bst.postOrder();
System.out.println("--------------------------");
System.out.println(bst.minElem());
System.out.println(bst.maxElem());
System.out.println("--------------------------");
System.out.println(bst.getFirst());
System.out.println("删除最小值d-------------------");
System.out.println(bst.removeMin());
System.out.println("-----------------------------------------");
System.out.println(bst.removeMin());
System.out.println("-----------------------------------------");
System.out.println(bst.removeMin());
System.out.println("删除最大值--------------------------------");
System.out.println(bst.removeMax());
System.out.println(bst.removeMax());
System.out.println("-------------------------------------------");
System.out.println("数组大小size:" + bst.getSize());
bst.inOrder();
bst.remove(123);
System.out.println("数组大小size:" + bst.getSize());
System.out.println(bst.minElem());
System.out.println("-----------------------------------");
bst.inOrder();
}
}