java - 为什么我的二叉树迭代器停止了？

尝试以有序方式遍历二叉树时，它将打印根，最右边的子代，然后停止。显然是错误的，并且由于我是树结构的新手，因此我难以解决这个问题。我究竟做错了什么？

主要：

while (tree.iterator().hasNext())
    System.out.println(tree.iterator().next());

迭代器：

public Iterator<T> iterator() {
  Iterator<T> it = new Iterator<T>() {

    Node<T> next = root;

    @Override
    public boolean hasNext() {
      return next != null;
    }

    @Override
    public T next() {
      if (!hasNext())
        throw new NoSuchElementException();

      System.out.println("Returning data");
      T r = next.data;

      if (next.right != null) {
        next = next.right;
        while (next.left != null)
          next = next.left;

      } else while (true) {
        if (next.parent == null) {
          next = null;
          return r;
        }
        if (next.parent.left == next) {
          next = next.parent;
          return r;
        }
        next = next.parent;
      }
      return r;
    }

    @Override
    public void remove() {
      // TODO Auto-generated method stub
    }

  };
  return it;
}

输出：

242
275
279
283

242是树的根。
242.left = 33
242.right = 283

更新1：

树：

242
|33
||29
|||25
||||NULL
||||NULL
|||NULL
||74
|||70
||||66
|||||NULL
|||||NULL
||||NULL
|||115
||||111
|||||107
||||||NULL
||||||NULL
|||||NULL
||||156
|||||152
||||||148
|||||||NULL
|||||||NULL
||||||NULL
|||||197
||||||193
|||||||NULL
|||||||NULL
||||||238
|||||||234
||||||||NULL
||||||||NULL
|||||||NULL
|283
||279
|||275
||||NULL
||||NULL
|||NULL
||NULL

最佳答案

您似乎从根的右侧开始，然后转到最左侧的孩子。因此，您会错过整个左手部分。

您应该使用最左边的孩子而不是根孩子来初始化next。

更新：您可以在初始化块中执行此操作，如下所示：

Iterator<T> it = new Iterator<T>() {

    Node<T> next;

    {
        next = root;
        while (next.left != null)
            next = next.left;
    }

    @Override
    public boolean hasNext() {
        return next != null;
    }

    //...
}