Как найти следующего по порядку преемника в бинарном дереве?

Это помогает учитывать правила бинарного дерева поиска. Предположим, что ранее возвращенный узел n:

• Если n имеет правое поддерево, то узел со следующим значением будет самым левым узлом правого поддерева.
• Если n не имеет правого поддерева, то узел со следующим значением будет первым предком n, который содержит n в своем левом поддереве.

Ваш код правильно обрабатывает первый случай, но не второй. Рассмотрим случай, когда node — крайний левый лист дерева (начальный случай). node не имеет правильного потомка, поэтому мы идем прямо к else. node имеет родителя, поэтому предложение if пропускается. node.parent.left == node, поэтому предложение while пропускается без выполнения вообще. Конечным результатом является то, что возвращается node. Я ожидаю, что ваш итератор будет продолжать возвращать один и тот же узел навсегда.

Существует 3 основных способа итерации бинарного дерева.

private void inOrder(TreeNode node) {
    if(isEmpty())return;
    if(node.getLeftNode()!=null)inOrder(node.getLeftNode());
    System.out.print(node.getNodeData()+" ");
    if(node.getRightNode()!=null)inOrder(node.getRightNode());
}

private void preOrder(TreeNode node) {
    if(isEmpty())return;
    System.out.print(node.getNodeData()+" ");
    if(node.getLeftNode()!=null)preOrder(node.getLeftNode());
    if(node.getRightNode()!=null)preOrder(node.getRightNode());
}

private void postOrder(TreeNode node) {
    if(isEmpty())return;
    if(node.getLeftNode()!=null)postOrder(node.getLeftNode());
    if(node.getRightNode()!=null)postOrder(node.getRightNode());
    System.out.print(node.getNodeData()+" ");
}

//use
inOrder(root);
preOrder(root);
postOrder(root);

Это просто, ваш код на самом деле не имеет для меня смысла, есть ли что-то еще, что вы пытаетесь сделать, кроме повторения одним из этих способов?

Я думаю, вам нужно сохранить предыдущую точку в итераторе, чтобы вы знали, где вы были раньше.

Вот некоторый код, но имейте в виду, что он не завершен, вы должны сделать это самостоятельно, и это просто для того, чтобы показать вам идею. он также не обрабатывает корневой узел.

findNext(TreeNode node, TreeNode previousNode) {

  if(node.left != null && node.left != previousNode && node.right != previousNode){ //go left if not been there yet
    return node.left; 
  }
  if(node.right != null && node.right != previousNode){ //go right if not been there yet
    return node.right;
  }
  return findNext(node.parent, node); //go up and pass current node to avoid going down
}

Хорошим подходом является использование стека для управления последовательностью, что как бы делается для вас, если вы используете рекурсивный обход (вместо того, чтобы вообще пытаться построить итератор), как описано в ответе SteveL.

Поскольку вы хотите начать слева, вы сначала загружаете в стек корневой узел и его крайние левые дочерние элементы в правильном порядке (нажимайте, спускаясь влево от корня).

Всегда извлекайте следующий из вершины стека и помещайте его правый дочерний элемент (если есть) и все его крайние левые дочерние элементы, прежде чем возвращать тот, который вы только что извлекли, чтобы они были следующими в очереди.

При таком подходе вершина стека всегда будет возвращаться следующей, и когда стек пуст, больше нет...

В коде:

import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Stack;

public class TreeNodeInOrderIterator<T> implements Iterator<T> {

    private final Stack<TreeNode<T>> stack;

    public TreeNodeInOrderIterator(TreeNode<T> root) {
        this.stack = new Stack<TreeNode<T>>();
        pushLeftChildren(root);
    }

    @Override
    public boolean hasNext() {
        return !stack.isEmpty();
    }

    @Override
    public T next() {
        if (!hasNext())
            throw new NoSuchElementException();
        TreeNode<T> top = stack.pop();
        pushLeftChildren(top.right);
        return top.val;
    }

    @Override
    public void remove() {
        throw new UnsupportedOperationException();
    }

    private void pushLeftChildren(TreeNode<T> cur) {
        while (cur != null) {
            stack.push(cur);
            cur = cur.left;
        }
    }

}

В этом коде TreeNode определяется как

public class TreeNode<T> {
    T val;
    TreeNode<T> left;
    TreeNode<T> right;
    TreeNode(T x) { val = x; }
}

Если вы хотите, чтобы каждый узел также знал своего родителя, это нормально, но весь обход осуществляется с использованием того, что находится в стеке, и добавления в стек с использованием дочерних ссылок left и right.