14.Java实现二分搜索树

Love The Way You Lie 2022-02-28 14:34 157阅读 0赞

package com.cl.set;
    
    import java.util.LinkedList;
    import java.util.Queue;
    
    /**
     * 二分搜索树
     * @param <E>
     */
    public class BST<E extends Comparable<E>>{
        private class Node{
            private E e;
            private Node left,right;
            public Node(E e){
                this.e = e;
                this.left = 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;
        }
    
        /**
         * 二分搜索树里插入元素，不包含重复元素
         * @param e
         */
        public void addNonrRecursion(E e){
            Node cur = root,parent = null;
            while(cur!=null){
                parent=cur;
                if(cur.e.compareTo(e)<0){
                    cur=cur.right;
                }else if(cur.e.compareTo(e)>0){
                    cur=cur.left;
                }else{
                    break;
                }
            }
            //结点存在
            if(cur!=null)
                return ;
    
            size++;
            cur= new Node(e);
            if(root==null){
                root=cur;
                return ;
            }
            if(parent.e.compareTo(e)>0){
                parent.left=cur;
            }else{
                parent.right=cur;
            }
        }
    
        public void add(E e){
           root =  add(root,e);
        }
    
        /**递归
         * 向以node为根节点的树插入元素e
         * @param node
         * @param e
         * @return:返回插入新结点后二分搜索树的根
         */
        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);
        }
    
        /**
         * 以node为根的结点是否包含元素
         * @param node
         * @param e
         * @return
         */
        private boolean contains(Node node,E e){
            if(node == null)
                return false;
            if(node.e.compareTo(e)==0){
                return true;
            }else if(e.compareTo(node.e)<0){
                return contains(node.left,e);
            }else{
                return contains(node.right,e);
            }
        }
    
        public void preOder(){
            preOrder(root);
        }
    
        /**
         * 以node为根的结点前序遍历
         * @param node
         */
        private void preOrder(Node node) {
          /*  if(node==null){
                return ;
            }*/
            if(node!=null) {
                System.out.println(node.e);
                preOrder(node.left);
                preOrder(node.right);
            }
        }
    
        public int getSize() {
            return size;
        }
    
        /**
         * 中序遍历：结果是顺序的
         */
         public  void inOrder(){
            inOrder(root);
        }
    
        /**
         * 中序遍历node为根的数
         * @param node
         */
        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 void levelOrder(){
            Queue<Node> queue = new LinkedList<Node>();
            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);
                }
            }
        }
    
        /**
         * 返回BST最小的结点值
         * @return
         */
        public E minmum(){
            if(size==0){
                throw new IllegalArgumentException("BST is empty");
            }
           return minmum(root).e;
        }
    
        /**
         * 找以node为根的树的最小结点
         * @param node
         * @return 返回最小的结点
         */
        private Node minmum(Node node) {
            if(node.left==null){
                return node;
            }
            return minmum(node.left);
        }
    
        /**
         * 返回BST最大结点的值
         * @return
         */
        public E maxmum(){
            if(size==0){
                throw new IllegalArgumentException("BST is empty");
            }
            return maxmum(root).e;
        }
    
        /**返回以node为根的最大的结点
         *
         * @param node
         * @return
         */
        private Node maxmum(Node node) {
            if(node.right==null){
                return node;
            }
            return maxmum(node.right);
        }
        /**
         * 删除最小值并返回
    
       * @return
         */
        public E removeMin(){
            E e = minmum();
    
            //删除后的结果重新赋值给root
            root = removeMin(root);
            return e;
        }
    
        /**
         * 删除以node为根节点的树的最小节点
         * @param node
         * @return：返回删除后的子树的根
         */
        private Node removeMin(Node node) {
            if(node.left==null){//找到最小值的结点
                Node rigthNode = node.right;//null或者非空
                node.right=null;
                size--;
                return rigthNode;
            }
            node.left = removeMin(node.left);
            return node;
    
        }
    
        /**
         * 删除BST最大值
         * @return
         */
        public E removeMax(){
            E e = maxmum();
            root = removeMax(root);
            return e;
        }
    
    
        /**
         * 删除以node为根的子树的最大值
         * @param node
         * @return，返回删除后的树的根结点
         */
        private Node removeMax(Node node) {
            if(node.right==null){
                Node nodeLeft = node.left;
                node.left=null;
                size--;
                return nodeLeft;
            }
            node.right = removeMax(node.right);
            return node;
        }
    
        /**
         * (通过被删除结点的后继s,取代被删除结点的方式)删除任意一个结点e
         * @param e
         */
        public void removeBySuccessor(E e){
            root = removeBySuccessor(root,e);
        }
    
        /**
         * 通过被删除结点的后继s,取代被删除结点的方式，删除以node为根的树中e结点
         * @param node
         * @param e
         * @return：返回删除后的树的根
         */
        private Node removeBySuccessor(Node node, E e) {
            //没找到
            if(node==null){
                return null;
            }
    
            if(e.compareTo(node.e)<0){
                node.left = removeBySuccessor(node.left,e);
                return node;
            }else if(e.compareTo(node.e)>0){
                node.right=removeBySuccessor(node.right,e);
                return node;
            }else {//e==node.e,找到删除的结点
                //左子树空
                if(node.left==null){
                    Node rightNoe = node.right;
                    node.right=null;
                    size--;
                    return rightNoe;
                }else if(node.right==null){//右子树空
                    Node leftNode = node.left;
                    node.left=null;
                    size--;
                    return leftNode;
                }else{//都不空
                    //找到比待删除结点的右子树中最小的结点
                    //用这个结点删除待删除的结点
                    Node successor = minmum(node.right);
                    //removeMin里有一次size--
                    successor.right = removeMin(node.right);
                    successor.left = node.left;
                    node.left=node.right=null;
                    return successor;
                }
            }
        }
    
        /**
         * （通过被删除结点的前驱,取代被删除结点的方式）删除结点e
         * @param e
         */
        public void removeByPredicessor(E e){
            root = removeByPredicessor(root,e);
    
        }
    
        /**
         * 通过被删除结点的前驱,取代被删除结点的方式，删除以node为根的结点树中的e
         * @param node
         * @param e
         * @return:删除结点以后的树根
         */
        private Node removeByPredicessor(Node node, E e) {
            if(node==null){
                return null;
            }
    
            if(e.compareTo(node.e)<0){
                node.left = removeByPredicessor(node.left,e);
                return  node;
            }else if(e.compareTo(node.e)>0){
                node.right = removeByPredicessor(node.right,e);
                return node;
            }else{
                if(node.left==null){
                    Node right = node.right;
                    node.right=null;
                    size--;
                    return right;
                }else if(node.right==null){
                    Node left = node.left;
                    node.left=null;
                    size--;
                    return left;
                }else {
                    Node prediccessor = maxmum(node.left);
                    prediccessor.left = removeMax(node.left);
                    prediccessor.right = node.right;
                    node.left = node.right = null;
                    return prediccessor;
                }
            }
        }
    
        /**
         * 寻找e的最大下限
         * @param e
         * @return
         */
        public E floor(E e){
            return floor(root,e);
    
        }
    
        /**
         * 以node为根的树中寻找其最大下限
         * @param node
         * @param e
         * @return 返回最大下限的值
         */
        private E floor(Node node, E e) {
            if(node==null||e.compareTo(minmum(node).e)<0){
                return null;
            }
            if(node.e.compareTo(e)==0)
                return node.e;
            else if(e.compareTo(node.e)<0){
                return floor(node.left,e);
            }else{
                E temp = floor(node.right,e);
                if(temp!=null){
                    return temp;
                }else{
                    return node.e;
                }
            }
    
        }
    
        /**
         * 找e的最小上限
         * @param e
         * @return
         */
        public E ceil(E e){
            return ceil(root,e);
        }
    
        /**
         * 返回以node为根的树中，e的最小上限
         * @param node
         * @param e
         * @return
         */
        private E ceil(Node node, E e) {
            if(node==null||e.compareTo(maxmum(node).e)>0)
                return null;
            //相等，找到最小上限
            if(node.e.compareTo(e)==0)
                return node.e;
            //node的值比e小，e的上限在node的右子树
            else if(e.compareTo(node.e)>0){
                return ceil(node.right,e);
            }else{//node的值比e大，e的最小上限是node.e或者其左子树中有比node.e小，且大于e的结点
                E temp = ceil(node.left,e);
                if(temp==null)
                    return node.e;
                return temp;
            }
        }
    
        @Override
        public String toString() {
            StringBuilder ret = new StringBuilder();
            generateBSTString(root,0,ret);
            return ret.toString();
        }
    
        /**
         * 生成以node为根节点，深度为depth的描述二叉树的字符串 ret
         * @param node
         * @param depth
         * @param ret
         */
        private void generateBSTString(Node node, int depth, StringBuilder ret) {
            if(node==null){
                ret.append(generateDepthString(depth)+"null\n");
                return ;
            }
            ret.append(generateDepthString(depth)+node.e+"\n");
            generateBSTString(node.left,depth+1,ret);
            generateBSTString(node.right,depth+1,ret);
        }
    
        private String generateDepthString(int depth) {
            StringBuilder ret = new StringBuilder();
            for(int i=0;i<depth;i++){
                ret.append("--");
            }
            return ret.toString();
        }
    }