摘要：二叉查找樹二叉查找樹也叫二叉搜索樹它只允許我們?cè)谧蠊?jié)點(diǎn)存儲(chǔ)比父節(jié)點(diǎn)更小的值，右節(jié)點(diǎn)存儲(chǔ)比父節(jié)點(diǎn)更大的值，上圖展示的就是一顆二叉查找樹。

前兩天接到了螞蟻金服的面試電話，面試官很直接，上來(lái)就拋出了三道算法題。。。

其中有一道關(guān)于二叉樹實(shí)現(xiàn)中序遍歷的，當(dāng)時(shí)沒(méi)回答好，所以特意學(xué)習(xí)了一把二叉樹的知識(shí)，行文記錄總結(jié)。

節(jié)點(diǎn)： 樹中的每個(gè)元素稱為一個(gè)節(jié)點(diǎn)，

根節(jié)點(diǎn)： 位于整棵樹頂點(diǎn)的節(jié)點(diǎn)，它沒(méi)有父節(jié)點(diǎn)， 如上圖 5

子節(jié)點(diǎn)： 其他節(jié)點(diǎn)的后代

葉子節(jié)點(diǎn): 沒(méi)有子節(jié)點(diǎn)的元素稱為葉子節(jié)點(diǎn)， 如上圖 3 8 24

二叉樹：二叉樹就是一種數(shù)據(jù)結(jié)構(gòu)， 它的組織關(guān)系就像是自然界中的樹一樣。官方語(yǔ)言的定義是：是一個(gè)有限元素的集合,該集合或者為空、或者由一個(gè)稱為根的元素及兩個(gè)不相交的、被分別稱為左子樹和右子樹的二叉樹組成。

二叉查找樹：
二叉查找樹也叫二叉搜索樹（BST）,它只允許我們?cè)谧蠊?jié)點(diǎn)存儲(chǔ)比父節(jié)點(diǎn)更小的值，右節(jié)點(diǎn)存儲(chǔ)比父節(jié)點(diǎn)更大的值，上圖展示的就是一顆二叉查找樹。

首先創(chuàng)建一個(gè)類來(lái)表示二叉查找樹，它的內(nèi)部應(yīng)該有一個(gè)Node類，用來(lái)創(chuàng)建節(jié)點(diǎn)

    function BinarySearchTree () {
        var Node = function(key) {
            this.key = key,
            this.left = null,
            this.right = null
        }
        var root = null
    }

它還應(yīng)該有一些方法：

insert(key) 插入一個(gè)新的鍵

inOrderTraverse() 對(duì)樹進(jìn)行中序遍歷，并打印結(jié)果

preOrderTraverse() 對(duì)樹進(jìn)行先序遍歷，并打印結(jié)果

postOrderTraverse() 對(duì)樹進(jìn)行后序遍歷，并打印結(jié)果

search(key) 查找樹中的鍵，如果存在返回true,不存在返回fasle

findMin() 返回樹中的最小值

findMax() 返回樹中的最大值

remove(key) 刪除樹中的某個(gè)鍵

向樹中插入一個(gè)新的鍵，首頁(yè)應(yīng)該創(chuàng)建一個(gè)用來(lái)表示新節(jié)點(diǎn)的Node類實(shí)例，因此需要new一下Node類并傳入需要插入的key值，它會(huì)自動(dòng)初始化為左右節(jié)點(diǎn)為null的一個(gè)新節(jié)點(diǎn)

然后，需要做一些判斷，先判斷樹是否為空，若為空，新插入的節(jié)點(diǎn)就作為根節(jié)點(diǎn)，如不為空，調(diào)用一個(gè)輔助方法insertNode()方法，將根節(jié)點(diǎn)和新節(jié)點(diǎn)傳入

    this.insert = function(key) {
        var newNode = new Node(key)
        if(root === null) {
            root = newNode
        } else {
            insertNode(root, newNode)
        }
    }

定義一下insertNode() 方法，這個(gè)方法會(huì)通過(guò)遞歸得調(diào)用自身，來(lái)找到新添加節(jié)點(diǎn)的合適位置

    var insertNode = function(node, newNode) {
        if (newNode.key <= node.key) {
            if (node.left === null) {
                node.left = newNode
            }else {
                insertNode(node.left, newNode)
            }
        }else {
            if (node.right === null) {
                node.right = newNode
            }else {
                insertNode(node.right, newNode)
            }
        }
    } 

要實(shí)現(xiàn)中序遍歷，我們需要一個(gè)inOrderTraverseNode(node)方法，它可以遞歸調(diào)用自身來(lái)遍歷每個(gè)節(jié)點(diǎn)

    this.inOrderTraverse = function() {
        inOrderTraverseNode(root)
    }

這個(gè)方法會(huì)打印每個(gè)節(jié)點(diǎn)的key值，它需要一個(gè)遞歸終止條件————檢查傳入的node是否為null，如果不為空，就繼續(xù)遞歸調(diào)用自身檢查node的left、right節(jié)點(diǎn)
實(shí)現(xiàn)起來(lái)也很簡(jiǎn)單:

    var inOrderTraverseNode = function(node) {
        if (node !== null) {
            inOrderTraverseNode(node.left)
            console.log(node.key)
            inOrderTraverseNode(node.right)
        }
    }

有了中序遍歷的方法，只需要稍作改動(dòng)，就可以實(shí)現(xiàn)先序遍歷和后序遍歷了
上代碼：

這樣就可以對(duì)整棵樹進(jìn)行中序遍歷了

    // 實(shí)現(xiàn)先序遍歷
    this.preOrderTraverse = function() {
        preOrderTraverseNode(root)
    }
    var preOrderTraverseNode = function(node) {
        if (node !== null) {
            console.log(node.key)
            preOrderTraverseNode(node.left)
            preOrderTraverseNode(node.right)
        }
    }

    // 實(shí)現(xiàn)后序遍歷
    this.postOrderTraverse = function() {
        postOrderTraverseNode(root)
    }
    var postOrderTraverseNode = function(node) {
        if (node !== null) {
            postOrderTraverseNode(node.left)
            postOrderTraverseNode(node.right)
            console.log(node.key)
        }
    }

發(fā)現(xiàn)了吧，其實(shí)就是內(nèi)部語(yǔ)句更換了前后位置，這也剛好符合三種遍歷規(guī)則：先序遍歷（根-左-右）、中序遍歷（左-根-右）、中序遍歷（左-右-根）

現(xiàn)在的完整代碼如下：

    function BinarySearchTree () {
        var Node = function(key) {
            this.key = key,
            this.left = null,
            this.right = null
        }
        var root = null
        
        //插入節(jié)點(diǎn)
        this.insert = function(key) {
            var newNode = new Node(key)
            if(root === null) {
                root = newNode
            } else {
                insertNode(root, newNode)
            }
        }
        var insertNode = function(node, newNode) {
            if (newNode.key <= node.key) {
                if (node.left === null) {
                    node.left = newNode
                }else {
                    insertNode(node.left, newNode)
                }
            }else {
                if (node.right === null) {
                    node.right = newNode
                }else {
                    insertNode(node.right, newNode)
                }
            }
        } 
        
        //實(shí)現(xiàn)中序遍歷
        this.inOrderTraverse = function() {
            inOrderTraverseNode(root)
        }
        var inOrderTraverseNode = function(node) {
            if (node !== null) {
                inOrderTraverseNode(node.left)
                console.log(node.key)
                inOrderTraverseNode(node.right)
            }
        }
        // 實(shí)現(xiàn)先序遍歷
        this.preOrderTraverse = function() {
            preOrderTraverseNode(root)
        }
        var preOrderTraverseNode = function(node) {
            if (node !== null) {
                console.log(node.key)
                preOrderTraverseNode(node.left)
                preOrderTraverseNode(node.right)
            }
        }

        // 實(shí)現(xiàn)后序遍歷
        this.postOrderTraverse = function() {
            postOrderTraverseNode(root)
        }
        var postOrderTraverseNode = function(node) {
            if (node !== null) {
                postOrderTraverseNode(node.left)
                postOrderTraverseNode(node.right)
                console.log(node.key)
            }
        }
    }

竟然已經(jīng)完成了添加新節(jié)點(diǎn)和遍歷的方式，我們來(lái)測(cè)試一下吧：

定義一個(gè)數(shù)組，里面有一些元素

var arr = [9,6,3,8,12,15]

我們將arr中的每個(gè)元素依此插入到二叉搜索樹中，然后打印結(jié)果

    var tree = new BinarySearchTree()
    arr.map(item => {
        tree.insert(item)
    })
    tree.inOrderTraverse()
    tree.preOrderTraverse()
    tree.postOrderTraverse()

運(yùn)行代碼后，我們先來(lái)看看插入節(jié)點(diǎn)后整顆樹的情況：

輸出結(jié)果

中序遍歷：

3
6
8
9
12
15

先序遍歷：

9
6
3
8
12
15

后序遍歷：

3
8
6
15
12
9

很明顯，結(jié)果是符合預(yù)期的，所以，我們用上面的JavaScript代碼，實(shí)現(xiàn)了對(duì)樹的節(jié)點(diǎn)插入，和三種遍歷方法，同時(shí)，很明顯可以看到，在二叉查找樹樹種，最左側(cè)的節(jié)點(diǎn)的值是最小的，而最右側(cè)的節(jié)點(diǎn)的值是最大的，所以二叉查找樹可以很方便的拿到其中的最大值和最小值

怎么做呢？其實(shí)只需要將根節(jié)點(diǎn)傳入minNode/或maxNode方法，然后通過(guò)循環(huán)判斷node為左側(cè)(minNode)/右側(cè)(maxNode)的節(jié)點(diǎn)為null

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

    // 查找最小值
    this.findMin = function() {
        return minNode(root)
    }
    var minNode = function(node) {
        if (node) {
            while (node && node.left !== null) {
                node = node.left
            }
            return node.key
        }
        return null
    }
    
    // 查找最大值
    this.findMax = function() {
        return maxNode(root)
    }
    var maxNode = function (node) {
        if(node) {
            while (node && node.right !== null) {
                node =node.right
            }
            return node.key
        }
        return null
    }

this.search = function(key) {
    return searchNode(root, key)
}

同樣，實(shí)現(xiàn)它需要定義一個(gè)輔助方法,這個(gè)方法首先會(huì)檢驗(yàn)node的合法性，如果為null，直接退出，并返回fasle。如果傳入的key比當(dāng)前傳入node的key值小，它會(huì)繼續(xù)遞歸查找node的左側(cè)節(jié)點(diǎn)，反之，查找右側(cè)節(jié)點(diǎn)。如果找到相等節(jié)點(diǎn)，直接退出，并返回true

    var searchNode = function(node, key) {
        if (node === null) {
            return false
        }
        if (key < node.key) {
            return searchNode(node.left, key)
        }else if (key > node.key) {
            return searchNode(node.right, key)
        }else {
            return true
        }
    }

移除節(jié)點(diǎn)的實(shí)現(xiàn)情況比較復(fù)雜，它會(huì)有三種不同的情況：

需要移除的節(jié)點(diǎn)是一個(gè)葉子節(jié)點(diǎn)

需要移除的節(jié)點(diǎn)包含一個(gè)子節(jié)點(diǎn)

需要移除的節(jié)點(diǎn)包含兩個(gè)子節(jié)點(diǎn)

和實(shí)現(xiàn)搜索指定節(jié)點(diǎn)一元，要移除某個(gè)節(jié)點(diǎn)，必須先找到它所在的位置，因此移除方法的實(shí)現(xiàn)中部分代碼和上面相同：

    // 移除節(jié)點(diǎn)
    this.remove = function(key) {
        removeNode(root,key)
    }
    var removeNode = function(node, key) {
        if (node === null) {
            return null
        }
        if (key < node.key) {
            node.left = removeNode(node.left, key)
            return node
        }else if(key > node.key) {
            node.right = removeNode(node.right,key)
            return node
        }else{
            //需要移除的節(jié)點(diǎn)是一個(gè)葉子節(jié)點(diǎn)
            if (node.left === null && node.right === null) {
                node = null
                return node
            }
            //需要移除的節(jié)點(diǎn)包含一個(gè)子節(jié)點(diǎn)
            if (node.letf === null) {
                node = node.right
                return node
            }else if (node.right === null) {
                node = node.left
                return node
            }
            //需要移除的節(jié)點(diǎn)包含兩個(gè)子節(jié)點(diǎn)
            var aux = findMinNode(node.right)
            node.key = aux.key
            node.right = removeNode(node.right, axu.key)
            return node
        }
    }
    var findMinNode = function(node) {
        if (node) {
            while (node && node.left !== null) {
                node = node.left
            }
            return node
        }
        return null
    }

其中，移除包含兩個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn)是最復(fù)雜的情況，它包含左側(cè)節(jié)點(diǎn)和右側(cè)節(jié)點(diǎn)，對(duì)它進(jìn)行移除主要需要三個(gè)步驟：

需要找到它右側(cè)子樹中的最小節(jié)點(diǎn)來(lái)代替它的位置

將它右側(cè)子樹中的最小節(jié)點(diǎn)移除

將更新后的節(jié)點(diǎn)的引用指向原節(jié)點(diǎn)的父節(jié)點(diǎn)

有點(diǎn)繞兒，但必須這樣，因?yàn)閯h除元素后的二叉搜索樹必須保持它的排序性質(zhì)

tree.remove(8)
tree.inOrderTraverse()

打印結(jié)果：

3
6
9
12
15

8 這個(gè)節(jié)點(diǎn)被成功刪除了，但是對(duì)二叉查找樹進(jìn)行中序遍歷依然是保持排序性質(zhì)的

到這里，一個(gè)簡(jiǎn)單的二叉查找樹就基本上完成了，我們?yōu)樗鼘?shí)現(xiàn)了，添加、查找、刪除以及先中后三種遍歷方法

但是實(shí)際上這樣的二叉查找樹是存在一些問(wèn)題的，當(dāng)我們不斷的添加更大/更小的元素的時(shí)候，會(huì)出現(xiàn)如下情況：

tree.insert(16)
tree.insert(17)
tree.insert(18)

來(lái)看看現(xiàn)在整顆樹的情況：

很容易發(fā)現(xiàn)，它是不平衡的，這又會(huì)引出平衡樹的概念，要解決這個(gè)問(wèn)題，還需要更復(fù)雜的實(shí)現(xiàn)，例如：AVL樹，紅黑樹 哎，之后再慢慢去學(xué)習(xí)吧

關(guān)于實(shí)現(xiàn)二叉排序樹，我也找到慕課網(wǎng)的一系列的視頻：Javascript實(shí)現(xiàn)二叉樹算法,
內(nèi)容和上述實(shí)現(xiàn)基本一致

原文鏈接：行無(wú)忌的成長(zhǎng)小屋：JavaScript實(shí)現(xiàn)簡(jiǎn)單二叉查找樹