Mode:
Mode của tập dữ liệu là số xuất hiện nhiều nhất. Ví dụ: 3 là mode của 2,3,1,3,4,2,3,1.
Binary Search Tree
Cây BST hợp lệ thỏa mãn: cây con trái chỉ chứa khóa ≤ khóa nút; cây con phải chỉ chứa khóa ≥ khóa nút; cả hai cây con cũng là BST.
Vấn đề
Cần viết hàm JS nhận gốc BST (có thể chứa trùng lặp), tìm và trả về mode của dữ liệu trong cây.
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(1); BST.insert(3); BST.insert(3); BST.insert(2); BST.insert(3); BST.insert(2); const findMode = function(root) { let max = 1; const hash = {}; const result = []; const traverse = node => { if (hash[node.data]) { hash[node.data] += 1; max = Math.max(max, hash[node.data]); } else { hash[node.data] = 1; }; node.left && traverse(node.left); node.right && traverse(node.right); }; if(root){ traverse(root); }; for(const key in hash) { hash[key] === max && result.push(key); }; return +result[0]; }; console.log(findMode(BST.root));
Kết quả
Kết quả in ra console:
3