数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究在 JavaScript 中从二叉搜索树中删除指定节点
问题
假设，我们有以下代码创建了一个二叉搜索树数据结构，并提供了插入节点的功能：
class Node{
constructor(data) {
this.data = data;
this.left = null;
this.right = null;
};
};
class BinarySearchTree{
constructor(){
// root of a binary seach tree
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(){
// root of a binary seach tree
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;
else root.right = deleteNode(root.right, key);
} else {
if(!root.left || !root.right){
return root.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
更新于: 2021年3月18日
202 次查看
广告