摘要：本文專門針對(duì)笨蛋介紹如何編寫二叉樹，包括二叉樹的結(jié)構(gòu)如何添加節(jié)點(diǎn)如何刪除節(jié)點(diǎn)。二叉樹的結(jié)構(gòu)有三個(gè)要點(diǎn)每個(gè)節(jié)點(diǎn)最多有兩個(gè)子節(jié)點(diǎn)，分別稱作左子節(jié)點(diǎn)和右子節(jié)點(diǎn)。通過這種生長(zhǎng)方式，我們無論何時(shí)都能得到滿足前面三個(gè)要素的二叉樹。

本文專門針對(duì)笨蛋介紹如何編寫二叉樹，包括二叉樹的結(jié)構(gòu)、如何添加節(jié)點(diǎn)、如何刪除節(jié)點(diǎn)。

首先介紹二叉樹的結(jié)構(gòu)。

二叉樹的結(jié)構(gòu)有三個(gè)要點(diǎn)：

每個(gè)節(jié)點(diǎn)最多有兩個(gè)子節(jié)點(diǎn)，分別稱作左子節(jié)點(diǎn)和右子節(jié)點(diǎn)。

每個(gè)節(jié)點(diǎn)的左子節(jié)點(diǎn)的值比它小，右子節(jié)點(diǎn)的值比它大。

每個(gè)節(jié)點(diǎn)的左子樹每個(gè)節(jié)點(diǎn)的值都比它小，右子樹每個(gè)節(jié)點(diǎn)的值都比它大。

看上面這個(gè)例子，就完全符合這三點(diǎn)。

這時(shí)候笨蛋就會(huì)問了：前面兩點(diǎn)我理解，但是第三點(diǎn)是怎么做到的？

所以接下來介紹下二叉樹是如何 “生長(zhǎng)” 起來的：

如上圖所示，當(dāng)加入一個(gè)新節(jié)點(diǎn)時(shí)，從根節(jié)點(diǎn)開始對(duì)它進(jìn)行比較。如果它比根節(jié)點(diǎn)小，則放入根節(jié)點(diǎn)的左子樹，如果比根節(jié)點(diǎn)大，則放入根節(jié)點(diǎn)的右子樹。

然后再進(jìn)行下一級(jí)節(jié)點(diǎn)的比較，直到遇到最后一級(jí)節(jié)點(diǎn)，才將新節(jié)點(diǎn)加入為該節(jié)點(diǎn)的左或右子節(jié)點(diǎn)。

以第四幅圖的節(jié)點(diǎn) 25 為例，它第一次會(huì)與根節(jié)點(diǎn) 10 比較，結(jié)果就是 25 應(yīng)該放入 10 的右子樹，這就排除了它放入左子樹的可能，即 25 不可能放到 4 的下面。

然后 25 再和節(jié)點(diǎn) 33 比較，結(jié)果是它比較小，所以應(yīng)該放入 33 的左子樹。因?yàn)?33 沒有左子節(jié)點(diǎn)，那么 25 就直接作為 33 的左子節(jié)點(diǎn)了。

通過這種生長(zhǎng)方式，我們無論何時(shí)都能得到滿足前面三個(gè)要素的二叉樹。

那么寫代碼該如何實(shí)現(xiàn)呢？所謂慢工出細(xì)活，我們一步一步來。

首先我們創(chuàng)建二叉樹節(jié)點(diǎn)的基本結(jié)構(gòu)。每個(gè)二叉樹都有四個(gè)成員，如下所示。

public class BasicBTree {

    public int value;            // 節(jié)點(diǎn)的值

    public BasicBTree left;      // 節(jié)點(diǎn)的左子節(jié)點(diǎn)

    public BasicBTree right;     // 節(jié)點(diǎn)的右子節(jié)點(diǎn)

    public BasicBTree parent;    // 節(jié)點(diǎn)的父節(jié)點(diǎn)。如果為 null 則表示該節(jié)點(diǎn)是根節(jié)點(diǎn)
    
    // 構(gòu)造方法
    public BasicBTree(int value) {
        this.value = value;
    }
}

回頭看第一張圖，你會(huì)發(fā)現(xiàn)每個(gè)節(jié)點(diǎn)最多有三根線連著，上面的線就代表 BasicBTree 的 parent，下面兩根線就分別代表 left 和 right 了。而節(jié)點(diǎn)中的數(shù)字就是 BasicBTree 的 value。

接下來我們要為 BasicBTree 編寫兩個(gè)簡(jiǎn)單的方法，用來給它添加左子節(jié)點(diǎn)和右子節(jié)點(diǎn)：

// 將一個(gè)節(jié)點(diǎn)加為當(dāng)前節(jié)點(diǎn)的左子節(jié)點(diǎn)
public void setLeft(BasicBTree node) {
    if (this.left != null) {
        this.left.parent = null;  // 解除當(dāng)前的左子節(jié)點(diǎn)
    }
    this.left = node;
    if (this.left != null) {
        this.left.parent = this;  // 設(shè)置新子節(jié)點(diǎn)的父節(jié)點(diǎn)為自身
    }
}

// 將一個(gè)節(jié)點(diǎn)加為當(dāng)前節(jié)點(diǎn)的右子節(jié)點(diǎn)
public void setRight(BasicBTree node) {
    if (this.right != null) {
        this.right.parent = null; // 解除當(dāng)前的右子節(jié)點(diǎn)
    }
    this.right = node;
    if (this.right != null) {
        this.right.parent = this; // 設(shè)置新子節(jié)點(diǎn)的父節(jié)點(diǎn)為自身
    }
}

在上面兩個(gè)方法的基礎(chǔ)上，我們可以添加一個(gè)添加任意值節(jié)點(diǎn)的方法：

// 將一個(gè)節(jié)點(diǎn)加為當(dāng)前節(jié)點(diǎn)的左或右子節(jié)點(diǎn)
public void setChild(BasicBTree node) {
    if (node == null) {
        return;
    }

    if (node.value < this.value) {
        setLeft(node);
    } else if (node.value > this.value) {
        setRight(node);
    }
}

另外我們?cè)偬砑右粋€(gè)刪除左子節(jié)點(diǎn)或右子節(jié)點(diǎn)的方法：

// 刪除當(dāng)前節(jié)點(diǎn)的一個(gè)直接子節(jié)點(diǎn)
public void deleteChild(BasicBTree node) {
    if (node == null) {
        return;
    }

    if (node == this.left) {
        node.parent = null;
        this.left = null;
    } else if (node == right) {
        node.parent = null;
        this.right = null;
    }
}

這幾個(gè)方法都是非常簡(jiǎn)單的，其中 setChild() 和 deleteChild() 這兩個(gè)方法，我們后面介紹刪除節(jié)點(diǎn)的時(shí)候會(huì)用到。

現(xiàn)在我們正式實(shí)現(xiàn)構(gòu)造樹的方法，就是把一個(gè)一個(gè)數(shù)字加到樹里面去，讓樹越長(zhǎng)越大的方法：

// 向當(dāng)前節(jié)點(diǎn)下面的樹中添加一個(gè)值作為新節(jié)點(diǎn)
public void add(int value) {
    if (value < this.value) {           // 表示應(yīng)該放入左子樹
        if (this.left == null) {        // 如果左子樹為空則構(gòu)建一個(gè)節(jié)點(diǎn)加進(jìn)去
            setLeft(new BasicBTree(value));
        } else {
            this.left.add(value);       // 否則對(duì)左子樹同樣調(diào)用 add 方法（即遞歸）
        }
    } else if (value > this.value) {    // 表示應(yīng)該放入右子樹
        if (this.right == null) {       // 如果右子樹為空則構(gòu)建一個(gè)節(jié)點(diǎn)加進(jìn)去
            setRight(new BasicBTree(value));
        } else {
            this.right.add(value);      // 否則對(duì)右子樹同樣調(diào)用 add 方法（即遞歸）
        }
    }
}

這個(gè)方法稍微復(fù)雜一些，主要是因?yàn)檫壿嬌鲜褂昧诉f歸。這個(gè)方法怎么用呢？以最開始的樹為例，演示如何長(zhǎng)成這棵樹：

public static void main(String[] args) {
    // 根節(jié)點(diǎn)
    BasicBTree tree = new BasicBTree(10);
    
    // 第一層子節(jié)點(diǎn)
    tree.add(4);
    tree.add(33);
    
    // 第二層子節(jié)點(diǎn)
    tree.add(25);
    tree.add(46);
    tree.add(8);
    tree.add(1);
}

你可能會(huì)注意到，加入每一層的子節(jié)點(diǎn)時(shí)，層內(nèi)節(jié)點(diǎn)的添加順序可以任意調(diào)換，構(gòu)造出來的樹都是一樣的；但是如果將不同層的節(jié)點(diǎn)順序互換，構(gòu)造出來的二叉樹就會(huì)變樣了。這當(dāng)中的原因可以自己想想。

最后來介紹二叉樹中最復(fù)雜的操作：刪除節(jié)點(diǎn)。為什么這個(gè)操作最復(fù)雜呢？因?yàn)閯h除一個(gè)節(jié)點(diǎn)之后，要把它下面的節(jié)點(diǎn)接上來，同時(shí)要保持這棵樹繼續(xù)滿足三要素。

如何把下面的節(jié)點(diǎn)接上來呢？最笨的方法當(dāng)然是把被刪節(jié)點(diǎn)的所有子節(jié)點(diǎn)一個(gè)個(gè)重新往樹里面加。但是這樣做效率實(shí)在不高。想想如果被刪節(jié)點(diǎn)有上百萬個(gè)子節(jié)點(diǎn)，那操作步驟就太多了（如下圖所示）。

怎么做才能效率高呢？有一個(gè)辦法，就是從被刪節(jié)點(diǎn)的子節(jié)點(diǎn)中找到一個(gè)合適的，替換掉被刪節(jié)點(diǎn)。這樣做的步驟就少得多了。

不過這樣的節(jié)點(diǎn)是否存在呢？答案是，除非被刪節(jié)點(diǎn)沒有子節(jié)點(diǎn)，否則是一定存在的。

而且這樣的節(jié)點(diǎn)可能不止一個(gè)。原則上講，被刪節(jié)點(diǎn)的左子樹的最大值，或右子樹的最小值，都是滿足條件的，都可以用來替換被刪節(jié)點(diǎn)。比如說，將左子樹的最大值節(jié)點(diǎn)替換上去之后，左子樹的剩余節(jié)點(diǎn)的值都仍然小于該位置的節(jié)點(diǎn)。下面是一個(gè)例子：

比如要?jiǎng)h除節(jié)點(diǎn) 33，而該節(jié)點(diǎn)左子樹的最大值為 31，那么直接將 31 替換到 33 的位置即可，整棵樹仍然滿足三要素。

同理，被刪節(jié)點(diǎn)右子樹的最小值也可以用來替換被刪節(jié)點(diǎn)。比如上圖中 33 節(jié)點(diǎn)的右子節(jié)點(diǎn) 46 也可以用來替換 33，整棵樹仍然滿足三要素。

所以這個(gè)問題就轉(zhuǎn)化為：如何尋找被刪節(jié)點(diǎn)的左子樹的最大值和右子樹的最小值。顯然，因?yàn)槎鏄渌械淖蠊?jié)點(diǎn)都比較小，右節(jié)點(diǎn)都比較大，所以要找最大值，順著右節(jié)點(diǎn)找即可；要找最小值，順著左節(jié)點(diǎn)找即可。下面是實(shí)現(xiàn)的代碼：

// 搜索當(dāng)前節(jié)點(diǎn)左子樹中的最大值節(jié)點(diǎn)，如果沒有左子節(jié)點(diǎn)則返回 null
public BasicBTree leftMax() {
    if (this.left == null) {
        return null;
    }

    BasicBTree result = this.left;  // 起始節(jié)點(diǎn)
    while (result.right != null) {  // 順著右節(jié)點(diǎn)找
        result = result.right;
    }
    return result;
}

// 搜索當(dāng)前節(jié)點(diǎn)右子樹中的最小值節(jié)點(diǎn)，如果沒有右子節(jié)點(diǎn)則返回 null
public BasicBTree rightMin() {
    if (this.right == null) {
        return null;
    }

    BasicBTree result = this.right; // 起始節(jié)點(diǎn)
    while (result.left != null) {   // 順著左節(jié)點(diǎn)找
        result = result.left;
    }
    return result;
}

我們還剩下兩個(gè)準(zhǔn)備工作，第一個(gè)是實(shí)現(xiàn)節(jié)點(diǎn)的查找：

// 查詢指定值的節(jié)點(diǎn)，如果找不到則返回 null
public BasicBTree find(int value) {
    BasicBTree result = this;     // 起始節(jié)點(diǎn)

    if (result.value == value) {
        return result;
    }

    while (result.left != null || result.right != null) {
        // 如果查找的值比當(dāng)前節(jié)點(diǎn)小則順著左子樹查找；
        // 如果比當(dāng)前節(jié)點(diǎn)大則順著右子樹查找。
        if (value < result.value && result.left != null) {
            result = result.left;
        } else if (value > result.value && result.right != null) {
            result = result.right;
        }

        if (result.value == value) {
            return result;
        }
    }

    return null;
}

第二個(gè)是實(shí)現(xiàn)節(jié)點(diǎn)的替換：

// 將節(jié)點(diǎn) node 替換為節(jié)點(diǎn) replace
public BasicBTree replace(BasicBTree node, BasicBTree replace) {

    // 1. replace 接管 node 的子節(jié)點(diǎn)
    replace.setLeft(node.left);
    replace.setRight(node.right);

    // 2. replace 從原來的 parent 脫離
    if (replace.parent != null) {
        replace.parent.deleteChild(replace);
    }

    // 3. node 原來的 parent 接管 replace
    if (node.parent != null) {
        node.parent.setChild(replace);
    }

    // 注意 2 必須在 3 之前，1 位置不論
    return replace;
}

注意這里用到了之前的 setChild() 和 deleteChild() 兩個(gè)方法。而 replace() 方法之所以設(shè)計(jì)為返回 replace 參數(shù)，是為了使用方便。

最后我們就可以正式實(shí)現(xiàn)二叉樹刪除節(jié)點(diǎn)的方法了：

// 從樹的子節(jié)點(diǎn)中刪除指定的值，并重組剩余節(jié)點(diǎn)
public BasicBTree delete(int value) {
    BasicBTree node = find(value);
    if (node == null) {
        return this;
    }

    // 沒有子節(jié)點(diǎn)，直接刪除即可
    if (node.left == null && node.right == null) {
        if (node.parent != null) {
            node.parent.deleteChild(node);
            return this;
        } else {
            // 表示整棵樹唯一的根節(jié)點(diǎn)刪了，只能返回 null
            return null;
        }
    }

    // 如果有子節(jié)點(diǎn)，則取左子樹的最大值或者右子樹的最小值都可以，
    // 來取代該節(jié)點(diǎn)。這里優(yōu)先取左子樹的最大值
    BasicBTree replace;
    if (node.left != null) {
        replace = replace(node, node.leftMax());
    } else {
        replace = replace(node, node.rightMin());
    }

    // 如果被刪除的是根節(jié)點(diǎn)，則返回用于替換的節(jié)點(diǎn)，否則還是返回根節(jié)點(diǎn)
    return node == this ? replace : this;
}