js实现二叉查找树的建立、插入、删除、遍历操作

概念

二叉排序树（二叉查找树），它或者是一颗空树，或者是具有以下性质的二叉树：

• 任意一个结点左子树上的所有结点值均小于该结点值
• 任意一个结点右子树上的所有结点值均大于该结点值

例如下图：

插入和建立二叉排序树

结点的数据结构

function newNode(value){
    this.value = value;
    this.left = null;
    this.right = null;
}

插入操作

插入操作很简单，即用递归依次比较插入值与结点值的大小，找到插入的位置

function InsertNode(root, key){
    if (!root.value){   //如果根结点不存在，则建立根结点
        root.value = key;
        return true; 
    }

    if (root.value > key){  //当前结点值比插入值大，说明插入位置在当前结点值的左子树中
        if (root.left){  //如果有左孩子结点，继续比较
            InsertNode(root.left, key);
        }else{   //插入操作
            root.left = new newNode(key);
        }
    }else if (root.value < key){ //当前结点值比插入值小，说明插入位置在当前结点值的右子树中
        if (root.right){ //如果有右孩子结点，继续比较
            InsertNode(root.right, key);
        }else{  //插入操作
            root.right = new newNode(key);
        }
    }else{  //树中已存在插入值的结点
        return false;
    }

    return true;
}

建立操作

二叉排序树的建立就是多次执行插入操作

function create(array){
    var tree = new newNode(null);  //建立根节点
    for (let i=0; i < array.length; i++){
        InsertNode(tree, array[i]);
    }
    return tree;
}

遍历

二叉排序树中序遍历的输出结果就是结点值从小到大排序的结果

function InOrderTraverse(root){
    if (!root) return;
    InOrderTraverse(root.left);
    console.log(root.value);
    InOrderTraverse(root.right);
}

查找

二叉树的查找课简单地细分成：

• 查找二叉树的最大最小值；
• 给定值在二叉树中进行查找。

查找最大最小值

function getMin(root) {
    var current = this.root;
    while(current.left != null) {
        current = current.left;
    }
    return current.value;
};

function getMax(root) {
    var current = this.root;
    while(current.right != null) {
        current = current.right;
    }
    return current.value;
};

查找给定值

• 节点值和给定值相当 => 返回该节点；
• 给定值 < 节点值 => 查找当前节点的左节点，用左节点的值和给定值比较；
• 给定值 > 节点值 => 查找当前节点的右节点，用右节点的值和给定值比较；

function find(root,key) {
    var current = this.root;
    while(current) {
        if(current.value == key) {
            return current;
        } else if(key < current.value) {
            current = current.left;
        } else{
            current = current.right;
        }
    }
    return null;
};

删除操作

删除操作稍微复杂一些。思路在于首先找到删除值的结点，若该结点是叶子结点，则直接将其置为null，若其具有左子树或右子树，则将左孩子结点或右孩子结点赋值给当前结点。若当前结点既有左子树，又有右子树，则在其左子树中，寻找一个和当前结点值最接近的孩子结点（即中序遍历结果中当前结点的前驱），将当前结点的值替换为该孩子结点的值，替换后，树中此时就有两个重复的值，因此，再利用递归删除重复的孩子结点，依次类推。。。

• 从待删除节点的左子树找节点值最大的节点A，替换待删除节点，并删除节点A；
• 从待删除节点的右子树找节点值最小的节点A，替换待删除节点，并删除节点A。

为什么要找右子树最小值（或者左子树的最大值）呢？因为右子树最小值比左子树的所有值都大，却比右子树的所有值小，这正是根节点的特性，用它来替代根节点再适合不过了。

function deleteNode(root, key){
    if (!root){
        console.log("删除失败");
        return root;
    }

    if (root.value > key){  //若当前结点值大于删除值，则继续在左子树中寻找删除值
        root.left = deleteNode(root.left, key);
    }else if (root.value < key){  //若当前结点值小于删除值，则继续在右子树中寻找删除值
        root.right = deleteNode(root.right, key);
    }else{  //找到与删除中相等的结点
        if (root.left === null & root.right === null){  //叶子结点
            root = null;
        }else if (root.left === null){  //只有右子树
            root = root.right;
        }else if (root.right === null){  //只有左子树
            root = root.left;
        }else{  //同时具有左右子树
            let prevNode = root.left;
            while(prevNode.right){  //寻找不大于当前结点值的最大结点值
                prevNode = prevNode.right;
            }
            root.value = prevNode.value;  //替换值
            root.left = deleteNode(root.left, prevNode.value);  //递归左子树，删除重复值的结点
        }
    } 
    return root;
}

参考：js实现二叉查找树的建立、插入、删除、遍历操作