在JavaScript中的二分搜索树中查找模式
模式：
一组数据的模式就是在该组数据中出现次数最多的次数。例如，3是数据集2、3、1、3、4、2、3、1的模式，因为它出现的次数最多。
二进制搜索树
如果树DS满足以下条件，则它是有效的二叉搜索树-
节点的左子树仅包含键小于或等于该节点的键的节点。
节点的右子树仅包含键大于或等于节点的键的节点。
左子树和右子树都必须也是二进制搜索树。
问题
我们需要编写一个以BST根作为唯一参数的JavaScript函数。BST可能或很可能包含重复项。我们需要找到并返回树存储的数据的模式。
示例
为此的代码将是-
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));输出结果控制台中的输出将是-
3