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

Question

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

Main：

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.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

Answer 1

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

应该使用最左边的子级而不是根来初始化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;     
    }

    //...
}