删除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