在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