BST

BST实现代码:

/**
 * Class BinarySearchTree
 * @author Administrator
 *
 */
import java.util.Stack;
import java.util.Queue;
import java.util.LinkedList;;;
public class BST<E extends Comparable<E>> {
    /**
     * class Node
     * @author Administrator
     *
     */
    private class Node{
        Node left;
        Node right;
        E e;
        public Node(E e) {
            left = null;
            right = null;
            this.e = e;
        }
    }
    //number of nodes
    private int size;
    private Node root;
    /**
     * constructor
     */
    public BST() {
        root = null;
        size = 0;
    }
    /**
     * determine  whether BST is empty
     * @return
     */
    public boolean isEmpty() {
        return size==0;
    }
    
    /**
     * the number of BST's nodes
     * @return
     */
    public int getSize() {
        return size;
    }
    
    /**
     * add nodes into BFS
     * there is no return
     * the goal of the code block is change the BST
     * @param e
     */
    public void add(E e) {
        /*
        if (root == null) {
            root = new Node(e);
            size++;
        }
        else
            add(root,e);
            */
        root = add(root,e);
    }
    /**
     * the private add method
     * the return value is type of node
     * @param node
     * @param e
     */
    private Node add(Node node,E e) {
        if (node == null) {
            size++;
            return new Node(e);         
        }
        
        if (e.compareTo(node.e)<0) {
            node.left = add(node.left, e);
        }
        else if(e.compareTo(node.e)>0) {
            node.right = add(node.right, e);
        }
        return node;
    }
    /*
    private void add(Node node,E e) {

        
        // the simplest case
         
        if(e.equals(node.e)) {
            return;
        }
        else if (e.compareTo(node.e)<0 && node.left == null) {
            node.left = new Node(e);
            size++;
            return;         
        }
        else if (e.compareTo(node.e)>0 && node.right == null){
            node.right = new Node(e);
            size++;
            return;         
        }
        
        
        //recursion
         
        if (e.compareTo(node.e)<0) {
            add(node.left,e);           
        }
        else if (e.compareTo(node.e)>0) {
            add(node.right,e);
        }       
    }
    */
    /**
     * determine whether BST contains the target 
     * @param e
     * @return
     */
    public boolean contains(E e) {
        return contains(root,e);        
    }
    
    private boolean contains(Node node,E e) {
        // simplest case
        if(node == null)
            return false;
        
        if (e.equals(node.e)) {
            return true;
        }
        
        /** recursion
         * the reason of return every contains is 
         * all of them will run into the simplest case
         * and return a boolean result 
         */
        if(e.compareTo(node.e)<0) {
            return contains(node.left,e);
        }
        else 
            return contains(node.right,e);
    }
    
    /**
     *  the method of traverse
     *  preOrder traverse
     */
    public void preOrder() {
        /**
         * traverse from root
         */
        preOrder(root);
    }
    
    
    private void preOrder(Node node) {
        if (node == null) {
            return;
        }
        
        /**
         * access the node first
         * then the subtree
         */
        System.out.println(node.e);
        preOrder(node.left);
        preOrder(node.right);
        
    }
    /**
     * preOrder based on stack structure
     */
    public void preOrderNR(Node node) {
        Stack<Node> stack = new Stack<>();
        if (node == null) {
            return;
        }
        
        stack.push(node);
        while(!stack.isEmpty()) {
            Node con_node = stack.pop();
            System.out.println(con_node.e);
            
            if (con_node.right != null) {
                stack.push(con_node.right);         
            }
            
            if (con_node.left != null) {
                stack.push(con_node.left);          
            }
        }
    }
    /**
     * the method of inOrder traverse
     */
    public void inOrder() {
        inOrder(root);
    }
    
    private void inOrder(Node node) {
        if (node == null) {
            return;
        }
        
        inOrder(node.left);
        System.out.println(node.e);
        inOrder(node.right);
    }
    
    /**
     * the method of post traverse
     */
    public void postOrder() {
        postOrder(root);
    }
    
    private void postOrder(Node node) {
        if (node == null) {
            return;
        }
        
        postOrder(node.left);
        postOrder(node.right);
        System.out.println(node.e);
        
    }
    /**
     * level-Traverse
     */
    public void levelTraverse(Node node) {
        if(node == null)
            return;
        Queue<Node> queue = new LinkedList<>();  //the usage of polymorphism ?
        queue.add(node);
        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);
            }       
        }
    }
    
    /**
     * get maximum element
     * the design idea is worthing for reference
     * @return
     */
    // get e
    public E maximum() {
        if(size ==0) {
            throw new IllegalArgumentException("BST is empty");
        }
        
        return maximum(root).e;
    }
    
    // private method --> get node
    private Node maximum(Node node) {
        if (node.right == null) {
            return node;
        }
        return maximum(node.right);
    }
    
    /**
     * get minimum element
     * the design idea is worthing for reference
     * @return
     */
    public E minimum() {
        if(size == 0) {
            throw new IllegalArgumentException("The BST is empty");
        }
        return minimum(root).e;
    }
    
    private Node minimum(Node node) {
        if (node.left == null) {
            return node;
        }
        return minimum(node.left);
    }
    
    /**
     * method of removeMinimum
     */
    public E removeMinimum() {
        E ret = minimum();
        root = removeMinimum(root);
        return ret;
    }
    
    private Node removeMinimum(Node node) {
        /*
        if (size == 0) {
            throw new IllegalArgumentException("The BST is empty");
        }
        if (node.left == minimum()) {
            node.left =null;
            return node;
        }
        return removeMinimum(node.left);
        */
        if (node.left == null) {
            Node rightNode = node.right;
            node.right = null;
            size --;
            return rightNode;
        }
        
        node.left = removeMinimum(node.left);
        return node;
    }
    
    /**
     * removeMaximum
     */
    public E removeMaximum() {
        E max = maximum();
        root = removeMaximum(root);
        return max;
        
    }
    
    private Node removeMaximum(Node node) {
        if (node.right == null) {
            Node leftnode = node.left;
            node.right = null;
            size--;
            return leftnode;
        }
        node.right = removeMaximum(node.right);
        return node;
    }
    /**
     * remove method
     */
    public void removeElement(E e) {
        root = removeElement(root,e);
    }
    
    private Node removeElement(Node node,E e) {
        if (node == null) {
            return null;
        }
        if (e.compareTo(node.e)<0) {
            node.left = removeElement(node.left,e); 
            return node;
        }
        else if (e.compareTo(node.e)>0) {
            node.right = removeElement(node.right,e);
            return node;
        }
        else {
            if(node.right == null) {
                Node leftNode = node.left;
                node.left = null;
                size--;
                return leftNode;
            }
            else if (node.left == null) {
                Node rightNode = node.right;
                node.right = null;
                size--;
                return rightNode;
            }
            else {
                Node successor = minimum(node);
                successor.right = removeMinimum(node.right);
                successor.left = node.left;
                
                node.left = node.right = null;
                return successor;           
            }
            
        }
    }
    
    /**
     * overwrite method of toString
     */
    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        generateBSTString(root,0,res);
        return res.toString();
    }
    
    /**
     * the goal of the method is change res
     * recursion
     * @param node
     * @param depth
     * @param res
     */
    private void generateBSTString(Node node,int depth,StringBuilder res) {
        if (node == null) {
            res.append(generateDepthString(depth) + "null");
            return;
        }
        
        res.append(generateDepthString(depth)+node.e + "\n");
        generateBSTString(node.left,depth+1,res);
        generateBSTString(node.right,depth+1,res);
    }
    
    /**
     * the goal of the function is to return a string 
     * @param depth
     * @return
     */
    private String generateDepthString(int depth) {
        StringBuilder res = new StringBuilder();
        for (int i = 0; i < depth; i++) {
            res.append("-");
        }
        return res.toString();
    }
    
    
}