資料結構
網路
關係資料庫管理系統
作業系統
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 次檢視
廣告