美文网首页
二分搜索树java实现(递归与非递归)

二分搜索树java实现(递归与非递归)

作者: 汇源可乐 | 来源:发表于2020-07-13 19:54 被阅读0次
    package cn.ololee.bstnew;
    import sun.reflect.generics.tree.Tree;
    import java.util.HashMap;
    import java.util.LinkedList;
    import java.util.Queue;
    import java.util.Stack;
    public class BST<E extends  Comparable<E>> {
        class TreeNode
        {
            E e;
            TreeNode left;
            TreeNode right;
            int height;
            int count;
    
            public TreeNode(E e) {
                this.e = e;
                left=right=null;
                count=1;
                height=0;
            }
        }
    
        public interface DiyPrintInterface<E extends Comparable<E>>{
            void print(E e,int count);
        }
    
        private TreeNode root;
        private int size;
        private int nonrepeatSize=0;
        public NRImpl NR=new NRImpl();
    
        public void add(E e)
        {
            root=add(root,e);
        }
    
        private TreeNode add(TreeNode node,E e)
        {
            if(node==null)
            {
                node=new TreeNode(e);
                size++;
                nonrepeatSize++;
                return node;
            }
            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);
            }
            else {
                node.count++;
                size++;
            }
            return node;
        }
    
        public void print()//中序遍历
        {
            print(root,null);
        }
    
        public void diyPrint(DiyPrintInterface diyPrintInterface)//中序遍历
        {
            if(diyPrintInterface!=null)
                print(root,diyPrintInterface);
        }
    
        private void print(TreeNode node,DiyPrintInterface diyPrintInterface)//中序遍历
        {
            if(node==null)
                return;
            print(node.left,diyPrintInterface);
            if(diyPrintInterface!=null)
                diyPrintInterface.print(node.e,node.count);
            else
                print(node.e,node.count);
            print(node.right,diyPrintInterface);
        }
    
        private void print(E e,int count)
        {
            if(count!=0)
            {
                for (int i = 0; i < count; i++) {
                    System.out.print(e+",");
                }
            }
            else
                System.out.print(e+",");
        }
    
        public void preOrder()//前序遍历
        {
            preOrder(root,null);
        }
    
        public void preOrder(DiyPrintInterface<E> diyPrintInterface)//前序遍历
        {
            if(diyPrintInterface!=null)
                preOrder(root,diyPrintInterface);
        }
    
        private void preOrder(TreeNode node,DiyPrintInterface<E> diyPrintInterface)//前序遍历
        {
            if(node==null)
                return;
            if(diyPrintInterface!=null)
            {
                diyPrintInterface.print(node.e,node.count);
            }
            else
                print(node.e,node.count);
            preOrder(node.left,diyPrintInterface);
            preOrder(node.right,diyPrintInterface);
        }
    
        public void inOrder()
        {
            print(root,null);
        }
    
        public void inOrder(DiyPrintInterface<E> diyPrintInterface)
        {
            if(diyPrintInterface!=null)
                print(root,diyPrintInterface);
        }
    
        public void postOrder(){//后续遍历
            postOrder(root,null);
        }
    
        public void postOrder(DiyPrintInterface<E> diyPrintInterface){//后续遍历
            if(diyPrintInterface!=null)
                postOrder(root,diyPrintInterface);
        }
    
        private void postOrder(TreeNode node,DiyPrintInterface<E> diyPrintInterface){//后续遍历
            if(node==null)
                return;
            postOrder(node.left,diyPrintInterface);
            postOrder(node.right,diyPrintInterface);
            if(diyPrintInterface!=null)
                diyPrintInterface.print(node.e,node.count);
            else
                print(node.e,node.count);
        }
    
        public boolean contains(E e)
        {
          return  contains(root,e);
        }
    
        private boolean contains(TreeNode node,E e)
        {
            if(node==null)
                return false;
            int compare=e.compareTo(node.e);
            if(compare==0)
                return true;
            else if(compare<0)
                return contains(node.left,e);
            else
                return contains(node.right,e);
        }
    
        public E getMin()
        {
            if(size==0)
                throw new IllegalArgumentException("BST is empty");
            return getMin(root).e;
        }
    
        private TreeNode getMin(TreeNode node)
        {
            if(node.left==null)
                return node;
           return getMin(node.left);
        }
    
        public E getMax()
        {
            if(size==0)
                throw new IllegalArgumentException("BST is empty");
            return getMax(root);
        }
    
        private E getMax(TreeNode node)
        {
            if(node.right==null)
                return node.e;
            return getMax(node.right);
        }
    
        public E deleteMin()
        {
            E ret=getMin();
            root=deleteMin(root);
            return ret;
        }
    
        private TreeNode deleteMin(TreeNode node)
        {
            if(node.left==null) {
                TreeNode right=node.right;
                node.right=null;
                resize(right.count);
                return right;
            }
            node.left=deleteMin(node.left);
            return node;
        }
    
        public E deleteMax()
        {
            E ret=getMax();
            root=deleteMax(root);
            return ret;
        }
    
        private TreeNode deleteMax(TreeNode node)
        {
            if(node.right==null)
            {
                TreeNode left=node.left;
                node.left=null;
                resize(left.count);
                return left;
            }
            node.right=deleteMax(node.right);
            return node;
        }
    
        public void delete(E e)
        {
            root=delete(root,e);
        }
    
        private TreeNode delete(TreeNode node,E e)
        {
            if(node==null)
                return null;
            int compare=e.compareTo(node.e);
            if(compare<0)
            {
                node.left=delete(node.left,e);
            }
            else if(compare>0)
            {
                node.right=delete(node.right,e);
            }
            else {
                if(node.left==null)
                {
                    TreeNode right=node.right;
                    node.right=null;
                    size-=node.count;
                    nonrepeatSize--;
                    return right;
                }
                else if(node.right==null)
                {
                    TreeNode left=node.left;
                    node.left=null;
                    size-=node.count;
                    nonrepeatSize--;
                    return left;
                }
                else {
                    TreeNode rightMin=getMin(node.right);
                    node.e=rightMin.e;
                    node.count=rightMin.count;
                    node.right=deleteMin(node.right);
                }
            }
            return node;
        }
    
        public int getSize() {
            return size;
        }
    
        public int getNonrepeatSize() {
            return nonrepeatSize;
        }
    
        private void resize(int count)
        {
            size-=count;
        }
    
        public int getHeight()
        {
            return getHeight(root,0);
        }
    
        public int getHeight(TreeNode node,int depth)
        {
            if(node==null)
            {
                return depth;
            }
            return Math.max(getHeight(node.left,depth+1),getHeight(node.right,depth+1));
        }
    
        public void levelOrder()
        {
            levelOrder(null);
        }
    
        public void levelOrder(DiyPrintInterface<E> diyPrintInterface)
        {
            if (root==null)
                return;
            Queue<TreeNode> queue=new LinkedList<>();
            if(root!=null)
            {
                queue.add(root);
            }
            TreeNode current=root;
            while (!queue.isEmpty())
            {
                current=queue.poll();
                if(diyPrintInterface!=null)
                    diyPrintInterface.print(current.e,current.count);
                else
                    print(current.e,current.count);
                if(current.left!=null)
                    queue.add(current.left);
                if(current.right!=null)
                    queue.add(current.right);
            }
        }
    
    
        class NRImpl
        {
            public void addNR(E e)//增加元素非递归实现
            {
                if (root==null)
                {
                    size++;
                    nonrepeatSize++;
                    root=new TreeNode(e);
                    return;
                }
                TreeNode current=root;
                while (current!=null)
                {
                    int compare=e.compareTo(current.e);
                    if(compare<0)
                    {
                        if(current.left==null)
                        {
                            size++;
                            nonrepeatSize++;
                            current.left=new TreeNode(e);
                            return;
                        }
                        else
                            current=current.left;
                    }
                    else if(compare>0)
                    {
                        if(current.right==null)
                        {
                            size++;
                            nonrepeatSize++;
                            current.right=new TreeNode(e);
                            return;
                        }
                        else
                            current=current.right;
                    }
                    else {
                        current.count++;
                        size++;
                        return;
                    }
                }
            }
    
            public void printNR()//非递归实现查询元素
            {
                printNR(null);
            }
    
            public void printNR(DiyPrintInterface<E> diyPrintInterface)//非递归实现查询元素
            {
                if(root==null)
                    return;
                Stack<TreeNode> stack=new Stack<>();
                TreeNode current=root;
                while (current!=null||!stack.isEmpty())//使用的是中序遍历的方式   ①
                {                                      //中序遍历是先访问左边再访问中间,最后访问右边
                    while (current!=null)              //那么就先访问最左边,然后依次入栈
                    {                                  //当已经到达了最左边,则可以操作左边了
                        stack.push(current);           //比如,最后这个current节点肯定为空
                        current=current.left;          //这时已经是最左边了
                    }                                  //那么让他出栈
                    if(!stack.isEmpty())               //则这个栈顶元素就是最左边的节点
                    {                                  //打印当前节点
                        current=stack.pop();           //当前节点是否还有右节点,有,把当前节点右节点进行同样的操作  ①
                        if(diyPrintInterface!=null)
                        {
                            diyPrintInterface.print(current.e,current.count);
                        }
                        else
                            print(current.e,current.count);
                        current=current.right;
                    }
                }
            }
    
            public void preOrderNR(){
                preOrderNR(null);
            }
    
            public void preOrderNR(DiyPrintInterface<E> diyPrintInterface) {
                if(root==null)
                    return;
                Stack<TreeNode> stack=new Stack<>();
                TreeNode current=root;
                //前序遍历,先中间再左边再右边
              while (current!=null||!stack.isEmpty())
              {
                 if(current!=null)
                 {
                     if(diyPrintInterface!=null)
                         diyPrintInterface.print(current.e,current.count);
                     else
                         print(current.e,current.count);
                     if(current.right!=null)
                         stack.push(current.right);
                     current=current.left;
                 }
                 else
                     current=stack.pop();
              }
            }
    
            public void inOrderNR(){
                printNR();
            }
    
            public void inOrderNR(DiyPrintInterface<E> diyPrintInterface){
                printNR(diyPrintInterface);
            }
    
            public void postOrderNR(){
                postOrderNR(null);
            }
    
            public void postOrderNR(DiyPrintInterface<E> diyPrintInterface){
                if(root==null)
                    return;
                TreeNode current=root;
                Stack<TreeNode> stack=new Stack<>();
                HashMap<E,Integer> map=new HashMap<>();
                while (current!=null||!stack.isEmpty())
                {
                    if(current!=null)
                    {
                        stack.push(current);
                        map.put(current.e,1);
                        current=current.left;
                    }
                    else {//栈不空,节点空
                        current=stack.peek();
                        if(map.get(current.e)==2)
                        {
                            stack.pop();
                            if(diyPrintInterface!=null)
                                diyPrintInterface.print(current.e,current.count);
                            else
                                print(current.e,current.count);
                            current=null;
                        }
                        else {
                            map.put(current.e,2);
                            current=current.right;
                        }
                    }
                }
            }
    
            public boolean containsNR(E e)
            {
                if(root==null)
                    return false;
                TreeNode current=root;
                int compare;
                while (current!=null)
                {
                    compare=e.compareTo(current.e);
                    if(compare==0)
                        return true;
                    else if(compare<0)
                        current=current.left;
                    else
                        current=current.right;
                }
                return false;
            }
    
            public E getMinNR(){
                TreeNode current=root;
                while (current.left!=null)
                    current=current.left;
                return current.e;
            }
    
            public E getMaxNR() {
                TreeNode current=root;
                while (current.right!=null)
                    current=current.right;
                return current.e;
            }
    
            public E deleteMinNR()
            {
                TreeNode min=root,parent = root;
                while (min.left!=null) {
                    parent=min;
                    min=min.left;
                }
                //min就是最小的节点
                E ret=min.e;
                parent.left=min.right;
                min.right=null;
                resize(min.count);
                return ret;
            }
    
            public E deleteMaxNR()
            {
                TreeNode max=root,parent=root;
                while (max.right!=null)
                {
                    parent=max;
                    max=max.right;
                }
                E ret=max.e;
                parent.right=max.left;
                max.left=null;
                resize(max.count);
                return ret;
            }
        }
    }
    

    相关文章

      网友评论

          本文标题:二分搜索树java实现(递归与非递归)

          本文链接:https://www.haomeiwen.com/subject/mjuzcktx.html