如何 return 二叉树中最常见的元素 Java

Question

我想要 return 个 BinaryTree 中出现次数最多的值。我有 BinaryClass，其中包含许多方法，如添加、包含、isEmpty、计数器、迭代器和 other.I 试图实现此方法 public int getMaxFrequency() 但我在标记行遇到 WhosebugException 问题。

当我运行我的代码出现 Whosebug 异常 时，任何人都可以帮助我，

我是 BinaryTree 的新手。

请帮帮我。

enter code here
public class TreeSetCounter<T extends Comparable<T>> implements    Iterable<T>{
public Node<T> root; 
int size;
int count=0;

public TreeSetCounter() {
    root = null;
    size = 0;
   }
 public int counter(T t) {
 return counterRecursive(root, t);
  }

   public int counterRecursive(Node<T> root, T t) {
   int count = 0;
   if(root == null) {
        return 0;
          }
    if(root.value.equals(t)) {
      count++; 
      }
   count = count + counterRecursive(root.left, t)+           counterRecursive(root.right, t);
   return count; }


 public int getMaxFrequency(){
 
  return inorder(root);           
  }

  public int inorder( Node<T> prev) {
 
    int count = 1, max = 0;
    if (root == null) {
        return 0;}
    List<T> list = new ArrayList<>();
    inorder(root.left);   // I get the Exception att this row code.
    while (prev != null) {
    if (root.value == prev.value)
            count++;
        else
            count = 1;
    }
    
    if (count > max) {
        max = count;
        list.clear();
        list.add(root.value);
    } else if (count == max) {
        list.add(root.value);
    }
    prev = root;
    inorder(root.right);
    return max;
}

enter code here
Node.java
public class Node <T>{
T value;
int counter;
Node<T> left;
Node<T> right;

Node(T value, int count) {
    this.value = value;
    right = null;
    left = null;
    this.counter= count;
    }

enter code here
public static void main(String[] args) {
    TreeSetCounter <String> tsc= new TreeSetCounter<String>();
    tsc.add("java");
    tsc.add("java");
    tsc.add("not");
    tsc.add("cool");
    tsc.add("java");
    tsc.add("is");
    tsc.add("java");
    tsc.add("good");
    System.out.println(tsc.getMaxFrequency());}

Answer 1

为你的计数器函数尝试这样的事情：

public int counter (T t) {
  if (root == null) return 0;
  
  int count = 0;
  if (root.value.equals(t))
    count++;
  
  count += counterRecursive(root.left, t);
  count += counterRecursive(root.right, t);

  return count;
}

public int counterRecursive (Node<T> root, T t) {
   if (root == null) return 0;
   
   if (root.value.equals(t))
    return 1 + counterRecursive(root.left, t) + counterRecursive(root.right, t);
   else
    return counterRecursive(root.left, t) + counterRecursive(root.right, t);
}

counter 函数看起来像是要使用的主要方法，counterRecursive 是您的辅助函数。更复杂的递归解决方案通常具有这种设计模式。

用斐波那契数列思考：

public static int fibonacci (int n) {
  return (n <= 1) ? n : fibonacci(n - 1) + fibonacci(n - 2);
}

这应该可以帮助您调试 inOrder 和 getMaxFrequency。我会在 getMaxFrequency 中使用 counter，而我会浏览其余部分。一般来说，使用 HashMap 或 HashTable 更适合跟踪计数。

尝试这样的事情：

public int getMaxFrequency () {
    if (root == null) return 0;
        
    HashMap<T, Integer> counts = new HashMap<T, Integer>();
        
    int count = counter(root.value);
    counts.put(root.value, count);

    // traverse the tree and grab counts
    int left = getMaxFrequencyHelper(root.left, counts, count);
    int right = getMaxFrequencyHelper(root.right, counts, count);

    return left > right ? left : right;
}

private int getMaxFrequencyHelper (Node<T> node, HashMap<T, Integer> counts, max) {
    if (node == null) return max;

    if (!counts.containsKey(node.value))
        counts.put(node.value, counter(node.value));

    int _max = counts.get(node.value) > max ? counts.get(node.value) : max;

    int left = getMaxFrequencyHelper(node.left, counts, _max);
    int right = getMaxFrequencyHelper(node.right, counts, _max);

    return left > right ? left : right;
}

此技术称为 memoization，其中先前的计数在 HashMap 中为 cached。

如何 return 二叉树中最常见的元素 Java

How to return most frequent element in BinaryTree in Java

java

stack-overflow

binary-tree

exception

max