樹是一種分層數(shù)據(jù)的抽象模型。它和散列表一樣是一種非順序數(shù)據(jù)結(jié)構(gòu)，它對于存儲需要快速查找的數(shù)據(jù)非常有用船侧。

樹的相關(guān)術(shù)語

一個樹結(jié)構(gòu)包含一系列存在父子關(guān)系的節(jié)點(diǎn)。每個節(jié)點(diǎn)都有一個父節(jié)點(diǎn)（除了頂部的第一個節(jié)點(diǎn)）以及零個或多個子節(jié)點(diǎn)厅各。

樹形結(jié)構(gòu)圖

根節(jié)點(diǎn)：位于樹頂部的節(jié)點(diǎn)叫做根節(jié)點(diǎn)勺爱，沒有父節(jié)點(diǎn)。
內(nèi)部節(jié)點(diǎn)和外部節(jié)點(diǎn)：樹中每個元素都叫做節(jié)點(diǎn)讯检，節(jié)點(diǎn)分為內(nèi)部節(jié)點(diǎn)和外部節(jié)點(diǎn)琐鲁。至少有一個子節(jié)點(diǎn)的節(jié)點(diǎn)被稱為內(nèi)部節(jié)點(diǎn)（B、D人灼、C围段、E）。沒有子節(jié)點(diǎn)的節(jié)點(diǎn)被稱為外部節(jié)點(diǎn)或葉節(jié)點(diǎn)（G投放、H奈泪、I、F）灸芳。
節(jié)點(diǎn)的祖先和后代：一個節(jié)點(diǎn)（除了根節(jié)點(diǎn)）的祖先包括父節(jié)點(diǎn)涝桅、祖父節(jié)點(diǎn)、曾祖父節(jié)點(diǎn)等烙样。一個節(jié)點(diǎn)的后代包括子節(jié)點(diǎn)冯遂、孫子節(jié)點(diǎn)、曾孫節(jié)點(diǎn)等谒获。例如D節(jié)點(diǎn)的祖先節(jié)點(diǎn)有B節(jié)點(diǎn)和A節(jié)點(diǎn)蛤肌，后代節(jié)點(diǎn)有G節(jié)點(diǎn)和H節(jié)點(diǎn)。
子樹：子樹由節(jié)點(diǎn)和它的后代構(gòu)成批狱。例如節(jié)點(diǎn)D裸准、G、H赔硫、就構(gòu)成了上圖中樹的一顆子樹炒俱。
節(jié)點(diǎn)深度：節(jié)點(diǎn)的深度取決于它的祖先元素的節(jié)點(diǎn)數(shù)量。比如節(jié)點(diǎn)G有三個祖先節(jié)點(diǎn)D、B权悟、A砸王，所有它的深度為3。
樹的高度取決于所有節(jié)點(diǎn)深度的最大值僵芹。一棵樹可以分解成層級处硬。根節(jié)點(diǎn)在0層，B節(jié)點(diǎn)在1層拇派、D節(jié)點(diǎn)在2層荷辕、G節(jié)點(diǎn)在3層，以此類推件豌。所有上圖中的樹高度為3疮方。

二叉樹和二叉樹搜索

二叉樹中的節(jié)點(diǎn)最多只能有兩個子節(jié)點(diǎn)：一個是左側(cè)幾點(diǎn)，一個是右側(cè)節(jié)點(diǎn)茧彤。
二叉樹搜索樹（BST）：是二叉搜索樹的一種骡显，但是它只允許在左側(cè)節(jié)點(diǎn)存儲（比父節(jié)點(diǎn)）小的值，在右側(cè)節(jié)點(diǎn)存儲（比父節(jié)點(diǎn)）大的值曾掂。
中序遍歷：是一種以上行順序訪問BST所有節(jié)點(diǎn)的遍歷方式惫谤，也就是以從小到最大的順序訪問所有節(jié)點(diǎn)。
先序遍歷：是以優(yōu)先于后代節(jié)點(diǎn)的順序訪問每個節(jié)點(diǎn)的珠洗。先序遍歷的一種應(yīng)用是打印一個結(jié)構(gòu)化的文檔溜歪。
后序遍歷：是先訪問節(jié)點(diǎn)的后代節(jié)點(diǎn)，在訪問節(jié)點(diǎn)本身许蓖。后序遍歷的一種應(yīng)用是計(jì)算一個目錄和它的子目錄所有文件所占空間的大小蝴猪。

function BinarySearchTree() {
    var Node = function (key) {
        this.key = key;
        this.left = null;
        this.right = null;
    };
    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);
            }
        }
    };

    var inOrderTraversalNode = function (node, callback) {
        //中序遍歷
        if(node !== null) {
            inOrderTraversalNode(node.left, callback);
            callback(node.key);
            inOrderTraversalNode(node.right, callback);
        }
    };
    var preOrderTraversalNode = function (node, callback) {
        //先序遍歷
        if(node !== null) {
          callback(node.key);
          preOrderTraversalNode(node.left, callback);
          preOrderTraversalNode(node.right, callback);
        }
    };

    var postOrderTraversalNode = function (node, callback) {
        //后序遍歷
        if(node !== null) {
            postOrderTraversalNode(node.left, callback);
            postOrderTraversalNode(node.right, callback);
            callback(node.key);
        }
    };

    var minNode = function (node) {
        //查找最最小值
        if(node !== null) {
            while (node && node.left !== null) {
                node = node.left;
            }
            return node.key;
        }
        return null;
    };

    var maxNode = function (node) {
        //查找最大值
        if(node !== null) {
            while (node && node.right !== null) {
                node = node.right;
            }
            return node.key;
        }
        return null;
    };
    var getMixNode = function (node) {
        //查找鍵值最小的節(jié)點(diǎn)返回
        if(node !== null) {
            while (node && node.left !== null) {
                node = getMixNode(node.left);
            }
            return node;
        }
        return null;
    };

    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;
        }
    };

    var removeNode = function (node, key) {
        if (node === null) {
            //當(dāng)節(jié)點(diǎn)等于null說明不存在直接返回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 {
            if(node.left === null && node.right === null) {
                return null;
            }
            if(node.left === null) {
                node = node.right;
                return node;
            }
            if(node.right === null) {
                node = node.left;
                return node;
            }
            var aux = getMixNode(node.right);
            node.key = aux.key;
            removeNode(node.right, aux.key);
        }
    };

    var root = null;

    this.insert = function (key) {
        //向樹中插入一個新鍵
        var newNode = new Node(key);
        if (root === null) {
            root = newNode;
        }else {
            insertNode(root, newNode);
        }
    };

    this.search = function (key) {
        //在樹中查找一個鍵，如果存在返回true否則false
        return searchNode(root, key);
    };

    this.inOrderTraversal = function (callback) {
        //通過中序遍歷方式遍歷所有節(jié)點(diǎn)
        inOrderTraversalNode(root, callback);
    };

    this.preOrderTraversal = function (callback) {
        //通過先序遍歷方式遍歷所有節(jié)點(diǎn)
        preOrderTraversalNode(root, callback);
    };

    this.postOrderTraversal = function (callback) {
        //通過后續(xù)遍歷方式遍歷所有節(jié)點(diǎn)
        postOrderTraversalNode(root, callback);
    };
    this.min = function () {
        //返回樹中最小值/鍵
        return minNode(root);
    };

    this.max = function () {
      //返回樹中最大值/鍵
        return maxNode(root);
    };

    this.remove = function (key) {
        //從樹中移除某個鍵
        return removeNode(root, key);
    };

}


var tree = new BinarySearchTree();
tree.insert(55);
tree.insert(88);
tree.insert(17);
tree.insert(65);
tree.insert(4);
tree.insert(5);
tree.insert(6);
tree.insert(5);
tree.insert(8);
tree.insert(78);
tree.insert(87);
tree.insert(27);
tree.insert(17);
tree.insert(28);

function printNode(value) {
    console.log(value);
}

tree.inOrderTraversal(printNode); //4 5 5 6 8 17 17  27 28 55 65 78 87 88
tree.preOrderTraversal(printNode);//55 17 4 5 6 5 8 27 17 28 88 65 78 87
tree.postOrderTraversal(printNode);// 5 8 6 5 4 17 28 27 17 87 78 65 88 55
console.log(tree.min()); //4

console.log(tree.search(20)); //false
tree.remove(88); //false
console.log(tree.max()); //87

查找樹中的最大最小值：因?yàn)樵跇渲胁沧Γ畲笾翟跇涞淖詈笠粚幼钣覀?cè)自阱，最小值在樹的最后一層最左側(cè)。所以通過遞歸（邊界條件為節(jié)點(diǎn)是否還有左側(cè)或者右側(cè)子節(jié)點(diǎn)）的方式米酬，當(dāng)子節(jié)點(diǎn)為null時返回當(dāng)前鍵沛豌。
移除一個節(jié)點(diǎn)：通過遞歸調(diào)用，查找到符合要移除的鍵的節(jié)點(diǎn)淮逻。當(dāng)鍵比當(dāng)前節(jié)點(diǎn)的值小琼懊，就沿著左側(cè)繼續(xù)查找。當(dāng)鍵比當(dāng)前節(jié)點(diǎn)的值大就沿著右側(cè)查找爬早。當(dāng)查找到的節(jié)點(diǎn)沒有子節(jié)點(diǎn)時，就會返回一個null值启妹，然后將最后一次遞歸調(diào)用傳入的節(jié)點(diǎn)（也就是和鍵相符合的節(jié)點(diǎn)）設(shè)置成返回的null值筛严，然后返回此節(jié)點(diǎn)。

移除有一個左側(cè)或者右側(cè)的節(jié)點(diǎn)：當(dāng)此節(jié)點(diǎn)左側(cè)沒有節(jié)點(diǎn)時饶米，就把把對此節(jié)點(diǎn)的引用指向此節(jié)點(diǎn)的右側(cè)子節(jié)點(diǎn)桨啃。當(dāng)此節(jié)點(diǎn)右側(cè)沒有節(jié)點(diǎn)時车胡，就把把對此節(jié)點(diǎn)的引用指向此節(jié)點(diǎn)的左側(cè)子節(jié)點(diǎn)。
移除有兩個子節(jié)點(diǎn)的節(jié)點(diǎn)：當(dāng)要移除有兩個字節(jié)點(diǎn)的節(jié)點(diǎn)時照瘾，它的繼承者就是它右邊子樹中最小的節(jié)點(diǎn)匈棘。所以首先查找到它右側(cè)最小節(jié)點(diǎn)，然后將此節(jié)點(diǎn)的值改為它右側(cè)最小節(jié)點(diǎn)的值析命，然后再移除右側(cè)最小節(jié)點(diǎn)主卫，因?yàn)樗呀?jīng)替代了別的節(jié)點(diǎn)位置。