js 二叉检索树删除结点
时间: 2023-10-09 10:09:23 浏览: 45
二叉搜索树的删除结点操作可以分为三种情况:
1. 如果要删除的结点没有子节点,即为叶子结点,直接删除即可。
2. 如果要删除的结点只有一个子节点,将子节点替换到要删除的结点的位置。
3. 如果要删除的结点有两个子节点,需要找到其后继结点(即大于该结点的最小值),将后继结点的值覆盖到要删除的结点上,然后再删除后继结点。
以下是 JavaScript 中实现二叉搜索树删除结点的代码示例:
```javascript
class Node {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
class BinarySearchTree {
constructor() {
this.root = null;
}
deleteNode(value) {
this.root = this._deleteNode(this.root, value);
}
_deleteNode(root, value) {
if (root === null) {
return root;
}
if (value < root.value) {
root.left = this._deleteNode(root.left, value);
} else if (value > root.value) {
root.right = this._deleteNode(root.right, value);
} else {
// Case 1: No child or only one child
if (root.left === null) {
return root.right;
} else if (root.right === null) {
return root.left;
}
// Case 2: Two children
const successor = this._findMinNode(root.right);
root.value = successor.value;
root.right = this._deleteNode(root.right, successor.value);
}
return root;
}
_findMinNode(node) {
let current = node;
while (current.left !== null) {
current = current.left;
}
return current;
}
}
```
使用方法:
```javascript
const bst = new BinarySearchTree();
bst.insert(8);
bst.insert(3);
bst.insert(10);
bst.insert(1);
bst.insert(6);
bst.insert(14);
bst.insert(4);
bst.insert(7);
bst.insert(13);
console.log("Before deletion:", JSON.stringify(bst, null, 2));
bst.deleteNode(3);
console.log("After deletion:", JSON.stringify(bst, null, 2));
```
这样就可以在 JavaScript 中实现二叉搜索树的结点删除操作。