資料結構
網路
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 次瀏覽
廣告