hello, everyone. Long time no see. 本期文章，我們主要講解一下二叉樹(shù)的相關(guān)概念，順便也把搜索二叉樹(shù)（也叫二叉排序樹(shù)）講一下。我們直接進(jìn)入正題吧！GitHub源碼鏈接

一、二叉樹(shù)的概念

為什么要使用二叉樹(shù)？

為什么要用到樹(shù)呢?因?yàn)樗ǔ＝Y(jié)合了另外兩種數(shù)據(jù)結(jié)構(gòu)的優(yōu)點(diǎn):一種是有序數(shù)組，另一種是鏈表。在樹(shù)中查找數(shù)據(jù)項(xiàng)的速度和在有序數(shù)組中查找一樣快，并且插入數(shù)據(jù)項(xiàng)和刪除數(shù)據(jù)項(xiàng)的速度也和鏈表一樣。下面，我們先來(lái)稍微思考一下這些話題，然后再深入地研究樹(shù)的細(xì)節(jié)。

在有序數(shù)組中插入數(shù)據(jù)太慢了，而在鏈表中查找數(shù)據(jù)也太慢了。所以到后來(lái)就有了二叉樹(shù)這種數(shù)據(jù)結(jié)構(gòu)。

樹(shù)是什么？

在深入講解二叉樹(shù)前，我們先簡(jiǎn)單地認(rèn)識(shí)一下樹(shù)這個(gè)概念。樹(shù)是由若干個(gè)節(jié)點(diǎn)和邊組合而成，例如，可以把城市看成節(jié)點(diǎn)，將各個(gè)城市之間的交通路線看成邊。當(dāng)然說(shuō)的更準(zhǔn)確一點(diǎn)，這個(gè)例子更應(yīng)該是屬于圖的范疇內(nèi)，關(guān)于圖的相關(guān)知識(shí)點(diǎn)。我們到后面再來(lái)討論。如下圖，就是一棵樹(shù)。

樹(shù)的相關(guān)術(shù)語(yǔ)！

​ 如下圖所示

根節(jié)點(diǎn)

​ 樹(shù)最頂端的節(jié)點(diǎn)稱(chēng)為根節(jié)點(diǎn)，一棵樹(shù)只有一個(gè)根節(jié)點(diǎn)，一般也是整棵樹(shù)遍歷的開(kāi)始。

路徑

​ 設(shè)想一下，從樹(shù)中的一個(gè)節(jié)點(diǎn)，沿著邊走向另一個(gè)節(jié)點(diǎn)，所經(jīng)過(guò)的節(jié)點(diǎn)順序排列就稱(chēng)為“路徑”。

父節(jié)點(diǎn)

​ 就像這個(gè)名稱(chēng)一樣，在二叉樹(shù)中扮演“父親”的角色， 在二叉樹(shù)中的每一個(gè)節(jié)點(diǎn)（除了根節(jié)點(diǎn)），都有一個(gè)邊向上可以找到該節(jié)點(diǎn)的”父節(jié)點(diǎn)“。

子節(jié)點(diǎn)

​ 每個(gè)節(jié)點(diǎn)都可能有一條或多條邊向下連接其他節(jié)點(diǎn)，下面的這些節(jié)點(diǎn)就稱(chēng)為它的“子節(jié)點(diǎn)”。

葉節(jié)點(diǎn)

​ 沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)稱(chēng)為“葉子節(jié)點(diǎn)”或簡(jiǎn)稱(chēng)“葉節(jié)點(diǎn)”。樹(shù)中只有一個(gè)根，但是可以有很多葉節(jié)點(diǎn)。

子樹(shù)

​ 每個(gè)節(jié)點(diǎn)都可以作為“子樹(shù)”的根，它和它所有的子節(jié)點(diǎn)，子節(jié)點(diǎn)的子節(jié)點(diǎn)等都含在子樹(shù)中。就像家族中那樣，一個(gè)節(jié)點(diǎn)的子樹(shù)包含它所有的子孫。

訪問(wèn)

​ 當(dāng)程序控制流程到達(dá)某個(gè)節(jié)點(diǎn)時(shí)，就稱(chēng)為“訪問(wèn)”這個(gè)節(jié)點(diǎn)，通常是為了在這個(gè)節(jié)點(diǎn)處執(zhí)行某種操作，例如查看節(jié)點(diǎn)某個(gè)數(shù)據(jù)字段的值或顯示節(jié)點(diǎn)。如果僅僅是在路徑上從某個(gè)節(jié)點(diǎn)到另一個(gè)節(jié)點(diǎn)時(shí)經(jīng)過(guò)了一個(gè)節(jié)點(diǎn)，不認(rèn)為是訪問(wèn)了這個(gè)節(jié)點(diǎn)。

層（深度）

​ 也就相當(dāng)于我們?nèi)艘粯?，我們這一輩人，就可以看做一層。而爸媽那一輩，又是另外一層。

關(guān)鍵字

​ 如圖中所示，每個(gè)節(jié)點(diǎn)里，有一個(gè)數(shù)值，這個(gè)數(shù)值我們就稱(chēng)為關(guān)鍵字。

滿二叉樹(shù)

​ 在一顆二叉樹(shù)中，如果所有分支節(jié)點(diǎn)都存在左子樹(shù)和右子樹(shù)，并且所有的葉節(jié)點(diǎn)都在同一層上，這樣的二叉樹(shù)，稱(chēng)為滿二叉樹(shù)。如上圖所示。

完全二叉樹(shù)

​ 對(duì)一顆具有n個(gè)節(jié)點(diǎn)的二叉樹(shù)按從上至下，從左到右的順序編號(hào)，如果編號(hào)為i(1 <= i <= n)的節(jié)點(diǎn)與同樣深度的滿二叉樹(shù)中編號(hào)為i的節(jié)點(diǎn)在二叉樹(shù)中的位置完全一樣，則這棵樹(shù)就被稱(chēng)為完全二叉樹(shù)。

從字面上的意思來(lái)看，滿二叉樹(shù)一定是完全二叉樹(shù)，而完全二叉樹(shù)不一定是滿的。如下圖：

二叉樹(shù)的五大性質(zhì)

1.在二叉樹(shù)的第i層上，最多有2（i-1）的次方個(gè)節(jié)點(diǎn)。例如：第三層上，最多也就有4個(gè)節(jié)點(diǎn)。

2.深度為k的二叉樹(shù)，最多有2k的次方 - 1個(gè)節(jié)點(diǎn)。 例如：深度為3的二叉樹(shù)，最多也就只有7個(gè)節(jié)點(diǎn)。

3.對(duì)任何一顆二叉樹(shù)，葉子節(jié)點(diǎn)的總數(shù)記為n0，度為2的節(jié)點(diǎn)的總數(shù)記為n2。則n0 = n2 + 1。解釋?zhuān)憾葹?的節(jié)點(diǎn)，指的是該節(jié)點(diǎn)左右子節(jié)點(diǎn)都有的情況，我們稱(chēng)為度為2的節(jié)點(diǎn)。那如果左右子節(jié)點(diǎn)，有且僅有一個(gè)的時(shí)候，我們就叫度為1的節(jié)點(diǎn)。

4.具有n個(gè)節(jié)點(diǎn)的完全二叉樹(shù)的深度為 log2n + 1。（此處的對(duì)數(shù) 向下取整）

由滿二叉樹(shù)的定義我們可以知道，深度為k的 滿二叉樹(shù)的節(jié)點(diǎn)數(shù)n一定等于 2k的次方 - 1。因?yàn)檫@是最多的節(jié)點(diǎn)數(shù)，再由這個(gè)公式，我們就可以倒推出

k = log2(n + 1)。比如節(jié)點(diǎn)數(shù)為8的滿二叉樹(shù)，深度就是3。

5.如果對(duì)一顆有n個(gè)節(jié)點(diǎn)的完全二叉樹(shù)的節(jié)點(diǎn)，按照從上至下，從左到右，對(duì)每一個(gè)節(jié)點(diǎn)進(jìn)行編號(hào)：則有如下性質(zhì)：

​ 1). 如果i=1，則該節(jié)點(diǎn)就是這棵樹(shù)的根結(jié)點(diǎn)。若i不等于1，則i節(jié)點(diǎn)的父節(jié)點(diǎn)就是i / 2節(jié)點(diǎn)。

​ 2). 如果2i > n，(n為整棵樹(shù)的總節(jié)點(diǎn)數(shù))，則i節(jié)點(diǎn)沒(méi)有左子節(jié)點(diǎn)，反之就是2i就是左子節(jié)點(diǎn)。

​ 3). 如果2i + 1 > n，(n為整棵樹(shù)的總節(jié)點(diǎn)數(shù))，則i節(jié)點(diǎn)沒(méi)有右子節(jié)點(diǎn)，反之就是2i + 1就是右子節(jié)點(diǎn)。

二、搜索二叉樹(shù)

上面我們講解完了二叉樹(shù)的一些基本的概念，現(xiàn)在我們繼續(xù)來(lái)看下一個(gè)知識(shí)點(diǎn)：搜索二叉樹(shù)。

定義：一個(gè)節(jié)點(diǎn)的左子節(jié)點(diǎn)的關(guān)鍵字值小于這個(gè)節(jié)點(diǎn)，右子節(jié)點(diǎn)的關(guān)鍵字值大于或等于這個(gè)父節(jié)點(diǎn)。如下圖，就是一個(gè)搜索二叉樹(shù)。

可能會(huì)有同學(xué)已經(jīng)發(fā)現(xiàn)了一個(gè)規(guī)律，那就是搜索二叉樹(shù)的中序遍歷的結(jié)果就是一個(gè)升序的。所以在判斷一顆樹(shù)是不是搜索二叉樹(shù)時(shí)，就可以從這里入手。

知道了定義，我們就可以根據(jù)定義來(lái)實(shí)現(xiàn)相應(yīng)的代碼。

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

class TreeNode {
    int val; //關(guān)鍵字
    TreeNode left; //左子節(jié)點(diǎn)
    TreeNode right; //右子節(jié)點(diǎn)
    
    public TreeNode(int val) {
        this.val = val;
    }
}

搜索二叉樹(shù)的整體框架結(jié)構(gòu)

public class BST {
    private TreeNode root; //根結(jié)點(diǎn)
    
    public void insert(int val) { //插入新的節(jié)點(diǎn)
        
    }
    
    public void remove(int val) { //刪除對(duì)應(yīng)的節(jié)點(diǎn)
        
    }
    
    public boolean contains(int val) { //查詢是否有該值
        
    }
}

我們就一個(gè)一個(gè)的講解每一方法具體的實(shí)現(xiàn)：

插入

插入新的節(jié)點(diǎn)，這個(gè)算是比較簡(jiǎn)單的。我們拿到依次比較當(dāng)前節(jié)點(diǎn)的值和傳遞進(jìn)來(lái)的形參值，如果形參值更小一點(diǎn)，我們就往左子樹(shù)上做遞歸，繼續(xù)這個(gè)操作即可。

//遞歸解法
public void insert(int val) {
    root = process(val, root);
}

private TreeNode process(int val, TreeNode node) {
    if (node == null) { //如果當(dāng)前節(jié)點(diǎn)為null，說(shuō)明已經(jīng)走到頭了，此時(shí)創(chuàng)建節(jié)點(diǎn)，返回即可
        return new TreeNode(val);
    } 
    if (val < node.val) { //小于當(dāng)前節(jié)點(diǎn)
        node.left = process(val, node.left);
    } else {
        node.right = process(val, node.right); //大于等于當(dāng)前節(jié)點(diǎn)
    }
    return node;
}

//非遞歸解法
public void insert(int val) {
    TreeNode node = new TreeNode(val); //先創(chuàng)建好節(jié)點(diǎn)
    TreeNode parent = null; //父節(jié)點(diǎn)，用于連接新的節(jié)點(diǎn)
    TreeNode cur = root; //當(dāng)前移動(dòng)的節(jié)點(diǎn)
    
    if (root == null) {
        root = node; //還沒(méi)有根結(jié)點(diǎn)的情況
    } else {
        while (true) {
            parent = cur;
            if (val < cur.val) { //小于當(dāng)前節(jié)點(diǎn)的情況
                cur = cur.left;
                if (cur == null) { //如果為null了，說(shuō)明走到了最后的節(jié)點(diǎn)
                    parent.left = node;
                    return;
                }
            } else { //大于當(dāng)前節(jié)點(diǎn)的情況
                cur = cur.right;
                if (cur == null) {
                    parent.right = node; //如果為null，就走到最后節(jié)點(diǎn)了
                    return;
                }
            }
        }
    }
}

遞歸與非遞歸的解法，差異只是在于空間復(fù)雜度。當(dāng)整棵樹(shù)很大時(shí)，遞歸去調(diào)用，就會(huì)耗費(fèi)大量的?？臻g。而非遞歸的解法，只是耗費(fèi)了幾個(gè)引用的空間。

刪除

刪除是一個(gè)比較難的點(diǎn)，刪除之后，還需要保持搜索二叉樹(shù)的結(jié)構(gòu)。所以我們需要分為三種情況：

• 被刪除節(jié)點(diǎn)是葉節(jié)點(diǎn)。
• 被刪除節(jié)點(diǎn)只有一個(gè)孩子節(jié)點(diǎn)。
• 被刪除節(jié)點(diǎn)有兩個(gè)孩子節(jié)點(diǎn)。

我們需要循環(huán)遍歷這顆樹(shù)，找到需要被刪除的節(jié)點(diǎn)，并且在遍歷的過(guò)程中，還需要記錄被刪除節(jié)點(diǎn)的父節(jié)點(diǎn)是誰(shuí)，以及被刪除節(jié)點(diǎn)是父節(jié)點(diǎn)的左孩子還是右孩子。所以循環(huán)時(shí)，有三個(gè)變量，分別是parent、cur和isLeftChild。

在找到需要被刪除的節(jié)點(diǎn)后。再對(duì)這個(gè)節(jié)點(diǎn)進(jìn)行判斷，看這個(gè)節(jié)點(diǎn)是葉節(jié)點(diǎn)？還是只有一個(gè)孩子節(jié)點(diǎn)？又或者是有兩個(gè)孩子節(jié)點(diǎn)的情況。

1. 如果是葉節(jié)點(diǎn)，parent的left（或者是right）置為null
2. 如果只有一個(gè)節(jié)點(diǎn)，我們就需要繞過(guò)cur節(jié)點(diǎn)，直接連接cur的left或者right
3. 如果是有兩個(gè)節(jié)點(diǎn)，我們就需要找到cur的后繼節(jié)點(diǎn)。也就是cur的右子樹(shù)中，最小的節(jié)點(diǎn)。

其次我們還需要判斷被刪除的節(jié)點(diǎn)，是不是root根結(jié)點(diǎn)？如果是，就需要更換根結(jié)點(diǎn)。

非遞歸版本大致框架：

//非遞歸版本
public boolean remove(int val) { //刪除對(duì)應(yīng)的節(jié)點(diǎn)
    if (root == null) {
        throw new RuntimeException("root is null.");
    }

    TreeNode parent = root;
    TreeNode cur = root;
    boolean isLeftChild = true;

    while (cur != null && cur.val != val) { //循環(huán)查找需要被刪除的節(jié)點(diǎn)
        parent = cur;
        if (val < cur.val) {
            cur = cur.left;
            isLeftChild = true;
        } else {
            cur = cur.right;
            isLeftChild = false;
        }
    }

    if (cur == null) { //沒(méi)找到需要?jiǎng)h除的節(jié)點(diǎn)
        return false;
    }

    //找到了需要被刪除的節(jié)點(diǎn)
    if ( cur.left== null && cur.right == null) { //葉節(jié)點(diǎn)的情況
        if (cur == root) {
            root = null;
        } else if (isLeftChild) {
            parent.left = null;
        } else {
            parent.right = null;
        }
    } else if (cur.right == null) {
        if (cur == root) {
            root = root.left;
        } else if (isLeftChild) {
            parent.left = cur.left;
        } else {
            parent.right = cur.left;
        }
    } else if (cur.left == null) { //只有一個(gè)孩子節(jié)點(diǎn)的情況
        if (cur == root) {
            root = root.right;
        } else if (isLeftChild) {
            parent.left = cur.right;
        } else {
            parent.right = cur.right;
        }
    } else { //有兩個(gè)孩子節(jié)點(diǎn)的情況
        TreeNode minNode = findMinNode(cur.right);
        if (cur == root) {
            root = minNode;
        } else if (isLeftChild) {
            parent.left = minNode;
        } else {
            parent.right = minNode;
        }
        minNode.left = cur.left; //新節(jié)點(diǎn)minNode的左孩子指向被刪除節(jié)點(diǎn)cur的左孩子
        // C/C++語(yǔ)言，需要回收cur內(nèi)存空間
    }
    return true;
}

private TreeNode findMinNode(TreeNode head)  {
    TreeNode pre = null;
    TreeNode cur = head;
    TreeNode next = head.left;
    while (next != null) {
        pre = cur;
        cur = next;
        next = next.left; //一直尋找該樹(shù)的最左的節(jié)點(diǎn)
    }
    if (pre != null) {
        pre.left = cur.right; //cur就是最左邊的節(jié)點(diǎn)，pre的cur的父節(jié)點(diǎn)。父節(jié)點(diǎn)的left指向cur的right
        cur.right = head; //cur的right指向head這個(gè)根結(jié)點(diǎn)
    }
    return cur; //返回最左邊的節(jié)點(diǎn)
}

//遞歸版本
public void remove2(int val) {
    if (root == null) {
        throw new RuntimeException("root is null.");
    }

    process2(val, root);
}

private TreeNode process2(int val, TreeNode node) {
    if (node == null) {
        return null;
    }
    if (val < node.val) { //小于
        node.left = process2(val, node.left);
    } else if (val > node.val){ //大于
        node.right = process2(val, node.right);
    } else if (node.left != null && node.right != null) { //上面的if沒(méi)成立，說(shuō)明val相等。這里是兩個(gè)孩子節(jié)點(diǎn)的情況
        
        node.val = getMinNodeVal(node.right); //覆蓋右子樹(shù)中最小的節(jié)點(diǎn)值
        
        node.right = process2(node.val, node.right); // 重新對(duì)已經(jīng)覆蓋的數(shù)值進(jìn)行刪除
        
    } else { //只有一個(gè)孩子節(jié)點(diǎn)或者沒(méi)有節(jié)點(diǎn)的情況
        node = node.left != null? node.left : node.right;
    }
    return node;
}

private int getMinNodeVal(TreeNode node) {
    TreeNode pre = null;
    TreeNode cur = node;
    while (cur != null) {
        pre = cur;
        cur = cur.left;
    }
    return pre.val;
}

遞歸版本的刪除，只是將右子樹(shù)最小節(jié)點(diǎn)的值，賦值給了cur，然后遞歸調(diào)用去刪除右子樹(shù)上最小值的節(jié)點(diǎn)。

最后一個(gè)contains方法就簡(jiǎn)單了，遍歷整顆二叉樹(shù)，找到了val就返回true，否則返回false。

public boolean contains(int val) {
    TreeNode cur = root;
    while (cur != null) {
        if (cur.val == val) {
            return true;
        } else if (val < cur.val) {
            cur = cur.left;
        } else {
            cur = cur.right;
        }
    }
    return false;
}

最后自己再寫(xiě)一個(gè)中序遍歷的方法，看看自己寫(xiě)的代碼是否正確了呢。切記：搜索二叉樹(shù)中序遍歷的結(jié)果，一定是一個(gè)升序的。不知道怎么寫(xiě)遍歷方法的，可以看一下前期文章：通俗易懂講解C語(yǔ)言與Java中二叉樹(shù)的三種非遞歸遍歷方式。
好啦，本期文章就到此結(jié)束啦，我們下期見(jiàn)！?。?/p>

到此這篇關(guān)于Java中關(guān)于二叉樹(shù)的概念以及搜索二叉樹(shù)詳解的文章就介紹到這了,更多相關(guān)Java 二叉樹(shù)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論