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

Question

当尝试以有序方式遍历二叉树时，它会打印根、最右边的子节点，然后停止。显然有些问题，我很难理解这一点，因为我是树结构的新手。我做错了什么？

主要:

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.左=33
242.右=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

Answer 1

您似乎从根的右侧开始，然后再转到最左边的子项。所以你一开始就错过了整个左侧部分。

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

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

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

    //...
}