二叉搜索树 JavaScript 实现 - 删除函数

您的代码针对以下情况进行了设置：找到的节点是根节点，并且它是树中的唯一节点，如果节点同时具有左子节点和右子节点，则会覆盖其值。但是，当要删除的节点是根并且它只有一个子节点时，代码中没有任何内容可以覆盖this.root，并且您不会覆盖根的值，因此不会删除它并且树保持不变。

您可以通过更改以下内容来解决此问题：

if ( node === void 0 ) node = this.root;
// compare the node's value with the value
if ( value < node.value ) {

对此：

if ( node === void 0 ) {
    this.root = this.remove(value, this.root);
// compare the node's value with the value
} else if ( value < node.value ) {

修复后，您可以稍微简化逻辑：

remove: function (value, node) {
    if (!this.isEmpty()) {
        // initialize node
        if (!node) {
            this.root = this.remove(value, this.root);
        } else if (value < node.value && node.left) {
            node.left = this.remove(value, node.left);
        } else if (value > node.value && node.right) {
            node.right = this.remove(value, node.right);
        } else if (value === node.value) {
            // check if node is a leaf node
            if (node.left && node.right) {
                // node has two children. change its value to the min
                // right value and remove the min right node
                node.value = this.findMinValue(node.right);
                node.right = this.remove(node.value, node.right);
            } else {
                // replace the node with whichever child it has
                node = node.left || node.right;
            }
        }
        return node;
    }
},

然后，您可以通过将其分为两种方法来进一步简化它：

remove: function (value) {
    this.root = this._removeInner(value, this.root);
},
_removeInner: function (value, node) {
    if (node) {
        if (value < node.value) {
            node.left = this._removeInner(value, node.left);
        } else if (value > node.value) {
            node.right = this._removeInner(value, node.right);
        } else if (node.left && node.right) {
            node.value = this.findMinValue(node.right);
            node.right = this._removeInner(node.value, node.right);
        } else {
            node = node.left || node.right;
        }
    }
    return node;
},

演示<小时 />@wmock问我是如何解决这个问题的，所以我会详细说明一下。

我做的第一件事是在调试器中遍历代码，专注于bst.remove(30)部分。我注意到当时 30 是根，并且在remove()完成后它仍然存在。这让我注意到，在这种特定情况下，代码永远不会修改根。

然后，我查看了如何将this.remove()的返回值分配给node.left和node.right，并回顾了BST算法，认为对根进行模拟也是有意义的。这确实是答案。

有几件事促使将该方法分为两种方法：

• 我注意到该方法具有相当多的特殊情况功能，这些功能仅与初始调用相关bst.remove()
  • 检查this.isEmpty()
  • 如果 node 为 null，则使用 this.root 作为 node 的值
  • 在某些情况下，当树高度为 0 时，将this.root重置为 null

每次通过remove()中都做所有这些似乎很草率

• 我也反复发现自己想用if (!node)来检查我是否已经到达树的边缘，但我不能，因为当node为空时，有特殊的情况逻辑可以使用this.root。

将方法分为两部分解决了上述所有问题。

请注意，在许多 BST 实现中，_removeInner() 中的功能将是 binaryTreeNode 类型的方法，树将只与根节点交互。这样就无需将节点从一个方法调用传递到下一个方法调用：

在binarySearchTree：

remove: function (value) {
    this.root && this.root.remove(value);
},

在binaryTreeNode：

remove: function (value) {
    if (value < this.value) {
        this.left = this.left && this.left.remove(value);
    } else if (value > this.value) {
        this.right = this.right && this.right.remove(value);
    } else if (this.left && this.right) {
        this.value = this.right.findMinValue();
        this.right = this.right.remove(this.value);
    } else {
        return this.left || this.right;
    }
    return this;
},
findMinValue: function () {
    return this.left ? this.left.findMinValue() : this.value;
}

演示

这是具有插入和删除功能的二叉树的完整示例

function Node(val) {
    this.data = val;
    this.right = null;
    this.left = null;
}
function BST() {
    this.root = null;
    this.insert = insert;
    this.inOrder = inOrder;
    this.remove = remove;
    this.removeNode = removeNode;
    this.kthSmallestNode = kthSmallestNode;
}
function insert(val) {
    if (val == null || val == undefined)
        return;
    if (this.root == null) {
        this.root = new Node(val);
        return;
    }
    var current = this.root
    var newNode = new Node(val);
    while (true) {
        if (val < current.data) {
            if (current.left == null) {
                current.left = newNode;
                return;
            }
            current = current.left;
        } else {
            if (current.right == null) {
                current.right = newNode;
                return;
            }
            current = current.right;
        }
    }
}
function remove(val) {
    this.root = removeNode(this.root, val);
}
function removeNode(current, value) {
    if (value == null || value == undefined)
        return;
    if (value == current.data) {
        if (current.left == null && current.right == null) {
            return null;
        } else if (current.left == null)
            return current.right;
        else if (current.right == null)
            return current.left;
        else {
            var tempNode = kthSmallestNode(current.right);
            current.data = tempNode.data;
            current.right = removeNode(current.right, tempNode.data);
            return current;
        }

    } else if (value < current.data) {
        current.left = removeNode(current.left, value);
        return current;
    } else {
        current.right = removeNode(current.right, value);
        return current;
    }
}
function kthSmallestNode(node) {
    while (!(node.left == null))
        node = node.left;
    return node;
}
function inOrder(node) {
    if (!(node == null)) {
        inOrder(node.left);
        console.log(node.data + " ");
        inOrder(node.right);
    }
}

var tree = new BST();
tree.insert(25);
tree.insert(20);
tree.insert(30);
tree.insert(27);
tree.insert(21);
tree.insert(16);
tree.insert(26);
tree.insert(35);
tree.remove(30)
console.log("Inorder : ")
console.log(tree.inOrder(tree.root))

祝你好运！！！

我有一个非常简单的答案，我想大多数人都会理解，它考虑了子节点。关键是，如果您要删除具有左右子项的值，则首先向左，然后一直向右，因为这可以向您保证它没有子项并且更容易更新。

  removeNode(val) {
    let currentNode, parentNode, nextBiggestParentNode=null, found=false, base=[this.root];
    while(base.length > 0 && !found) {
      currentNode = base.pop();
      if(currentNode.value === val) {
        found=true;
        if(!currentNode.left && !currentNode.right) {
          parentNode.right === currentNode ? parentNode.right = null : parentNode.left = null;
        }
        else if(!currentNode.right && currentNode.left) {
          parentNode.right === currentNode ? parentNode.right = currentNode.left : parentNode.left = currentNode.left;
        }
        else if(!currentNode.left && currentNode.right) {
          parentNode.right === currentNode ? parentNode.right = currentNode.right : parentNode.left = currentNode.right;
        }
        else {
          let _traverse = node => {
            if (node.right) {
              nextBiggestParentNode = node;
              _traverse(node.right);
            }
            else {
              currentNode.value = node.value;
              nextBiggestParentNode ? nextBiggestParentNode.right = null : currentNode.left = null;
            }
          }
          _traverse(currentNode.left);
        }
      }
      else {
        parentNode = currentNode;
        val > currentNode.value && currentNode.right ? base.unshift(currentNode.right) : base.unshift(currentNode.left);
      }
    }
    return this;
  }

该代码是类的一部分，如果有人感兴趣，这是我的构造函数代码的其余部分

let TreeNode = class  {
  constructor(value, left=null, right=null) {
    this.value = value;
    this.left = left;
    this.right = right;
  }
}
let BST = class {
  constructor(root=null) {
    this.root = root;
  }
  insert(nodeToInsert) {
    if (this.root === null) {
      this.root = nodeToInsert;
    } else {
      this._insert(this.root, nodeToInsert);
    }
  }
  _insert(root, nodeToInsert) {
    if (nodeToInsert.value < root.value) {
      if (!root.left) {
        root.left = nodeToInsert;
      } else {
        this._insert(root.left, nodeToInsert);
      }
    } else {
      if (!root.right) {
        root.right = nodeToInsert;
      } else {
        this._insert(root.right, nodeToInsert);
      }
    }
  }

下面是一些用于创建 BST 并删除值的演示代码

let bst = new BST();
const nums = [20,10,5,15,3,7,13,17,30,35,25,23,27,37,36,38];
function createBst() {
  for (let i of nums) {
    bst.insert(new TreeNode(i));
  }
  console.log(JSON.stringify(bst, null, 2));
  bst.removeNode(35);
}
createBst();
console.log(JSON.stringify(bst, null, 2));