二分搜索树的基本实现
树是一种常见的数据结构，而二分搜索树又是一种最简单的树。接下来我将手写一棵二分搜索树，其中包含了
- 二分搜索树的增删改查
- 二分搜索树的前中后序遍历，其中前序遍历提供了非递归写法
- 二分搜索树的层序遍历
由于是底层实现，所以本文还是以递归代码为主
在这里主要想讲一下树的删除操作
我不会一上来就直接删除二分搜索树中的任意元素，首先我们可以先实现容易的删除。比如先删除树中的最大值或者最小值.
删除二分搜索树的最大值或最小值
为了方便，我们定义一个查找二分搜索树最大值或者最小值的方法
以删除二分搜索树的最大值为例。
如果该节点是叶子节点，那么很简单，我们直接将其删除即可，维护一下size变量即可。
如果该节点有左孩子，我们直接将他的左孩子进行挂接即可。
有了上述删除最大值或者最小值的思路，那么接下来我们进行删除二分搜索树中任意节点的实现。
- 如果删除的该节点只有左孩子，或者只有右孩子，那么与我们上面的思路是一样的，只需要将左孩子或者右孩子进行挂接就可以了。当然，如果是叶子节点，我们可以理解为只有左孩子或者只有右孩子，即叶子节点并不需要单独处理。
- 如果删除的该节点即有左孩子，又有右孩子。那么就是删除的重点了。在这里我们采用Hibbard deletion删除。
如果我们要删除的节点是58，此时我们找出58的后继节点，即第一个大于他的节点。很简单，我们只用去该节点的右子树中寻找最小元素即可，我们在上面封装的方法就派上了用场。
- 我们将删除该后继节点的右子树，挂接到该后继节点上
- 然后将58这个节点的左子树，挂接到后继节点上
- 然后将58这个节点删除即可
public class BinarySearchTree<E extends Comparable<E>> {
private class Node{
public E e;
public Node left;
public Node right;
public Node(E e){
this.e=e;
left=null;
right=null;
}
}
private Node root;
/**
* the number of node
*/
private int size;
public BinarySearchTree(){
size=0;
root=null;
}
/**
*
* @return size
*/
public int getSize(){
return size;
}
/**
*
* @return isEmpty
*/
public boolean isEmpty(){
return size==0;
}
/**
* insert element e to the tree
* @param e
*/
public void add(E e){
add(root,e);
}
/**
* recursion
* @param node
* @param e
* @return the root of the tree
*/
private Node add(Node node,E e){
if(node==null) {
size++;
return new Node(e);
}
// the number is small than the node.val
if(e.compareTo(node.e)<0)
node.left=add(node.left,e);
//the number is big than the node.val
if(e.compareTo(node.e)>0)
node.right=add(node.right,e);
return node;
}
/**
* is contains the element
* @param e
* @return
*/
public boolean contains(E e){
return contains(root,e);
}
/**
* recursion
* @param node
* @param e
* @return
*/
private boolean contains(Node node,E e){
if(node==null) return false;
if(e.compareTo(node.e)<0)
return contains(node.left,e);
else if(e.compareTo(node.e)>0)
return contains(node.right,e);
else{
return true;
}
}
/**
* preorder traversal
*/
public void preOrder(){
preOrder(root);
}
/**
* recursion
* @param node
*/
private void preOrder(Node node){
if(node==null) return;
System.out.println(node.e);
preOrder(node.left);
preOrder(node.right);
}
/**
* preorder traversal and no recursion
*/
public void preOrderNR(){
if(root==null) return;
Stack<Node>stack=new Stack<>();
stack.push(root);
while(!stack.isEmpty()){
Node cur=stack.pop();
System.out.println(cur.e);
if(cur.right!=null)
stack.push(cur.right);
if(cur.left!=null)
stack.push(cur.left);
}
}
/**
* inorder traversal
*/
public void inOrder(){
inOrder(root);
}
/**
* recursion
* @param node
*/
private void inOrder(Node node) {
if(node==null) return;
inOrder(node.left);
System.out.println(node.e);
inOrder(node.right);
}
/**
* postOrder traversal
*/
public void postOrder(){
postOrder(root);
}
/**
* recursion
* @param node
*/
private void postOrder(Node node){
if(node==null) return;
postOrder(node.left);
postOrder(node.right);
System.out.println(node.e);
}
/**
* sequenceorder tavaersal
* use FIFO(first in first out)
*/
public void levelOrder(){
if(root==null) return;
Queue<Node>queue=new LinkedList<>();
queue.add(root);
while(!queue.isEmpty()){
Node cur=queue.remove();
System.out.println(cur.e);
if(cur.left!=null) queue.add(cur.left);
if(cur.right!=null) queue.add(cur.right);
}
}
/**
* search the minimum of the tree
* @return
*/
public E minimum(){
if(size==0)
throw new IllegalArgumentException("BinarySearch Tree is empty");
Node node=minimum(root);
return node.e;
}
/**
* recursion search
* @param node
* @return node
*/
private Node minimum(Node node){
if(node.left==null)
return node;
return minimum(node.left);
}
/**
* search the maximum of the tree
* @return
*/
public E maximum(){
if(size==0)
throw new IllegalArgumentException("BinarySearch Tree is empty");
Node node = maximum(root);
return node.e;
}
/**
* recursion search
* @param node
* @return node
*/
private Node maximum(Node node){
if(node.right==null)
return node;
return maximum(node.right);
}
/**
* delete the node of the minimum element
* @return the element
*/
public E removeMin(){
E minimum = minimum();
root=removeMin(root);
return minimum;
}
/**
* recursion process
* @param node
* @return node
*/
private Node removeMin(Node node){
//the border of recursion
if(node.left==null){
Node rightNode=node.right;
// make the node out of the tree
node.right=null;
size--;
return rightNode;
}
node.left=removeMin(node.left);
return node;
}
/**
* delete the node of the maximum element
* @return the element
*/
public E removeMax(){
E maximum=maximum();
root=removeMax(root);
return maximum;
}
/**
* recursion process
* @param node
* @return node
*/
private Node removeMax(Node node){
//the border of recursion
if(node.right==null){
Node leftNode=node.left;
// make the node out of the tree
node.left=null;
size--;
return leftNode;
}
node.right=removeMax(node.right);
return node;
}
/**
* delete the node of element
* @param e
*/
public void remove(E e){
root= remove(e,root);
}
/**
* recursion process
* @param e
* @param node
* @return node
*/
private Node remove(E e, Node node) {
if(node==null)
return null;
if(e.compareTo(node.e)<0){
node.left=remove(e,node.left);
return node;
}else if(e.compareTo(node.e)>0){
node.right=remove(e,node.right);
return node;
}else{
// e==node.e
if(node.left==null){
Node rightNode=node.right;
node.right=null;
size--;
return rightNode;
}
if(node.right==null){
Node leftNode=node.left;
node.left=null;
size--;
return leftNode;
}
Node successor=minimum(node.right);
successor.right=removeMin(node.right);
successor.left=node.left;
node.left=node.right=null;
return successor;
}
}
}
