定義

• 二叉樹

二叉樹在圖論中是這樣定義的：二叉樹是一個連通的無環(huán)圖，并且每一個頂點的度不大于3。有根二叉樹還要滿足根結(jié)點的度不大于2。有了根結(jié)點之后，每個頂點定義了唯一的父結(jié)點，和最多2個子結(jié)點。然而，沒有足夠的信息來區(qū)分左結(jié)點和右結(jié)點。如果不考慮連通性，允許圖中有多個連通分量，這樣的結(jié)構(gòu)叫做森林。

• 二叉查找樹

二叉排序樹或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹：
（1）若左子樹不空，則左子樹上所有結(jié)點的值均小于或等于它的根結(jié)點的值；
（2）若右子樹不空，則右子樹上所有結(jié)點的值均大于或等于它的根結(jié)點的值；
（3）左、右子樹也分別為二叉排序樹；

實現(xiàn)二叉查找樹

BST 的基本方法

要實現(xiàn)二叉查找樹，首先實現(xiàn) Node 類，Node 類定義如下：

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

我們可以定義一個二叉查找樹類（BST）如下：

// BST類
function BST() {
    this.root = null;
    this.insert = insert; // 插入數(shù)據(jù)方法
}

接著我們實現(xiàn)一個 insert 方法，實現(xiàn)這個方法的思路：

首先檢查 BST 是否有根節(jié)點，如果沒有，則這是一個新樹，這個需要插入的數(shù)據(jù)就成為了根節(jié)點，這個方法就完成了；否則，進入下一步。

1. 設(shè)置根節(jié)點為當前節(jié)點。

2. 如果待插入數(shù)據(jù)小于當前節(jié)點的數(shù)據(jù)，則設(shè)置新的當前節(jié)點為原節(jié)點的左節(jié)點；反之，執(zhí)行第4步。

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

4. 設(shè)置新的當前節(jié)點為原節(jié)點的右節(jié)點。

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

所以，我們現(xiàn)在可以實現(xiàn) insert 方法如下：

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

遍歷二叉查找樹

BST 類目前已經(jīng)初步成型，我們已經(jīng)可以插入數(shù)據(jù)，現(xiàn)在我們還需要有能力遍歷
BST ， 我們有三種遍歷 BST 的方式： 中序、先序和后序。

前序遍歷：根節(jié)點->左子樹->右子樹
中序遍歷：左子樹->根節(jié)點->右子樹
后序遍歷：左子樹->右子樹->根節(jié)點

則 BST 類現(xiàn)在可以寫成如下：

// BST類
function BST() {
    this.root = null;
    this.insert = insert; // 插入數(shù)據(jù)方法
    this.inOrder = inOrder; // 中序遍歷
    this.preOrder = preOrder; // 先序遍歷
    this.postOrder = postOrder; // 后序遍歷
}

現(xiàn)在我們首先實現(xiàn)中序遍歷方法如下：

function inOrder(node) {
    if(node) {
        inOrder(node.left);
        console.log(node.show() + " ");
        inOrder(node.right);
    }
}

先序遍歷如下：

// 先序遍歷 
function  preOrder (node) {
    if (node) {
        console.log(node.show()+"");
        preOrder(node.left);
        preOrder(node.right);
    }
}

后序遍歷如下：

// 后序遍歷
function postOrder(node) {
    if (node) {
        postOrder(node.left);
        postOrder(node.right);
        console.log(node.show()+"");
    }
}