二分搜索樹java實(shí)現(xiàn)(遞歸與非遞歸)

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)//加到左子節(jié)點(diǎn)
        {
            node.left=add(node.left,e);
        }
        else if(e.compareTo(node.e)>0)//加到右子節(jié)點(diǎn)
        {
            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(){//后續(xù)遍歷
        postOrder(root,null);
    }

    public void postOrder(DiyPrintInterface<E> diyPrintInterface){//后續(xù)遍歷
        if(diyPrintInterface!=null)
            postOrder(root,diyPrintInterface);
    }

    private void postOrder(TreeNode node,DiyPrintInterface<E> diyPrintInterface){//后續(xù)遍歷
        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)//增加元素非遞歸實(shí)現(xiàn)
        {
            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()//非遞歸實(shí)現(xiàn)查詢?cè)?        {
            printNR(null);
        }

        public void printNR(DiyPrintInterface<E> diyPrintInterface)//非遞歸實(shí)現(xiàn)查詢?cè)?        {
            if(root==null)
                return;
            Stack<TreeNode> stack=new Stack<>();
            TreeNode current=root;
            while (current!=null||!stack.isEmpty())//使用的是中序遍歷的方式   ①
            {                                      //中序遍歷是先訪問左邊再訪問中間，最后訪問右邊
                while (current!=null)              //那么就先訪問最左邊，然后依次入棧
                {                                  //當(dāng)已經(jīng)到達(dá)了最左邊，則可以操作左邊了
                    stack.push(current);           //比如，最后這個(gè)current節(jié)點(diǎn)肯定為空
                    current=current.left;          //這時(shí)已經(jīng)是最左邊了
                }                                  //那么讓他出棧
                if(!stack.isEmpty())               //則這個(gè)棧頂元素就是最左邊的節(jié)點(diǎn)
                {                                  //打印當(dāng)前節(jié)點(diǎn)
                    current=stack.pop();           //當(dāng)前節(jié)點(diǎn)是否還有右節(jié)點(diǎn)，有，把當(dāng)前節(jié)點(diǎn)右節(jié)點(diǎn)進(jìn)行同樣的操作  ①
                    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 {//棧不空,節(jié)點(diǎn)空
                    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就是最小的節(jié)點(diǎn)
            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;
        }
    }
}
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

友情鏈接更多精彩內(nèi)容