JavaScript的数据结构与算法（五） —— 二叉搜索树

摘要：简介二叉树是一种非常重要的数据结构，很多其它数据结构都是基于二叉树的基础演变而来的。二叉搜索树是二叉树的一种，但是它只允许你在左侧节点存储比父节点小的值，在右侧节点存储比父节点大或者等于的值。树的高度，树的高度体现为节点深度的最大值。

二叉树是一种非常重要的数据结构，很多其它数据结构都是基于二叉树的基础演变而来的。

对于二叉树，有深度遍历和广度遍历，深度遍历有前序、中序以及后序三种遍历方法，广度遍历即我们平常所说的层次遍历。因为树的定义本身就是递归定义，因此采用递归的方法去实现树的三种遍历不仅容易理解而且代码很简洁，而对于广度遍历来说，需要其他数据结构的支撑，比如堆了。

二叉树中的节点最多只能有两个节点：一个是左侧子节点，另一个是右侧子节点。
二叉搜索树（BST）是二叉树的一种，但是它只允许你在左侧节点存储（比父节点）小的值，在右侧节点存储（比父节点）大（或者等于）的值。

树中的每个元素，都叫做节点。从节点延伸而下的，叫子节点。
树顶部的节点叫根节点。每棵树只有一个根节点。
在节点中，有子节点的节点也称为内部节点，没有的话则被称为外部节点或者叶节点。
同时在节点中是有祖先和后代关系的，比如节点9的祖先就有13,7,6,15四个。

深度: 节点的深度取决于其祖先的数量，节点9的深度就是4。
树的高度，树的高度体现为节点深度的最大值。
比如上图，节点深度最大值为4，则树的高度为4。

下面我们先来简单实现一个二叉搜索树类，并包含以下的方法：

insert(key): 向树中插入一个新的键

min(): 返回树中最小的值

max(): 返回树中最大的值

search(key): 搜索某个值，在树中则返回true

remove(key): 从树中移除某个键

代码如下：

function BinarySearchTree() {
    var Node = function(key){ //数据结构类
        this.key = key;
        this.left = null;
        this.right = null;
    };
    var root = null; //根节点
    this.insert = function(key){ //插入新的键
        var newNode = new Node(key);
        //special case - first element
        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.getRoot = function(){
        return root;
    };
    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.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.remove = function(element){
        root = removeNode(root, element);
    };
    var findMinNode = function(node){ //返回节点
        while (node && node.left !== null) {
            node = node.left;
        }
        return node;
    };
    var removeNode = function(node, element){ //移除一个节点
        if (node === null){
            return null;
        }
        if (element < node.key){
            node.left = removeNode(node.left, element);
            return node;
        } else if (element > node.key){
            node.right = removeNode(node.right, element);
            return node;
        } else { //命中后分三种情况         
            //移除叶子节点，即该节点没有左侧或者右侧子节点的叶结点
            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; //返回更新后节点的引用
        }
    };
}

前序遍历：根结点 ---> 左子树 ---> 右子树
中序遍历：左子树---> 根结点 ---> 右子树
后序遍历：左子树 ---> 右子树 ---> 根结点
层次遍历：只需按层次遍历即可

例如，求下面二叉树的各种遍历

前序遍历：1 2 4 5 7 8 3 6
中序遍历：4 2 7 5 8 1 3 6
后序遍历：4 7 8 5 2 6 3 1
层次遍历：1 2 3 4 5 6 7 8

代码实现如下：

/**
 * 先序遍历
 * @param {any} callback 回调函数
 */
this.preOrderTranverse = function (callback) {
    preOrderTranverseNode(root, callback)
}
var preOrderTranverseNode = function (node, callback) {
    if (node !== null) {
        callback && callback(node.key);
        preOrderTranverseNode(node.left, callback);
        preOrderTranverseNode(node.right, callback);
    }
}

代码实现如下：
/**

中序遍历

@param {any} callback 回调函数
*/

this.inOrderTraverse = function (callback) {

inOrderTraverseNode(root, callback)

}
var inOrderTraverseNode = function (node, callback) {

if (node !== null) {
    inOrderTraverseNode(node.left, callback);
    callback && callback(node.key)
    inOrderTraverseNode(node.right, callback);
}

}

代码实现如下：

 /**
  * 后序遍历
  * @param {any} callback 回调函数
  */
 this.postOrderTranverse = function (callback) {
     postOrderTranverseNode(root, callback);
 }
 var postOrderTranverseNode = function (node, callback) {
     if (node !== null) {
         postOrderTranverseNode(node.left, callback);
         postOrderTranverseNode(node.right, callback);
         callback(node.key);
     }
 }