如何在Java中返回二叉树中出现最频繁的元素

Question

如何在Java中返回二叉树中出现最频繁的元素

javaexceptionmaxbinary-treestack-overflow

4

我想返回在二叉树中最常出现的值的数量。我有一个BinaryClass，其中包含许多方法，如add、contain、isEmpty、counter、iterator等。我尝试实现此方法public int getMaxFrequency()，但是在标记行处遇到了StackOverFlowException问题。

运行代码时，我遇到了StackOverFlow Exception，请问是否有人可以帮助我？

我对二叉树很陌生，请帮助我。

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());}

- Hala

看起来你漏掉了一些步骤。你需要继承特定的“类（classes）”吗？ - Juliana Hill

我有一个名为Binarytree的类，其中包含许多方法（add、size、isEmpty、counter和getMaxFrequency()）。在getMaxFrequency()方法中，我必须返回测试二叉树中最常出现的值的数量。我还有一个名为Node的类。我的所有方法都能正常工作，但是对于getMaxFrequency()方法却不行。对于我的测试代码，getMaxFrequency()应该返回4，因为"java"是最常见的。 - Hala

我有 BinaryTree 和 Node 类，getMaxFrequency() 应该在包含许多类的 BinaryTree 类中。 - Hala

1

好的，我正在阅读你的代码。我很快就会回复！ - Juliana Hill

我对此非常感兴趣，顺便说一下！ :) - Juliana Hill

需要使用“inorder”吗？ - Juliana Hill

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Juliana Hill · Accepted Answer

尝试像这样编写计数器函数：

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;
}

这种技术被称为“记忆化”，其中以前的计数在一个“哈希表”中被缓存。