js代码实现二叉查找树的算法

理论

二叉查找树（Binary Search Tree），又称二叉排序树或二叉搜索树，是属于二叉树的一种。它最大的特点是每个节点的左子节点永远比该节点小，而每个节点的右子节点却永远比该节点大，即任意节点的左子树上所有结点永远比该节点的右子树上所有结点的值小，它的任意左、右子树也分别为二叉查找树。

代码

以下是使用js代码来实现。

先定义二叉查找树的节点：

/**
 * 树的节点
 * @param  data  节点的数值
 * @param  left  该节点的左子节点
 * @param  right 该节点的右子节点
 */
function TreeNode(data, left, right) {
    this.data = data;
    this.left = left || null;
    this.right = right || null;
}

定义二叉树：

/**
 * 二叉查找树
 * @param  rootNode 根节点
 */
function BinarySearchTree(rootNode) {
    this.rootNode = rootNode || null;
}

BinarySearchTree.prototype = {
    // 后面讲的查找，新增，删除功能会放在本区域（即原型）
}

二叉查找树的新增功能

插入工作必须按照二叉查找树的特性来完成。

1. 首先判断该二叉树是否有根节点，如果没有则把新节点作为根节点，反之则继续；
2. 从根节点开始逐级比较，即如果新结点的值小于根节点的值，则将新结点与根节点的左子树中的节点去比较，大于则与根节点的右子树中的节点去比较；
3. 逐级比较直到找到需要插入的空位为止，把新节点放入即可；

新增代码如下：

/**
* 插入节点
* @param   data 需要插入节点的值
*/
function insert(data) {
   // 生成新的节点
   var newNode = new TreeNode(data);
   // 判断根节点是否存在
   if (!this.rootNode) {
       this.rootNode = newNode;
       return;
   }
   var currentNode = this.rootNode;
   var parent = null;
   while (true) {
       parent = currentNode;
       if (data < currentNode.data) {
           currentNode = currentNode.left;
           if (!currentNode) {
               parent.left = newNode;
               return;
           }
       } else if (data > currentNode.data) {
           currentNode = currentNode.right;
           if (!currentNode) {
               parent.right = newNode;
               return;
           }
       } else {
           console.log("该节点已存在");
           return;
       }
   }
}

二叉查找树的查找功能

查找功能其实与新增功能类似，首先要判断根节点是否存在，然后需要把待查找的节点从根节点开始逐级比较查找，规则同样是左子树的节点永远小于右子树的节点，直到找到为止。

/**
* 查找节点
* @param   data 待查找节点的值
*/
function: find(data) {
    // 判断根节点是否存在
    if (!this.rootNode) {
        return;
    }
    var currentNode = this.rootNode;
    while (true) {
        if (!currentNode) {
            console.log("该节点不存在");
            return;
        }
        if (data < currentNode.data) {
            currentNode = currentNode.left;
        } else if (data > currentNode.data) {
            currentNode = currentNode.right;
        } else {
            return currentNode;
        }
    }
}

二叉查找树的节点删除功能

删除功能就比较复杂了，主要分三种情况：

1. 待删除节点无子节点时，直接删除节点即可；
2. 待删除节点只有右子树或只有左子树时，直接把待删除节点的父节点的指针指向待删除节点的右子树或右子树即可，然后删除节点；
3. 这种情况相对较复杂，就是待删除节点既有左节点又有右节点。通常有两种方法来解决：
   
   1. 从待删除节点的左子树选出最大的节点即最靠近右边的节点来顶替删除后腾出的节点位置；
   2. 从待删除节点的右子树选出最小的节点即最靠近左边的节点来顶替删除后腾出的节点位置；

具体流程如下：
1. 查找到待删除的结点和它的父节点；
2. 判断该节点有无左右子树，如果没有，那么直接删除；
3. 如果只有左右子树中的一个，那么直接它的父节点指向它的左子树或右子树，然后删除节点；
4. 如果左右子树都有，本人按照从左子树的取最大的节点方法列实行；

/**
* 删除目标节点
* @param   data 待删除目标节点的值
*/
function removeNode(data) {
    // 判断根节点是否存在
    if (!this.rootNode) {
        return;
    }
    // 目标节点的父节点
    var parent = null;
    // 目标节点
    var currentNode = this.rootNode;
    // 目标节点位于父节点的位置
    var place = null;
    while (true) {
        if (!currentNode) {
            console.log("该节点不存在");
            return;
        }
        if (data < currentNode.data) {
            parent = currentNode;
            currentNode = currentNode.left;
            place = "left";
        } else if (data > currentNode.data) {
            parent = currentNode;
            currentNode = currentNode.right;
            place = "right";
        } else {
            // 找到对应节点跳出循环
            break;
        }
    }

    if (!currentNode.left) {
        // 删除的节点没有左孩子的情况
        parent[place] = currentNode.right || null;
    } else if (!currentNode.right) {
        // 删除的节点没有右孩子的情况
        parent[place] = currentNode.left || null;
    } else {
        // 用于代替的节点
        var replaceNode = currentNode.left;
        // 代替节点的父节点
        var replaceNodeParent = null;
        // 循环找出左子树中最大的节点（即用于代替的节点）
        while(replaceNode.right) {
            replaceNodeParent = replaceNode;
            replaceNode = replaceNode.right;
        }
        // 代替原位置
        parent[place] = replaceNode;
        // 当代替节点就是删除的节点的左子节点时无需赋左子树
        if (replaceNodeParent) {
            replaceNodeParent.right = replaceNode.left || null;
            parent[place].left = currentNode.left;
        }
        // 获取删除的节点的右子树
        parent[place].right = currentNode.right;
    }
    return;
}

以上即是具体讲解，整套代码如下：