Vấn đề
Cho code tạo BST và chèn nút. Sau khi chèn 5,3,6,2,4,7, cây như sau:
5 / \ 3 6 / \ \ 2 4 7
Cần viết hàm deleteNode() nhận gốc BST và giá trị. Nếu giá trị tồn tại, xóa nút đó, trả về gốc cập nhật. Nếu không, không làm gì, trả về gốc.
Ví dụ
Mã thực hiện:
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; 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));
Giải thích code:
Ba trường hợp khi xóa nút:
Lá (không con trái, không con phải);
Có một con (chỉ trái hoặc chỉ phải);
Có cả hai con -> thay bằng nhỏ nhất cây con phải (hoặc lớn nhất cây con trái).
Kết quả
Kết quả in ra console:
Before Deleting any node 2 3 4 5 6 7 After deleting node with data 4 2 3 5 6 7