Как перебрать двоичное дерево?

Question

Прямо сейчас у меня есть

 private static void iterateall(BinaryTree foo) {
    if(foo!= null){
    System.out.println(foo.node);
    iterateall(foo.left);
    iterateall(foo.right);
   }
  }

Можете ли вы изменить его на Итерацию вместо рекурсии?

Answer 1

То, что вы ищете, это алгоритм-преемник.

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

• Первое правило : Первый узел в дереве является самым левым узлом в дереве.
• Следующее правило : Преемник узла:
  • Правило Next-R : Если у него есть правое поддерево, самый левый узел в правом поддереве.
  • Правило следующего 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

Answer 2

Можете ли вы изменить его на Итерацию вместо рекурсии?

Можно, используя явный стек. Псевдокод:

private static void iterateall(BinaryTree foo) {
    Stack<BinaryTree> nodes = new Stack<BinaryTree>();
    nodes.push(foo);
    while (!nodes.isEmpty()) {
        BinaryTree node = nodes.pop();
        if (node == null)
            continue;
        System.out.println(node.node);
        nodes.push(node.right);
        nodes.push(node.left);
    }
}

Но на самом деле это не лучше, чем рекурсивный код (за исключением отсутствия базового условия в вашем коде).

Answer 3

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

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

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

Answer 4

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

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

}

Answer 5

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

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

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

Вспомогательные функции

Во-первых, узел должен обеспечивать 2 простые функции. Это будет зависеть от реализации вашего класса Node:

leftMost - Это первый дочерний узел. Если у этого узла есть дочерние элементы, это первый дочерний элемент и т. Д. Если нет дочерних элементов, верните this .

fun leftMost(): Node {
        if (children.isEmpty()) {
            return this
        }
        var n = this
        while (n.children.isNotEmpty()) {
            n = n.children[0]
        }
        return n
}

nextSibling - следующий брат этого узла или NULL

fun nextSibling(): Node? {
    if (parent == null) return null
    val siblingIndex = parent.children.indexOf(this) + 1
    return if (siblingIndex < parent.children.size) {
        parent.children[siblingIndex]
    } else {
        null
    }
}

Итерация

Итерация начинается с левой части корня.

Затем осмотрите следующего брата.

• Если NOT NULL, левый или младший брат одного из братьев
• Если NULL, родитель, и если родитель NULL, мы закончили.

Вот и все.

Вот итератор Котлина.

fun iterator(): Iterator<Node> {
    var next: Node? = this.leftMost()

    return object : Iterator<Node> {

        override fun hasNext(): Boolean {
            return next != null
        }

        override fun next(): Node {
            val ret = next ?: throw NoSuchElementException()
            next = ret.nextSibling()?.leftMost() ?: ret.parent
            return ret
        }
    }
}

Здесь та же функция next (), но без сокращения Kotlin для работы со значениями NULL, для тех, которые не соответствуют синтаксису.

fun next(): Node {
    val ret = next
    if (ret == null) throw NoSuchElementException()
    val nextSibling = ret.nextSibling()
    if (nextSibling != null) {
        next = nextSibling.leftMost()
    }
    else {
        next = ret.parent
    }
    return ret
}

Answer 6

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