数据结构之树（操作树的节点）

这是我参与更文挑战的第29天，活动详情查看：更文挑战

本篇文章中，我们来实现树的remove方法。

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

function BinarySearchTree () {
    // 初始化根节点为null
    let root = null
    // 声明节点Node类，用于创建多个独立的节点
    let Node = function (key) {
        this.key = key
        this.left = null
        this.right = null
    }
    
    this.remove = function (key) {
        // 注意：此处将 removeNode方法的结果赋值给了root，目的是用于移除键key对应的节点node之后，处理其父节点对其的引用，保证移除该节点之后其父节点的引用变为null
        root = removeNode(root, key)
    }
    // 辅助函数，用于移除树的节点
    let removeNode = function (node, key) {
        // 同样的，首先得判断node是否有效
        if (!node) {
            return null
        }
        // node存在则继续下面的操作
        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 { // 键key等于node.key
            /** 
                此时说明匹配到了节点，那么当点匹配到的节点node，又分为多种情况：
                1. 当前节点是一个没有子节点的节点。
                2. 当前节点是一个只有一个子节点的节点。
                3. 当前节点是一个拥有两个子节点的节点。
            **/
            // 第一种：一个节点
            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
            }
            // 第三种：一个有两个子节点的节点
            let aux = findMinNode(node.right)
            node.key = aux.key
            node.right = removeNode(node.right, aux.key)
            return node
        }
    }
    // 找到最小的节点
    let findMinNode = (node) {
        if (node) {
            while (node && node.left !==null) {
                node = node.left
            }
            return node
        }
        return null
    }
    
}
复制代码

下面是移除节点的逻辑实现步骤：

1. 首先得检测我们要移除的这个节点是否有效；
2. 判断节点有效之后，就是要在树中找到我们要移除的这个节点；
3. 找到要移除的节点之后，得清楚该节点是哪种类型的节点，其不同类型的节点，处理方式不同；
4. 第一种情况是，要移除的节点是一个没有左侧子节点和右侧子节点的叶子节点：在这种情况下，我们要移除这个节点需要将null赋值给它，表示移除。但是在树结构中，虽然该节点没有任何的子节点，但是它有父节点，所以我们需要返回null来将对应的父节点的指针赋值为null。
5. 第二种情况是，要移除的节点是一个只有左侧子节点或者只有右侧子节点的节点：这种情况下，需要跳过这个节点，直接将该节点的父节点指向该节点的子节点。对应到代码中也就是说，我们需要将该节点node的子节点node.right或者node.left赋值给node，并将改变后的node返回。
6. 第三种情况是，要移除的节点一个拥有两个子节点的节点：在这种情况下，(1)需要先找到当前节点node右边子树中最小的节点。(2)然后将找到的这个右侧最小的节点aux的key指向当前节点node的key，此时当前节点node的键key改变，也就意味着原来在树的这个位置的节点已经被移除。(3)到这一步，树中就会出现两个拥有相同键的节点了，分别是此时的node.key和aux.key,而这是万万不行的，所以我们需要继续把右侧子树中的最小节点移除。(4)最后，返回更新后的node

PS: 第三种情况不太好理解，需要仔细琢磨