摘要：二叉樹和二叉查找樹一個父節(jié)點的兩個子節(jié)點分別稱為左節(jié)點和右節(jié)點。下圖展示了一顆二叉樹當考慮某種特殊的二叉樹，比如二叉查找樹時，確定子節(jié)點非常重要。實現(xiàn)二叉查找樹定義對象。現(xiàn)在可以創(chuàng)建一個類來表示二叉查找樹。因此二叉查找樹也被叫做二叉排序樹。

樹是計算機科學中經(jīng)常用到的一種數(shù)據(jù)結構。樹是一種非線性的數(shù)據(jù)結構，以分層的方式存儲數(shù)據(jù)。

樹被用來存儲具有層級關系的數(shù)據(jù)，比如文件系統(tǒng)中的文件。

樹還可以用來存儲有序列表。

樹是由一組以邊連接的節(jié)點組成。公司的組織結構圖就是一個樹的例子。

組織結構圖就是一種樹


一棵樹最上面的節(jié)點成為根節(jié)點。如果一個節(jié)點下面連接著多個節(jié)點，那么該節(jié)點稱為父節(jié)點，它下面的節(jié)點稱為子節(jié)點。一個節(jié)點可以有0個，1個或者多個子節(jié)點。沒有任何子節(jié)點的節(jié)點稱為葉子節(jié)點。下圖展示了一些樹的術語。

沿著一組特定的邊，可以從一個節(jié)點走到另外一個與它不直接相連的節(jié)點。從一個節(jié)點到另一個節(jié)點的這一組邊稱為路徑。以特定的順序訪問樹中所有的節(jié)點稱為樹的遍歷。


樹可以分為幾個層次，根節(jié)點是第0層，它的子節(jié)點是第1層，子節(jié)點的子節(jié)點是第2層，以此類推。樹中任何一層的節(jié)點都可以看成是子樹的根，該子樹包含根節(jié)點的子節(jié)點，子節(jié)點的子節(jié)點等。我們定義樹的層數(shù)就是樹的深度。


節(jié)點的高度：節(jié)點到葉子節(jié)點的最長路徑（邊樹）。
節(jié)點的深度：根節(jié)點到這個節(jié)點所經(jīng)歷的邊的個數(shù)。
節(jié)點的層數(shù)：節(jié)點的深度+1。
節(jié)點的高度：根節(jié)點的高度。


下面舉個例子來看：





每一個節(jié)點都有一個與之關聯(lián)的值，該值有時被稱為鍵。


二叉樹是一種特殊的樹。它的子節(jié)點不超過2個。二叉樹具有一些特殊的計算性質(zhì)，使得在它之上的一些操作異常高效。

一個父節(jié)點的兩個子節(jié)點分別稱為左節(jié)點和右節(jié)點。左節(jié)點包含一組特定的值，右節(jié)點包含一組特定的值。

下圖展示了一顆二叉樹：



當考慮某種特殊的二叉樹，比如二叉查找樹時，確定子節(jié)點非常重要。二叉查找樹是一種特殊的二叉樹，相對較小的值保存在左節(jié)點中，較大的值保存在右節(jié)點中。這一特性使得查找的效率很高，對于數(shù)值和非數(shù)值的數(shù)據(jù)，比如單詞和字符串，也是如此。


我們來看下圖中的樹：





編號2的二叉樹中，葉子節(jié)點全在最底層，除了葉子節(jié)點以外的每個節(jié)點都有左右兩個子節(jié)點，這種二叉樹叫做滿二叉樹。


編號3的二叉樹中，葉子節(jié)點都在最底下兩層，最后一層的葉子節(jié)點都靠左排列，并且除了最后一層，其它層的節(jié)點個數(shù)都達到最大，這種二叉樹叫做完全二叉樹。

定義 Node?對象。

function node(data, left, right) {
    this.data = data;
    this.left = left;
    this.right = right;
    this.show = show;

    function show() {
        return this.data;
    }
}

現(xiàn)在可以創(chuàng)建一個 BST?類來表示二叉查找樹。我們讓類只包含一個數(shù)據(jù)成員：一個表示二叉查找樹根節(jié)點的 Node?對象。該類的構造函數(shù)將根節(jié)點初始化為?null ，以此創(chuàng)建一個空節(jié)點。

BST?首先要有一個?insert()?方法，用來向樹中插入新節(jié)點。首先要創(chuàng)建一個 Node?對象，將數(shù)據(jù)傳入該對象保存。
其次，檢查 BST?是否有根節(jié)點，如果沒有，則這是棵新樹，該節(jié)點就是根節(jié)點，這個方法到此也就結束了；否則，進入下一步。

如果待插入節(jié)點不是根節(jié)點，那么就準備遍歷 BST ，找到插入的適當位置。該過程類似遍歷鏈表。用一個節(jié)點保存當前節(jié)點，一層層地遍歷 BST 。

進入 BST?以后，下一步就需要確定將該節(jié)點放在什么位置。找到正確的插入點時，會跳出循環(huán)。

查找正確的插入點的算法如下：

設根節(jié)點為當前節(jié)點；

如果待插入的節(jié)點小于當前節(jié)點，則設新的當前節(jié)點為原節(jié)點的左節(jié)點；反之，執(zhí)行第四步；

如果當前節(jié)點的左節(jié)點為?null ，就將新的節(jié)點插入這個位置，退出循環(huán)；反之，繼續(xù)執(zhí)行下一次循環(huán)；

設新的當前節(jié)點為原節(jié)點的右節(jié)點；

如果當前節(jié)點的右節(jié)點為 null ，就將新的節(jié)點插入該位置，退出循環(huán)；反之，繼續(xù)執(zhí)行下一次循環(huán)。

function BST() {
    this.root = null;
    this.insert = insert;
  
    function insert(data) {
        var n = new Node(data, null, null);
        if(this.root == null) {
            this.root = n;
        }else {
            var currentNode = this.root;
            var parent;
            while(true) {
                parent = currentNode;
                if(data < currentNode.data) {
                    currentNode = currentNode.left;
                    if(currentNode == null) {
                        parent.left = n;
                        break;
                    }
                }else {
                    currentNode = currentNode.right;
                    if(currentNode.data == null) {
                        parent.right = n;
                        break;
                    }
                }
            }
        }
    }
  
}

另外一個寫法，其實思路是一樣的，但是上面的稍微簡潔一些。（代碼思路來自王爭老師的《數(shù)據(jù)結構與算法之美?》）

function insert(data) {
        var node = new Node(data, null, null);
        if(this.root == null) {
            this.root = node;
        }else {
            p = this.root;
            while(p !== null) {
                if(data < p.data) {
                    if(p.left == null) {
                        p.left = node;
                        return;
                    }
                    p = p.left;
                }else {
                    if(p.right == null) {
                        p.right = node;
                        return;
                    }
                    p = p.right;
                }
            }
        }
    }

有三種遍歷二叉樹的方法：中序、先序、后序。

中序遍歷按照節(jié)點上的鍵值，以升序訪問 BST?上的所有節(jié)點。
先序遍歷先訪問根節(jié)點，然后以同樣的方式訪問左子樹和右子樹。
后序遍歷先訪問葉子節(jié)點，從左子樹到右子樹，再到根節(jié)點。

先序遍歷是指，對于樹中的任意節(jié)點來說，先打印這個節(jié)點，然后在打印它的左子樹，最后打印它的右子樹。
中序遍歷是指，對于樹中的任意節(jié)點來說，先打印它的左子樹，然后打印它自己，最后打印它的右子樹。
后序遍歷是指，對于樹中的任意節(jié)點來說，先打印它的左子樹，然后打印它的右子樹，最后打印它自己。

中序遍歷的代碼如下：

function inOrder(node) {
        if(!(node == null)) {
            this.inOrder(node.left);
            console.log(node.show());
            this.inOrder(node.right);
        }
    }

var bst = new BST();
bst.insert(17)
bst.insert(19)
bst.insert(16)
bst.insert(34)
bst.insert(35)
bst.insert(36)
bst.inOrder(bst.root); // 16 17 19 34 35 36

下圖展示中序遍歷的訪問路徑：

先序遍歷的代碼如下：

function perOrder(node) {
        if(!(node == null)) {
            console.log(node.show());
            this.perOrder(node.left);
            this.perOrder(node.right);
        }
}

var bst = new BST();
bst.insert(17)
bst.insert(19)
bst.insert(16)
bst.insert(34)
bst.insert(35)
bst.insert(36)
console.log("先序遍歷");
bst.perOrder(bst.root); // 17 16 19 34 35 36

下圖展示先序遍歷的訪問路徑：

后序遍歷的代碼：

var bst = new BST();
bst.insert(17)
bst.insert(19)
bst.insert(16)
bst.insert(34)
bst.insert(35)
bst.insert(36)

console.log("后序遍歷");
bst.postOrder(bst.root); // 16 36 35 34 19 17

下圖展示后序遍歷的訪問路徑：

對 BST?通常有以下三種類型的查找：

查找給定值

查找最大值

查找最小值

因為較小的值總在左節(jié)點上，在 BST?上查找最小值，只需要遍歷左子樹，知道找到最后一個節(jié)點即可。

function getMin() {
        let currentNode = this.root;
        while(currentNode.left != null) {
            currentNode = currentNode.left;
        }
        return currentNode.data;
    }

在BST?上查找最大值，只需要遍歷右子樹，知道找到最后一個節(jié)點即可。

function getMax() {
        let currentNode = this.root;
        while(currentNode.right != null) {
            currentNode = currentNode.right;
        }
        return currentNode.data;
    }

在 BST?上查找給定的值，需要比較該值和當前節(jié)點值的大小。通過比較，就能確定如果給定值不在當前節(jié)點上，該向左遍歷還是向右遍歷。

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

如果找到給定值，該方法返回保存該值的方法；如果沒找到，該方法返回?null。

從 BST?上刪除節(jié)點的操作最復雜，其復雜程度取決于刪除哪個節(jié)點。如果刪除沒有子節(jié)點的節(jié)點，那么非常簡單。如果節(jié)點只有一個子節(jié)點，就變得稍微復雜了。如果節(jié)點有兩個子節(jié)點，是最復雜的。

分三種情況來處理：

如果要刪除的節(jié)點沒有子節(jié)點，我們只需要將父節(jié)點中，指向要刪除的節(jié)點的指針置為?null。比如圖中刪除節(jié)點55。

如果要刪除的節(jié)點只有一個子節(jié)點（左子節(jié)點或者右子節(jié)點），我們只需要更新父節(jié)點中，指向要刪除節(jié)點的指針，讓它指向要刪除節(jié)點的子節(jié)點就可以了。比如圖中刪除節(jié)點13。

如果要刪除的節(jié)點有兩個子節(jié)點，我們需要找到這個節(jié)點右子樹中的最小節(jié)點，把它替換到要刪除節(jié)點上，然后再刪除這個最小節(jié)點，因為最小節(jié)點中肯定沒有左子節(jié)點，我們可以用這兩個規(guī)則來進行刪除操作，比如圖中刪除節(jié)點18。

function deleteNode(data) {
        var p = this.root; // p指向刪除的節(jié)點，初始化為根節(jié)點
        var pp = null; // pp記錄P的父節(jié)點
        while(p != null && p.data != data) {
            pp = p;
            if(data > p.data) {
                p = p.right;
            }else {
                p = p.left;
            }
        }
        if(p == null) return; // 沒有找到

        if(p.left != null && p.right != null) { // 要刪除的節(jié)點有兩個子節(jié)點
            // 查找右子樹中的最小節(jié)點
            var minP = p.right;
            var minPP = p; // minPP表示minP的父節(jié)點
            while(minP.left != null) {
                pnode = minP;
                minP = p.left;
            }
            p.data = minP.data; // 將minP的數(shù)據(jù)替換到p中
            p = minP; //下面就變成刪除minP了
            pp = minP;

        }
        // 刪除節(jié)點是葉子節(jié)點或者只有一個子節(jié)點
        var childNode = null;
        if(p.left != null) {
            childNode = p.left;
        }else if(p.right != null) {
            childNode = p.right;
        }else {
            chiildNode = null;
        }
        if(pp == null) {
            p = chiildNode; // 刪除的是根節(jié)點
        }else if(pp.left == p) {
            pp.left = childNode;
        }else {
            pp.right = childNode;
        }
    }

實際上，關于二叉樹的刪除操作，還有個非常簡單、取巧的方法，就是單純地將已刪除的節(jié)點標記為“已刪除”，但并不是真正的刪除。這樣原本要刪除的元素還存儲在內(nèi)存中，比較浪費內(nèi)存空間，但是刪除操作簡單了很多，也沒有增加插入和查找的代碼實現(xiàn)的難度。

二叉查找樹還有一個重要的特性，就是中序遍歷二叉查找樹，可以輸入有序的數(shù)據(jù)序列，時間復雜度是O(n)，非常高效。因此二叉查找樹也被叫做二叉排序樹。