前言

• 緊接前面說過的 二叉樹的實現(xiàn) 和 二叉樹的遍歷狗热，今天來說一下用javascript實現(xiàn)二叉樹的查找和節(jié)點刪除。

• 為了表面寫起來讀起來很拗口虑省，以下內(nèi)容中就將“節(jié)點值為x的節(jié)點”直接省略成“節(jié)點x”

• 下面先引入二叉樹的實現(xiàn)和遍歷斗搞，二叉樹的實現(xiàn)在此做了一點修改：

// 節(jié)點對象
function Node(data, right, left) {
    this.data = data;
    this.left = left;
    this.right = right;
}
// 二叉樹對象
function BST() {
    this.root = null;
}
// 插入二叉樹
BST.prototype.insert = function(data) {
    var node = new Node(data, null, null);
    if(this.root == null) {
        this.root = node;
    } else {
        var current = this.root;
        while(true) {
            if(data < current.data) {
                if(current.left == null) {
                    current.left = node;
                    break;
                } else {
                    current = current.left;
                }
            } else {
                if(current.right == null) {
                    current.right = node;
                    break;  
                } else {
                    current = current.right;
                }
            }
        }
    }
};
// 中序遍歷
BST.prototype.inOrder = function(node, callback) {
    if(node != null) {
        this.inOrder(node.left, callback);
        callback && callback(node.data);
        this.inOrder(node.right, callback);
    }
};
// 先序遍歷
BST.prototype.preOrder = function(node, callback) {
    if(node != null) {
        callback && callback(node.data);
        this.preOrder(node.left, callback);
        this.preOrder(node.right, callback);
    }
};
// 后序遍歷
BST.prototype.postOrder = function(node, callback) {
    if(node != null) {
        this.postOrder(node.left, callback);
        this.postOrder(node.right, callback);
        callback && callback(node.data);
    }
};

二叉樹查找

二叉樹的查找課簡單地細(xì)分成：

• 查找二叉樹的最大最小值；
• 給定值在二叉樹中進(jìn)行查找慷妙。

查找最大最小值

看過 二叉樹的實現(xiàn) 的或者已經(jīng)有相關(guān)數(shù)據(jù)結(jié)構(gòu)的道友就會了解，實現(xiàn)起來異常簡單允悦。最小值就是二叉樹最左邊的葉子節(jié)點膝擂，而最大值就是二叉樹最左邊的葉子節(jié)點。

BST.prototype.getMin = function() {
    var current = this.root;
    while(current.left != null) {
        current = current.left;
    }
    return current.data;
};

BST.prototype.getMax = function() {
    var current = this.root;
    while(current.right != null) {
        current = current.right;
    }
    return current.data;
};

異常簡單吧隙弛！
代碼測試一下：

查找給定值

二叉樹的一個特點是：左節(jié)點值 < 父節(jié)點值 < 右節(jié)點
這樣思路就出來了架馋，分成三種情況：

• 節(jié)點值和給定值相當(dāng) => 返回該節(jié)點；
• 給定值 < 節(jié)點值 => 查找當(dāng)前節(jié)點的左節(jié)點全闷，用左節(jié)點的值和給定值比較叉寂；
• 給定值 > 節(jié)點值 => 查找當(dāng)前節(jié)點的右節(jié)點，用右節(jié)點的值和給定值比較总珠；

PS：說白了屏鳍，就是用給定值從根節(jié)點開始往下逐個和每個節(jié)點比較，相等就返回局服，大于就找右邊钓瞭，小于就找左邊，直到找到相等的或已經(jīng)沒得找淫奔。

BST.prototype.find = function(data) {
    var current = this.root;
    while(current) {
        if(current.data == data) {
            return current;
        } else if(data < current.data) {
            current = current.left;
        } else{
            current = current.right;
        }
    }
    return null;
};

也是異常簡單吧山涡！

?

二叉樹節(jié)點的刪除

二叉樹節(jié)點的刪除也是可以分為幾種情況:

• 被刪除節(jié)點為葉子節(jié)點；
• 被刪除節(jié)點僅有一個子節(jié)點（子樹）唆迁；
• 被刪除節(jié)點有兩個子節(jié)點（子樹）

被刪除節(jié)點為葉子節(jié)點

思路：將該葉子節(jié)點的父節(jié)點指向的子節(jié)點的引用值設(shè)為空

以上圖為例子鸭丛，要刪除節(jié)點 2

console.log(node.data);  // 3
// 刪除節(jié)點2
node.letf = null;

被刪除節(jié)點僅有一個子樹

思路：將該節(jié)點的父節(jié)點指向該節(jié)點的引用改成指向該節(jié)點的子節(jié)點。

以上圖為例子唐责，刪除節(jié)點4鳞溉。就是將節(jié)點3的node.right 改成 node.letf = 節(jié)點9

被刪除節(jié)點有兩個子樹

思路：處理這種情況有兩種方法：

• 從待刪除節(jié)點的左子樹找節(jié)點值最大的節(jié)點A，替換待刪除節(jié)點鼠哥，并刪除節(jié)點A穿挨；
• 從待刪除節(jié)點的右子樹找節(jié)點值最小的節(jié)點A月弛，替換待刪除節(jié)點，并刪除節(jié)點A科盛。

PS：我們這里選擇第二種方法帽衙。
以下圖的二叉樹為例，刪除節(jié)點3贞绵。

看到我改了圖吧彩郊，改一下前弯，讓人好點理解嘛，絕不是避開坑專門不說秫逝。

三種情況的解決思路都說完苗傅，來看看代碼的具體實現(xiàn)：

// 獲取給定節(jié)點下的二叉樹最小值
BST.prototype.getSmallest = function(node) {
    if(node.left == null) {
        return node;
    } else {
        return getSmallest(node.left);
    }
};
// 根據(jù)給定刪除給定節(jié)點下二叉樹的對應(yīng)節(jié)點
BST.prototype.removeNode = function(node, data) {
    if(node == null) {
        return null;
    }
    if(data == node.data) {
        // 沒有子節(jié)點（子樹）
        if(node.left == null && node.right == null) {
            return null;
        } 
        // 只有右子節(jié)點（子樹）
        else if(node.left == null ) {
            return node.right;
        } 
        // 只有左子節(jié)點（子樹）
        else if(node.right == null){
            return node.left;
        } 
        // 有兩個子節(jié)點（子樹）
        else {
            var tempNode = this.getSmallest(node.right);
            node.data = tempNode.data;
            node.right = this.removeNode(node.right, tempNode.data);
            return node;
        }
    } else if(data < node.data) {
        node.left = this.removeNode(node.left, data);
        return node;
    } else {
        node.right = this.removeNode(node.right, data);
        return node;
    }
}

由上面看到這兩個方法都是用遞歸實現(xiàn)的。removeNode 遞歸實現(xiàn)的巧妙之處在于 return 班巩，比如說 node.right = this.removeNode(node.right, data); 這一句渣慕，假設(shè)被刪除的節(jié)點是節(jié)點4

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

理一下代碼抱慌，最后的代碼是：node.right = node.right.right;逊桦，在“不知不覺中”就刪除了節(jié)點node.right，可以用刪除節(jié)點4代入一下抑进。node就是節(jié)點3强经，而node.right就是節(jié)點4， node.right.right就是節(jié)點9寺渗。
最后也是代碼測試一下：

[傳送門：demo]

各位觀眾老爺匿情，先說到這里兰迫，下次再尬blog。