Java數(shù)據(jù)結(jié)構(gòu)之二叉搜索樹(shù)實(shí)例分析

這篇文章主要介紹“Java數(shù)據(jù)結(jié)構(gòu)之二叉搜索樹(shù)實(shí)例分析”，在日常操作中，相信很多人在Java數(shù)據(jù)結(jié)構(gòu)之二叉搜索樹(shù)實(shí)例分析問(wèn)題上存在疑惑，小編查閱了各式資料，整理出簡(jiǎn)單好用的操作方法，希望對(duì)大家解答”Java數(shù)據(jù)結(jié)構(gòu)之二叉搜索樹(shù)實(shí)例分析”的疑惑有所幫助！接下來(lái)，請(qǐng)跟著小編一起來(lái)學(xué)習(xí)吧！

性質(zhì)

二叉搜索樹(shù)或者是一棵空樹(shù)，或者是具有下列性質(zhì)的一棵二叉樹(shù)，如果當(dāng)前節(jié)點(diǎn)具有左子樹(shù)，則左子樹(shù)上的每一個(gè)節(jié)點(diǎn)值均小于等于當(dāng)前節(jié)點(diǎn)值，如果當(dāng)前節(jié)點(diǎn)具有右子樹(shù)，則右子樹(shù)上的每一個(gè)節(jié)點(diǎn)值均大于等于當(dāng)前節(jié)點(diǎn)值。依據(jù)這個(gè)性質(zhì)，當(dāng)我們前序遍歷二叉搜索樹(shù)的時(shí)候，得到的序列應(yīng)該是從小到大的非遞減序列。同時(shí)搜索指定值時(shí)，只需要與當(dāng)前節(jié)點(diǎn)比較，根據(jù)相對(duì)大小在左子樹(shù)或者右子樹(shù)上進(jìn)行搜索。

實(shí)現(xiàn)

根據(jù)二叉搜索樹(shù)的性質(zhì)我們接下來(lái)需要實(shí)現(xiàn)插入節(jié)點(diǎn)，查詢節(jié)點(diǎn)，刪除節(jié)點(diǎn)功能。

節(jié)點(diǎn)結(jié)構(gòu)

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode() {
    }

    public TreeNode(int val) {
        this.val = val;
    }

    public TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

初始化

這里我們假設(shè)所有節(jié)點(diǎn)值大于0，初始化一個(gè)頭節(jié)點(diǎn)。ps：對(duì)于樹(shù)，鏈表這類數(shù)據(jù)結(jié)構(gòu)，為了使第一個(gè)節(jié)點(diǎn)操作與其他節(jié)點(diǎn)保持一致，方便操作，常見(jiàn)的方法是添加一個(gè)額外的頭節(jié)點(diǎn)，指向第一個(gè)節(jié)點(diǎn)。

TreeNode head;
    private void init() {
        //添加一個(gè)頭節(jié)點(diǎn)
        head = new TreeNode(-1);
    }

插入節(jié)點(diǎn)

從頭節(jié)點(diǎn)開(kāi)始我們遍歷二叉搜索樹(shù)，如果當(dāng)前節(jié)點(diǎn)值小于等于插入節(jié)點(diǎn)值，則插入節(jié)點(diǎn)在當(dāng)前節(jié)點(diǎn)的右子樹(shù)上，否則在左子樹(shù)上，一直深度遍歷知道當(dāng)前節(jié)點(diǎn)的右子樹(shù)（左子樹(shù)）為空，則插入。

/**
     * 插入新節(jié)點(diǎn)，假設(shè)新節(jié)點(diǎn)均大于0
     * @param val 插入節(jié)點(diǎn)值
     * @return 插入的節(jié)點(diǎn)
     */
    public TreeNode insert(int val) {
        TreeNode temp = head;
        while (true) {
            if (temp.val < val) {
                //val應(yīng)該在右子樹(shù)上
                if (null != temp.right) {
                    temp = temp.right;
                    continue;
                } else {
                    temp.right = new TreeNode(val);
                    return temp.right;
                }
            }
            //應(yīng)該在左子樹(shù)上
            if (null != temp.left) {
                temp = temp.left;
                continue;
            }
            temp.left = new TreeNode(val);
            return temp.left;
        }
    }

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

查找節(jié)點(diǎn)的步驟其實(shí)在插入節(jié)點(diǎn)的時(shí)候已經(jīng)有體現(xiàn)，其實(shí)就是將查找值與當(dāng)前節(jié)點(diǎn)比較，大于當(dāng)前節(jié)點(diǎn)走右子樹(shù)，小于當(dāng)前節(jié)點(diǎn)走左子樹(shù)，直到值匹配返回節(jié)點(diǎn)，或者沒(méi)有找到返回null。ps：這里為了后面方便實(shí)現(xiàn)刪除，同時(shí)返回了當(dāng)前節(jié)點(diǎn)以及當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)，這里使用了commons-lang3包下的Pair工具。

/**
     * 搜索節(jié)點(diǎn)值
     * @param val
     * @return
     */
    public Pair<TreeNode, TreeNode> find(int val) {
        TreeNode temp = head.right;
        TreeNode parent = head;
        while (null != temp) {
            if (temp.val == val) {
                return Pair.of(temp, parent);
            }
            parent = temp;
            if (temp.val < val) {
                //在右子樹(shù)上
                temp = temp.right;
                continue;
            }
            temp = temp.left;
        }
        return null;
    }

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

刪除節(jié)點(diǎn)時(shí)候我們需要先找到刪除節(jié)點(diǎn)的位置，然后做對(duì)應(yīng)操作。有三種情況：

1.如果刪除的是葉子節(jié)點(diǎn)直接刪除

2.如果刪除的節(jié)點(diǎn)只有左子樹(shù)或者右子樹(shù)，則直接將左子樹(shù)或者右子樹(shù)節(jié)點(diǎn)放在刪除節(jié)點(diǎn)位置

3.如果刪除節(jié)點(diǎn)同時(shí)有左子樹(shù)和右子樹(shù)，則將右子樹(shù)節(jié)點(diǎn)放在原來(lái)節(jié)點(diǎn)位置，將左子樹(shù)放在右子樹(shù)最左邊節(jié)點(diǎn)左子樹(shù)上（反之將左子樹(shù)放在原來(lái)節(jié)點(diǎn)位置，右子樹(shù)放在左子樹(shù)最右邊節(jié)點(diǎn)右子樹(shù)上也可）

/**
     * 1.如果刪除的是葉子節(jié)點(diǎn)直接刪除，
     * 2.如果刪除的節(jié)點(diǎn)只有左子樹(shù)或者右子樹(shù)，則直接將左子樹(shù)或者右子樹(shù)節(jié)點(diǎn)放在刪除節(jié)點(diǎn)位置
     * 3.如果刪除節(jié)點(diǎn)同時(shí)右左子樹(shù)和右子樹(shù)，則將右子樹(shù)節(jié)點(diǎn)放在原來(lái)節(jié)點(diǎn)位置，將左子樹(shù)放在右子樹(shù)最左邊節(jié)點(diǎn)左子樹(shù)上
     * @param val
     */
    public void delete(int val) {
        //找到刪除節(jié)點(diǎn)，刪除節(jié)點(diǎn)父節(jié)點(diǎn)
        Pair<TreeNode, TreeNode> curAndParent = this.find(val);
        TreeNode cur = curAndParent.getLeft();
        TreeNode parent = curAndParent.getRight();
        //記錄刪除當(dāng)前節(jié)點(diǎn)后，當(dāng)前節(jié)點(diǎn)位置放置哪個(gè)節(jié)點(diǎn)
        TreeNode changed;
        if (null == cur.left && null == cur.right) {
            changed = null;
        } else if (null != cur.left && null != cur.right) {
            TreeNode tempRight = cur.right;
            while (null != tempRight.left) {
                //找到最左側(cè)節(jié)點(diǎn)
                tempRight = tempRight.left;
            }
            tempRight.left = cur.left;
            changed = cur.right;
        } else if (null != cur.left) {
            changed = cur.left;
        } else {
            changed = cur.right;
        }
        if (parent.left == cur) {
            parent.left = changed;
            return;
        }
        parent.right = changed;
    }

到此，關(guān)于“Java數(shù)據(jù)結(jié)構(gòu)之二叉搜索樹(shù)實(shí)例分析”的學(xué)習(xí)就結(jié)束了，希望能夠解決大家的疑惑。理論與實(shí)踐的搭配能更好的幫助大家學(xué)習(xí)，快去試試吧！若想繼續(xù)學(xué)習(xí)更多相關(guān)知識(shí)，請(qǐng)繼續(xù)關(guān)注億速云網(wǎng)站，小編會(huì)繼續(xù)努力為大家?guī)?lái)更多實(shí)用的文章！