什么是树？

树是一种分层数据的抽象模型。现实生活中最常见的树的例子就是家谱，或是公司的组织架构。

树的结构图：如下图



树的相关术语：

一棵树包含一系列存在父子关系的节点。每个节点都有一个父节点(除了顶部的第一个节点)以及零个或多个子节点.下面介绍几个常见的树的术语。

根节点：位于树顶部的节点，它没有父节点
	
内部节点：至少有一个子节点的节点
	
外部节点：没有子节点的节点，也称为叶节点
	
子树：子树由节点和它的后代构成，如树的结构图中的子树
	
节点的深度：节点的祖先节点的数量
	
树的高度：所有节点深度的最大值
二叉树和二叉搜索树：

二叉树是一种特殊的树结构，二叉树中的节点最多只能有了两个子节点，一个是左侧节点，另一个是右侧节点。

二叉搜索树(BST)：二叉搜索树是二叉树的一种，但是它只允许你在左侧节点存储(比父节点)小的值，在右侧节点存储(比父节点)大(或者等于)的值，如上面的树结构就是典型的二叉搜索树。

二叉搜索树的每一个节点也有两个指针，分别指向左侧子节点和右侧子节点。如下图：



注意：规范来说，键是树的相关术语中对节点的称呼。

js实现二叉搜索树的相关定义与方法：

首先是定义一个树的类，因为树的每个节点都有左子树和右子树，所以在定义节点的时候需要指定两个指针。二叉树中的一些方法有向树中插入一个节点，以及寻找树中的最小值和最大值，代码如下：

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

        //向树中插入一个新的键
        this.insert = function (key) {
            //创建一个用来表示新节点的Node实例
            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);
                }
            }
        };
 //搜索树中的最小值
        this.min = function () {
            return minNode(root);
        }
        var minNode = function (node) {
            if (node){
                while (node && node.left !== null){
                    node = node.left;
                }
                return node.key;
            }
            return null;
        }

        //搜索树中的最大值
        this.max = 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);
        }
        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;
            }
        }
}

二叉树的遍历：

二叉树的遍历是树结构的经典，主要有三种，分别是先序，中序和后序，代码如下：

       //树的中序遍历
        this.inOrderTraverse = function (callback) {
            inOrderTraverseNode(root, callback);
        }

        var inOrderTraverseNode = function (node, callback) {
            //这里的回调函数用来定义我们对遍历到的每个节点进行的操作
            if (node !== null){
                inOrderTraverseNode(node.left, callback);
                callback(node.key);
                inOrderTraverseNode(node.right,callback);
            }
        }

        //先序遍历
        this.preOrderTraverse = function (callback) {
            preOrderTraverseNode(root, callback);
        }

        var preOrderTraverseNode = function (node , callback) {
            if (node !== null){
                //先序遍历会先访问节点本身，然后再访问它的左侧子节点，最后是右侧子节点
                callback(node.key);
                preOrderTraverseNode(node.left, callback);
                preOrderTraverseNode(node.right, callback);
            }
        }

        //后序遍历
        this.postOrderTraverse = function (callback) {
            postOrderTraverseNode(root, callback);
        }

        var postOrderTraverseNode = function (node , callback) {
            if (node !== null){
                //后序遍历会先访问它的左侧子节点，再访问右侧子节点，最后是父节点本身
                postOrderTraverseNode(node.left, callback);
                postOrderTraverseNode(node.right, callback);
                callback(node.key);
            }
        }

最后是二叉树的删除节点，根据某个特定的值，找到树中的值相等的节点，并删除。这里面的情况比较复杂，需要分多种情况讨论，尤其是找到该节点后。删除了该节点还要考虑将该节点的父元素的指针转移，具体分析和代码如下：

//移除一个节点
        this.remove = function (key) {
            root = removeNode(root,key);
        }
        var removeNode = function (node ,key) {//node表示当前访问的节点
            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 {//键等于node.key
                /*第一种情况，相等的节点是一个叶子节点
                移除了节点之后，需要将节点的父节点的指针赋予null值，当节点的值是null后，父节点指向它
                的指针会接收到这个值，所以要在最后返回这个节点node；第二种情况，当前的节点只有左侧子
                节点或者右侧子节点的时候，也需要将当前节点的父节点的指针指向当前节点的左侧子节点或者
                右侧子节点；
                第三种情况，如果当前节点既有左侧子节点又有右侧子节点时，这时首先需要找到当前结点的右边
                子树中最小的节点，然后用这个最小的节点替换当前节点，同时移除原来的最小的节点，更新其
                父节点的指针
                */
                if (node.left === null  && node.right === null){
                    node = null;
                    return node;
                }
                //第二种情况，相等的节点是只有一个子节点的节点
                if (node.left === null){
                    node = node.right;
                    return node;
                }else if (node.right === null){
                    node = node.left;
                    return node;
                }
                //第三种情况，相等的节点是有两个子节点的节点
                var aux = findMinNode(node.right);
                node.key = aux.key;//最小的值的节点替换当前节点
                node.right = removeNode(node.right, aux.key);//移除原右子树的最小的节点
                return node;//更改父节点的指针
            }
        }
        var findMinNode = function (node) {
            while (node && node.left !== null){
                node = node.left;
            }
            return node;
        }


树的使用：

树的使用主要是调用以上的方法，具体代码和输出如下：

var tree = new BinarySearchTree();
    tree.insert(11);
    tree.insert(7);
    tree.insert(15);
    tree.insert(5);
    tree.insert(3);
    tree.insert(9);
    tree.insert(8);
    tree.insert(10);
    tree.insert(13);
    tree.insert(12);
    tree.insert(14);
    tree.insert(20);
    tree.insert(18);
    tree.insert(25);
    tree.insert(6);
    function printNode(value) {
        console.log(value);
    }
    console.log('树中序遍历的结果为：')
    tree.inOrderTraverse(printNode);
    //输出为：3 5 6 7 8 9 10 11 12 13 14 15 18 20 25

    console.log('树先序遍历的结果为：')
    tree.preOrderTraverse(printNode);
    //输出为：11 7 5 3 6 9 8 10 15 13 12 14 20 18 25

    console.log('树后序遍历的结果为：')
    tree.postOrderTraverse(printNode);
    //输出为：3 6 5 8 10 9 7 12 14 13 18 25 20 15 11

    //找到树中最小值和最大值
    console.log('树中的最小值为：'+tree.min());//输出3
    console.log('树中的最大值为：'+tree.max());//输出25

    //搜索树种某个特定的值
    console.log(tree.search(12)? 'key 12 found': 'key 12 not found');//输出key 12 found
    console.log(tree.search(2)? 'key 2 found': 'key 2 not found');//输出key 2 ot found