Java實(shí)現(xiàn)二叉查找樹的增刪查詳解

更新時(shí)間：2022年06月28日 11:30:33 作者：WX7251

二叉查找樹（ADT）是一個(gè)具有對于樹種的某個(gè)節(jié)點(diǎn)X,它的左節(jié)點(diǎn)都比X小，它的右節(jié)點(diǎn)都比X大的二叉樹。本文將用Java實(shí)現(xiàn)二叉查找樹的增刪查，需要的可以參考一下

定義

二叉查找樹（ADT）是一個(gè)具有對于樹種的某個(gè)節(jié)點(diǎn)X,它的左節(jié)點(diǎn)都比X小，它的右節(jié)點(diǎn)都比X大的二叉樹。如下就是一個(gè)符合

要求的二叉查找樹：

增加節(jié)點(diǎn)

1.定義節(jié)點(diǎn)類:

class Node{
    int val;
    Node left;
    Node right;
    public Node(int val){
        this.val=val;
    }
}

2.插入元素

我們采用遞歸的方法：

1.判斷與根節(jié)點(diǎn)是否相同，相同無需操作

2.比根元素小往左邊查找，左節(jié)點(diǎn)不存在的話則作為左節(jié)點(diǎn)插入即可

3.比根元素大往右邊查找，右節(jié)點(diǎn)不存在的話則作為右節(jié)點(diǎn)插入即可

代碼實(shí)現(xiàn)如下：

Node root;
 
    /**
     * 添加元素
     * @param val
     */
    public void add(int val){
        if(root==null){
            root=new Node(val);
            return;
        }
        addNode(val,root);
    }
    private void addNode(int val,Node root){
        if(root==null || root.val==val){
            return;
        }
        if(root.val>val){
            if(root.left==null){
                root.left=new Node(val);
            }else {
                addNode(val,root.left);
            }
        }else {
            if(root.right==null){
                root.right=new Node(val);
            }else {
                addNode(val,root.right);
            }
        }
    }

查詢節(jié)點(diǎn)

我們采用遞歸的方法：

1.判斷與根節(jié)點(diǎn)是否相同，相同則返回true

2.比根元素小往左邊查找，左節(jié)點(diǎn)為null則返回false表示不存在

3.比根元素大往右邊查找，右節(jié)點(diǎn)為null則返回false表示不存在

代碼實(shí)現(xiàn)如下:

/**
     * 判斷指定值是否存在
     * @param val 指定值
     * @return true--存在   false--不存在
     */
    public boolean findVale(int val){
        return isExit(root,val);
    }
 
    private boolean isExit(Node node,int val){
        if(node==null){
            return false;
        }
        if(node.val==val){
            return true;
        }else if(node.val>val){
            return isExit(node.left,val);
        }else {
            return isExit(node.right,val);
        }
    }

刪除節(jié)點(diǎn)

刪除元素時(shí)要判斷元素的情況：

1.刪除的元素沒有葉子節(jié)點(diǎn)，直接刪除，如刪除值為1的節(jié)點(diǎn)，雖然平衡性不是太好，但是還是符合二叉查找樹的特性

2.刪除的元素只有一個(gè)節(jié)點(diǎn)，刪除元素并將指針指向其子節(jié)點(diǎn) ，如刪除值為4的節(jié)點(diǎn):

3.刪除的元素有左右兩個(gè)節(jié)點(diǎn)，從右節(jié)點(diǎn)中找出大于該節(jié)點(diǎn)的最小節(jié)點(diǎn)，作為新的節(jié)點(diǎn)A,如刪除節(jié)點(diǎn)值為2的節(jié)點(diǎn):

代碼實(shí)現(xiàn)如下:

/**
     * 刪除元素
     * 1.刪除的元素沒有葉子節(jié)點(diǎn)，直接刪除
     * 2.刪除的元素只有一個(gè)節(jié)點(diǎn)，刪除元素并將指針指向其子節(jié)點(diǎn)
     * 3.刪除的元素有兩個(gè)節(jié)點(diǎn)，從右節(jié)點(diǎn)中找出大于該元素的最小值，作為新的節(jié)點(diǎn)
     * @param val
     */
    public void deleteElement(int val){
        deleteElement(null,root,val,true);
    }
 
    /**
     * 刪除元素
     * @param prev 父節(jié)點(diǎn)
     * @param root 當(dāng)前節(jié)點(diǎn)
     * @param val  刪除值
     * @param isright  是否是右節(jié)點(diǎn)
     */
    private void deleteElement(Node prev,Node root,int val,boolean isright){
        if(root.val==val){
            //刪除的元素沒有葉子節(jié)點(diǎn)，直接刪除
            if(root.left==null &&  root.right==null){
                changeValue(prev,null,isright);
            }else if(root.left!=null &&  root.right!=null){
                //3.刪除的元素有兩個(gè)節(jié)點(diǎn)，從右節(jié)點(diǎn)中找出大于該元素的最小值，作為新的節(jié)點(diǎn)
                changeValue(prev,new Node(findMinGt(root,root.right,true)),isright);
                if(prev==null){
                    //對于頭結(jié)點(diǎn)的刪除特殊處理
                    prev=this.root;
                    prev.left=root.left;
                    prev.right=root.right;
                    return;
                }
                if(isright){
                    prev.right.right=root.right;
                    prev.right.left=root.left;
                }else {
                    prev.left.right=root.right;
                    prev.left.left=root.left;
                }
            }//刪除的元素只有一個(gè)節(jié)點(diǎn)，刪除元素并將指針指向其子節(jié)點(diǎn)
            else if(root.left!=null){
                changeValue(prev,root.left,isright);
            }else {
                changeValue(prev,root.right,isright);
            }
            return;
        }
        if(root.val>val){
            deleteElement(root,root.left,val,false);
        }else{
            deleteElement(root,root.right,val,true);
        }
    }
    //改變元素值
    private void changeValue(Node prev,Node value,boolean isright){
        if(prev==null){
            root=value;
            return;
        }
        if(isright){
            prev.right=value;
        }else {
            prev.left=value;
        }
    }
    //尋找大于根節(jié)點(diǎn)的最小值
    private int findMinGt(Node prev,Node root,boolean isRight){
        if(root.left==null && root.right==null){
            changeValue(prev,null,isRight);
            return root.val;
        }
        if(root.left==null){
            changeValue(prev,null,isRight);
            return root.val;
        }
        return findMinGt(root,root.left,false);
    }

到此這篇關(guān)于Java實(shí)現(xiàn)二叉查找樹的增刪查詳解的文章就介紹到這了,更多相關(guān)Java二叉查找樹增刪查內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: