删除Javascript树中的节点

如果从远处看，从树中删除节点非常复杂。删除节点时需要考虑3种情况。这些在以下功能的注释中提到。正如我们之前所做的那样，我们将在类中创建一个方法和一个递归调用的助手。

类方法

deleteNode(key) {
   //如果成功删除节点，将收到参考。
   return !(deleteNodeHelper(this.root, key) === false);
}

辅助方法

/**
   * Takes root and key and recursively searches for the key.
   * If it finds the key, there could be 3 cases:
   *
   * 1. This node is a leaf node.
   *
   * Example: Removing F
   *     A
   *    / \
   *   B   C
   *  /   / \
   * D   E   F
   *
   * To remove it, we can simply remove its parent's connection to it.
   *
   *      A
   *     / \
   *    B   C
   *   /    /
   *  D    E
   *
   * 2. This node is in between the tree somewhere with one child.
   *
   * Example: Removing B
   *       A
   *      / \
   *     B   C
   *    /   / \
   *   D   E   F
   *
   * To remove it, we can simply make the child node replace the parent node in the above connection
   *       A
   *      / \
   *     D   C
   *        / \
   *       E   F
   *
   * 3. This node has both children. This is a tricky case.
   *
   * Example: Removing C
   *
   *        A
   *       / \
   *      B   C
   *     /   / \
   *    D   E   F
   *       /   / \
   *      G   H   I
   *
   * In this case, we need to find either a successor or a predecessor of the node and replace this node with
   * that. For example, If we go with the successor, its successor will be the element just greater than it,
   * ie, the min element in the right subtree. So after deletion, the tree would look like:
   *
   *        A
   *       / \
   *      B   H
   *     /   / \
   *    D   E   F
   *       /     \
   *      G       I
   *
   * To remove this element, we need to find the parent of the successor, break their link, make successor's left
   * and right point to current node's left and right. The easier way is to just replace the data from node to be
   * deleted with successor and delete the sucessor.
*/
function deleteNodeHelper(root, key) {
   if (root === null) {
      //空树返回false；
   }
   if (key < root.data) {
      root.left = deleteNodeHelper(root.left, key);
      return root;
   } else if (key > root.data) {
      root.right = deleteNodeHelper(root.right, key);
      return root;
   } else {
      //没有孩子
      //情况1-叶子节点
      if (root.left === null && root.right === null) {
         root = null;
         return root;
      }
      //独生子女案件
      if (root.left === null) return root.right;
      if (root.right === null) return root.left;

      //两个孩子，所以需要找到继任者
      let currNode = root.right;
      while (currNode.left !== null) {
         currNode = currNode.left;
      }
      root.data = currNode.data;
      //从右子树中删除该值。
      root.right = deleteNodeHelper(root.right, currNode.data);
      return root;
   }
}

您可以使用以下方式进行测试： 

示例

let BST = new BinarySearchTree();

BST.insertRec(10);
BST.insertRec(15);
BST.insertRec(5);
BST.insertRec(50);
BST.insertRec(3);
BST.insertRec(7);
BST.insertRec(12);
 
BST.inOrder();

BST.deleteNode(15);
BST.deleteNode(10);
BST.deleteNode(3);

BST.inOrder();

输出结果

这将给出输出-

5
7
12
50