java - 计算二叉树中通用对象的频率

Question

我正在创建一个方法来计算方法参数值的频率。我创建了一个二叉树并将值放入其中，我现在尝试计算等于参数的所有值。问题是我陷入了无限循环，任何人都可以明白为什么:

public int counter(T value)
  {
     if (value == null) return 0;
      Node<T> p = root, q = null; // q is the parent of p
      int values = 0;


    while (p != null)                           // checks p
    {
      int cmp = comp.compare(p.value,value);// compares

      if(p.value.equals(value))
      {
          values++;
      }

      if (cmp < 0) { q = p; p = p.left; }      // goes left in the tree
      else if (cmp > 0) { q = p; p = p.rigth; }  goes right in the tree


     if ( p == null) return values;
        }


      return 0; // if no values found in the tree 
  }

构造函数:

   private Node(T value, Node<T> l, Node<T> r) 
    {
      this.value = value;
      left = l; right = r;
    }

Answer 1

当您找到匹配的值时，您会增加计数器，但不会更改 p，因此此后您将永远停留在同一个节点上。

树可以包含多个值实例的任何解决方案都必须是递归的。只需绘制一棵树，其中包含某个特定值的 6 个实例，然后遍历您的代码。此时您必须查看两个子树，因此递归是轻松完成此操作的唯一方法(或者，我想您也可以使用父指针堆栈，但递归太多了清洁剂)。