二分搜索树

package BST;

import java.util.LinkedList;
import java.util.Queue;

public class BST<Key extends Comparable<Key>,Value>{

private class Node{             //节点的构造是key，value对应，外加上一个左右孩子节点
        private Key key;
private Value value;
private Node left;
private Node right;
public Node(Key key,Value value)
        {
this.key=key;
this.value=value;
this.left=null;
this.right=null;
        }
public Node(Node node)　　　　//第二种构造方法，直接用另一个节点进行复制
        {
this.key=node.key;
this.value=node.value;
this.left=node.left;
this.right=node.right;
        }
    }

private Node root;      //根节点
    private int count;      //节点数量

    public BST()            //默认构造一颗空的二分搜索树
    {
        Node root=null;
count=0;
    }

public int size()
    {
return count;
    }
public boolean isEmpty()
    {
return count==0;
    }

public void insert(Key key,Value value)         //插入一个元素，找到合适的位置插入
    {
root= insert(root,key,value);
    }
public boolean contain(Key key)                 //查找是否包含这个元素，包含返回true，否则返回false;
    {
return contain(root,key);                   //递归调用

    }
public Value search(Key key)                    //查找是否有这个元素，找到了返回这个元素key对应的value值，不然返回null
    {
return search(root,key);                    //递归调用
    }
public void preOrder()                          //先序遍历
    {
        perOrder(root);
    }
public void inOrder()                           //中序遍历
    {
        inOrder(root);
    }
public  void postOrder()                        //后序遍历
    {
        postOrder(root);
    }

public void levelOrder()                        //二叉树的层序遍历，
    {
        Queue<Node> q=new LinkedList<>();           //利用一个队列，每次取出一个节点，入队，取出它，操作，再将左右孩子节点入队列
        q.add(root);
while(!q.isEmpty())
        {
            Node node = q.remove();
            System.out.println(node.key);
if(node.left!=null)
                q.add(node.left);
if(node.right!=null)
                q.add(node.right);
        }
    }
// 寻找二分搜索树的最小的键值
    public Key minimum(){
assert count != 0;
        Node minNode = minimum( root );
return minNode.key;
    }

// 寻找二分搜索树的最大的键值
    public Key maximum(){
assert count != 0;
        Node maxNode = maximum(root);
return maxNode.key;
    }

public void removeMin()
    {
if(root!=null)
        {
root=removeMin(root);
        }
    }

public void removeMax()
    {
if(root!=null)
root=removeMax(root);
    }
public void remove(Key key)
    {
root=remove(root,key);
    }

private Node remove(Node node, Key key) {
if(node==null)
return null;
if(key.compareTo(node.key)<0)
        {
            node.left=remove(node.left,key);
return node;

        }
else if(key.compareTo(node.key)>0)
        {
            node.right=remove(node.right,key);
return node;
        }
else
        {
if(node.left==null)
            {
                Node rightNode=node.right;
                node.right=null;
count--;
return rightNode;
            }
else if(node.right==null)
            {
                Node leftNode=node.left;
                node.left=null;
count--;
return leftNode;
            }
else            //左右孩子都不为空
            {
                Node successor=new Node(minimum(node.right));
count++;
                successor.right=removeMin(node.right);
                successor.left=node.left;
                node.left=null;
                node.right=null;
count--;
return successor;
            }
        }

    }

// 删除掉以node为根的二分搜索树中的最大节点
    // 返回删除节点后新的二分搜索树的根