ปัญหา
มีโค้ด BST พร้อม Insert ต้องเพิ่มฟังก์ชัน deleteNode(root, key) ลบโหนดที่มีค่า key คืน root ใหม่
โค้ดตัวอย่าง
class Node{ constructor(data) { this.data = data; this.left = null; this.right = null; } };
class BinarySearchTree{ constructor(){ this.root = null; } insert(data){ ... } insertNode(node, 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 Node();
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));
คำอธิบาย
3 กรณีลบ: 1) Leaf 2) มีลูกข้างเดียว 3) มีลูกสองข้าง → หา successor (น้อยสุดของขวา) แทนที่
ผลลัพธ์
Before Deleting any node 2 3 4 5 6 7 After deleting node with data 4 2 3 5 6 7
