Как я выполняю итерации по Двоичному дереву?

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

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

LinkedList queue = new LinkedList();

queue.add(root);

while (!queue.isEmpty()){
    Object element = queue.remove();

    queue.add(element.left);
    queue.add(element.right);

    // Do your processing with element;
}

Вы ищете алгоритм-преемник.

Вот как это можно определить:

• Первое правило : первый узел в дереве - это крайний левый узел в дереве.
• Следующее правило : Преемник узла:
  • Правило Next-R : если у него есть правое поддерево, это крайний левый узел в правом поддереве.
  • Правило Next-U : в противном случае пройти вверх по дереву.
    • Если вы сделаете поворот направо (т.е. этот узел был левым дочерним), тогда этот родительский узел станет его преемником
    • Если вы сделаете поворот налево (т.е. этот узел был правым дочерним узлом), продолжайте движение вверх.
    • Если вы больше не можете подняться вверх, значит, преемника нет.

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

Пример:

• Первое правило : Первый узел в дереве - это крайний левый узел в дереве: (1)
• Правило Next-U : С ( 1) не имеет правого поддерева, переходим к (3) . Это поворот направо, поэтому следующим будет (3) .
• Правило Next-R : Поскольку (3) имеет правое поддерево, крайний левый узел в этом поддереве следующий: (4) .
• Правило Next-U : Поскольку (4) не имеет правого поддерева, мы переходим к (6) . Это поворот направо, поэтому следующий (6) .
• Правило Next-R : Поскольку (6) имеет правое поддерево, крайним левым узлом в этом поддереве является следующий: (7) .
• Правило Next-U : Поскольку (7) не имеет правого поддерева, мы переходим к (6) .Это левый поворот, продолжаем подниматься к (3) . Это левый поворот, продолжаем подниматься до (8) . Это поворот направо, поэтому следующий (8) .
• Правило Next-R : Поскольку (8) имеет правое поддерево, крайний левый узел в этом поддереве является следующим: (10) .
• Правило Next-R : Поскольку (10) имеет правое поддерево, крайний левый узел в этом поддереве следующий: (13) .
• Правило Next-U : Поскольку (13) не имеет правого поддерева, мы переходим к (14) . Это поворот направо, поэтому следующий (14) .
• Правило Next-U : Поскольку (14) не имеет правого поддерева, мы переходим к (10) . Это левый поворот, продолжаем подниматься к (8) . Это левый поворот, поэтому мы хотим продолжить движение вверх, но поскольку (8) не имеет родителя, мы достигли конца. (14) не имеет преемника.

Псевдокод

Node getLeftMost(Node n)
  WHILE (n.leftChild != NULL)
    n = n.leftChild
  RETURN n

Node getFirst(Tree t)
  IF (t.root == NULL) RETURN NULL
  ELSE
     RETURN getLeftMost(t.root);

Node getNext(Node n)
  IF (n.rightChild != NULL)
     RETURN getLeftMost(n.rightChild)
  ELSE
     WHILE (n.parent != NULL AND n == n.parent.rightChild)
        n = n.parent;
     RETURN n.parent;

PROCEDURE iterateOver(Tree t)
  Node n = getFirst(t);
  WHILE n != NULL
     visit(n)
     n = getNext(n)

Код Java

Вот простая реализация вышеупомянутого алгоритма:

public class SuccessorIteration {
    static class Node {
        final Node left;
        final Node right;
        final int key;
        Node parent;
        Node(int key, Node left, Node right) {
            this.key = key;
            this.left = left;
            this.right = right;
            if (left != null) left.parent = this;
            if (right != null) right.parent = this;
        }
        Node getLeftMost() {
            Node n = this;
            while (n.left != null) {
                n = n.left;
            }
            return n;
        }
        Node getNext() {
            if (right != null) {
                return right.getLeftMost();
            } else {
                Node n = this;
                while (n.parent != null && n == n.parent.right) {
                    n = n.parent;
                }
                return n.parent;
            }
        }
    }
}

Затем вы можете получить такую ​​тестовую программу:

static Node C(int key, Node left, Node right) {
    return new Node(key, left, right);
}
static Node X(int key)             { return C(key, null, null);  }
static Node L(int key, Node left)  { return C(key, left, null);  }
static Node R(int key, Node right) { return C(key, null, right); }
public static void main(String[] args) {
    Node n =
        C(8,
            C(3,
                X(1),
                C(6,
                    X(4),
                    X(7)
                )
            ),
            R(10,
                L(14,
                    X(13)
                )
            )
        );
    Node current = n.getLeftMost();
    while (current != null) {
        System.out.print(current.key + " ");
        current = current.getNext();
    }
}

Это печатает:

1 3 4 6 7 8 10 13 14 

См. Также

• Полная Java листинг и вывод на ideone.com

Как и в любой рекурсии, вы можете использовать дополнительную структуру данных, то есть стек. набросок решения :

private static void visitall(BinaryTree foo) {
  Stack<BinaryTree> iterationStack = new Stack<BinaryTree>();
  iterationStack.push(foo);

  while (!iterationStack.isEmpty()) {
      BinaryTree current = iterationStack.pop();
      System.out.println(current.node);
      current.push(current.right);        // NOTE! The right one comes first
      current.push(current.left);
   }

}

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