public class BST> { private class Node{ public E e; public Node left,right; public Node(E e) { this.e = e; this.left = null; this.right = null; } } private Node root; private int size; public BST(){ root=null; size=0; } public int size(){ return size; } public boolean isEmpty(){ return size==0; } // //向二分搜索树中添加新的元素e // public void add(E e){ // if(root==null){ // root=new Node(e); // size++; // }else{ // add(root,e); // size++; // } // } // //向以NOde为根的二分搜索树中插入元素E,递归算法 // private void add(Node node,E e){ // 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); // return; // } // if(e.compareTo(node.e)<0){ // add(node.left,e); // }else{ // add(node.right,e); // } // } //递归实现 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.left=add(node.left,e); }else if(e.compareTo(node.e)>0){ node.right=add(node.right,e); } return node; } //查询是否包含元素 public boolean contains(E e){ return contains(root,e); } private boolean contains(Node node,E e){ if(node==null) return false; if(e.compareTo(node.e)==0) return true; else if(e.compareTo(node.e)<0){ return contains(node.left,e); }else{ return contains(node.right,e); } } //遍历二分搜索树 public void preOrder(){ preOrder(root); } private void preOrder(Node node) { if (node == null) return; System.out.println(node.e); preOrder(node.left); preOrder(node.right); } 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); } //后序遍历 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); } //寻找二分搜索树的最小元素 public E minimum() { if (size == 0) throw new IllegalArgumentException("BST is empty"); return minimum(root).e; } private Node minimum(Node node){ if(node.left==null) return node; return minimum(node.left); } //寻找二分搜索树的最da元素 public E maximum() { if (size == 0) throw new IllegalArgumentException("BST is empty"); return minimum(root).e; } private Node maximum(Node node){ if(node.right==null) return node; return maximum(node.right); } public E removeMin(){ E ret=minimum(); removeMin(root); return ret; } private Node remobeMin(Node node){ if(node.left==null){ Node rightNode=node.right; node.right=null; size--; return rightNode; } node.left=removeMin(node.left); return node; } @Override public String toString(){ StringBuilder res=new StringBuilder(); generateBSTString(root,0,res); return res.toString(); } private void generateBSTString(Node node,int depth,StringBuilder res){ if(node==null){ res.append(generateDepthString(depth)+"nulln"); return; } res.append(generateDepthString(depth)+node.e+"n"); generateBSTString(node.left,depth+1,res); generateBSTString(node.right,depth+1,res); } private String generateDepthString(int depth){ StringBuilder res=new StringBuilder(); for (int i = 0; i



