Chế độ:
Chế độ của một tập dữ liệu chỉ đơn giản là số xuất hiện trong hầu hết số lần trong tập dữ liệu đó. Ví dụ:3 là chế độ của tập dữ liệu 2, 3, 1, 3, 4, 2, 3, 1 vì nó xảy ra trong hầu hết các lần.
Cây tìm kiếm nhị phân
DS cây là một Cây tìm kiếm nhị phân hợp lệ nếu nó đáp ứng các điều kiện sau -
-
Cây con bên trái của một nút chỉ chứa các nút có khóa nhỏ hơn hoặc bằng khóa của nút đó.
-
Cây con bên phải của một nút chỉ chứa các nút có khóa lớn hơn hoặc bằng khóa của nút đó.
-
Cả cây con bên trái và bên phải cũng phải là cây tìm kiếm nhị phân.
Vấn đề
Chúng tôi bắt buộc phải viết một hàm JavaScript lấy gốc BST làm đối số duy nhất. BST có thể có hoặc hầu hết có thể chứa các bản sao. Chúng tôi được yêu cầu tìm và trả về chế độ của dữ liệu được lưu trữ bởi cây.
Ví dụ
Mã cho điều này sẽ là -
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(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)); Đầu ra
Và đầu ra trong bảng điều khiển sẽ là -
3