数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济
心理学
社会学
时装学
法律学在 JavaScript 中找出二叉查找树中的众数
众数
一组数据的众数，就是该组数据中出现次数最多的数字。例如，在数据集 2, 3, 1, 3, 4, 2, 3, 1 中，众数是 3，因为它出现次数最多。
二叉查找树
如果一个树 DS 满足以下条件，则它是一个有效的二叉查找树 -
一个节点的左子树只包含键小于或等于该节点键的节点。
一个节点的右子树只包含键大于或等于该节点键的节点。
左子树和右子树也必须是二叉查找树。
问题
需要编写一个 JavaScript 函数，该函数只接受一个 BST 根作为参数。BST 很可能包含重复项。需要找到并返回树存储的数据的众数。
示例
代码如下 -
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));输出
控制台中的输出如下 -
3
更新日期： 04-Mar-2021
248 次浏览
广告