从 JavaScrip 中的二叉搜索树中删除所需的节点
问题
假设，我们有以下代码创建一个二叉搜索树DS并为我们提供插入节点的功能-
class Node{
constructor(data) {
this.data= data;
this.left= null;
this.right= null;
};
};
class BinarySearchTree{
constructor(){
//二叉搜索树的根
this.root= null;
}
insert(data){
var newNode = new Node(data);
if(this.root === null){
this.root = newNode;
}else{
this.insertNode(this.root, newNode);
};
};
insertNode(node, newNode){
if(newNode.data < node.data){
if(node.left === null){
node.left= newNode;
}else{
this.insertNode(node.left, newNode);
};
} else {
if(node.right === null){
node.right= newNode;
}else{
this.insertNode(node.right,newNode);
};
};
};
};
const BST = new BinarySearchTree();
BST.insert(5);
BST.insert(3);
BST.insert(6);
BST.insert(2);
BST.insert(4);
BST.insert(7);执行完这段代码后，我们的BST将如下所示-
5 / \ 3 6 / \ \ 2 4 7
我们需要编写另一个函数deleteNode()，它接受任何BST的根作为第一个参数，一个数值作为第二个参数。
如果第二个参数指定的值存在于树中，我们的函数应该删除保存该值的节点，否则我们的函数什么都不做。在这两种情况下，我们的函数都应该返回BST的更新根。
示例
此代码将是-
class Node{
constructor(data) {
this.data= data;
this.left= null;
this.right= null;
};
};
class BinarySearchTree{
constructor(){
//二叉搜索树的根
this.root= null;
}
insert(data){
var newNode = new Node(data);
if(this.root === null){
this.root = newNode;
}else{
this.insertNode(this.root, newNode);
};
};
insertNode(node, newNode){
if(newNode.data < node.data){
if(node.left === null){
node.left= newNode;
}else{
this.insertNode(node.left, newNode);
};
} else {
if(node.right === null){
node.right= newNode;
}else{
this.insertNode(node.right,newNode);
};
};
};
};
const BST = new BinarySearchTree();
BST.insert(5);
BST.insert(3);
BST.insert(6);
BST.insert(2);
BST.insert(4);
BST.insert(7);
const printTree = (node) => {
if(node !== null) {
printTree(node.left);
console.log(node.data);
printTree(node.right);
};
};
const deleteNode = function(root, key) {
if(!root){
return null;
};
if(root.data > key){
if(!root.left){
return root;
}else{
root.left = deleteNode(root.left, key);
};
} else if(root.data < key){
if(!root.right) return root;
elseroot.right= deleteNode(root.right, key);
} else {
if(!root.left || !root.right){
returnroot.left|| root.right;
} else {
let nd = new TreeNode();
let right = root.right;
nd.left = root.left;
while(right.left){
right = right.left;
}
nd.data = right.data;
nd.right = deleteNode(root.right, right.data);
return nd;
}
}
return root;
};
console.log('Before Deleting any node');
printTree(BST.root);
console.log('After deleting node with data 4');
printTree(deleteNode(BST.root, 4));代码说明：
一旦找到目标节点，我们总共需要考虑三个条件。
一片叶子（没有左，没有右）；
有左，无右；没有左有右；
左右都有。
1和2很简单，我们只需要返回null或我们拥有的任何东西（左或右）；
而对于最后一个条件，我们需要知道在我们删除目标节点后，将用什么来替换它。如果我们简单地向左或向右拖动它，BST将无效。所以我们必须从右子树中找到最小的，或者从左子树中找到最大的。
输出结果
控制台中的输出将是-
Before Deleting any node 2 3 4 5 6 7 After deleting node with data 4 2 3 5 6 7