Comment puis-je effectuer une itération sur Arbre Binaire?

Ce que vous êtes à la recherche d'un successeur de l'algorithme.

Voici comment il peut être défini:

• Première règle: Le premier nœud de l'arbre est le plus à gauche du nœud dans l'arbre.
• Règle suivante: Le successeur d'un nœud est:
  • De la prochaine R de la règle: Si il a un droit de sous-arbre, le plus à gauche du nœud du sous-arbre droit.
  • Prochaine-U règle: Sinon, parcourez l'arborescence
    • Si vous faites un virage à droite (c'est à dire ce nœud était à gauche de l'enfant), alors que le nœud parent est le successeur
    • Si vous faites un virage à gauche (c'est à dire ce nœud est un droit de l'enfant), continuer de monter.
    • Si vous ne pouvez pas aller jusqu'à plus, alors il n'y a pas de successeur

Comme vous pouvez le voir, pour ce travail, vous avez besoin d'un nœud parent pointeur.

---

Exemple:

• Première règle: Le premier nœud de l'arbre est le plus à gauche du nœud dans l'arbre: (1)
• Prochaine-U règle: Depuis (1) n'a pas le droit de sous-arborescence, nous montons à (3). C'est un virage à droite, de sorte (3) est à côté.
• De la prochaine R de la règle: Depuis (3) a un sous-arbre droit, le nœud le plus à gauche dans ce sous-arbre est le suivant: la (4).
• Prochaine-U règle: Depuis (4) n'a pas le droit de sous-arborescence, nous montons à (6). C'est un virage à droite, donc la prochaine est (6).
• De la prochaine R de la règle: Depuis (6) a un sous-arbre droit, le nœud le plus à gauche dans ce sous-arbre est le suivant: la (7).
• Prochaine-U règle: Depuis (7) n'a pas le droit de sous-arborescence, nous montons à (6). C'est un virage à gauche, donc nous continuons à aller jusqu'à (3). C'est un virage à gauche, donc nous continuons à aller jusqu'à (8). C'est un virage à droite, donc la prochaine est (8).
• De la prochaine R de la règle: Depuis (8) a un sous-arbre droit, le nœud le plus à gauche dans ce sous-arbre est le suivant: la (10).
• De la prochaine R de la règle: Depuis (10) a un sous-arbre droit, le nœud le plus à gauche dans ce sous-arbre est le suivant: la (13).
• Prochaine-U règle: Depuis (13) n'a pas le droit de sous-arborescence, nous montons à (14). C'est un virage à droite, donc la prochaine est (14).
• Prochaine-U règle: Depuis (14) n'a pas le droit de sous-arborescence, nous montons à (10). C'est un virage à gauche, donc nous continuons à aller jusqu'à (8). C'est un virage à gauche, nous voulons continuer de monter, mais depuis (8) n'a pas de parent, nous avons atteint la fin. (14) n'a pas de successeur.

---

Pseudo-code

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)

---

Code Java

Voici une simple mise en œuvre de l'algorithme ci-dessus:

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

Alors vous pouvez avoir un harnais de test comme ceci:

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

Cette affiche:

1 3 4 6 7 8 10 13 14 

Voir aussi

• Java complet d'inscription et de sortie sur ideone.com

OriginalL'auteur polygenelubricants

Comme à chaque récursion, vous pouvez utiliser la structure de données supplémentaires - c'est à dire de la pile.
Un esquisse de la solution:

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

}

OriginalL'auteur Grzegorz Oledzki

J'ai eu un arbre (non binaire) et finalement résolu avec cet algorithme très simple. Les solutions utilisées gauche et droit qui n'étaient pas pertinents ou même mis en œuvre dans les exemples.

Ma structure a été: des noeuds avec chaque parent contenant la liste des enfants, et chaque enfant contenant un pointeur à la maison mère. Assez commun...

Après un tas de refactoring, je suis venu avec l'exemple suivant à l'aide de Kotlin. Il doit être facile à convertir à la langue de votre choix.

Des Fonctions D'Assistance

Tout d'abord, le nœud doit fournir 2 fonctions simples. Cela peut varier en fonction de votre classe de Nœud de mise en œuvre:

gauche - C'est le premier nœud enfant. Si le nœud a des enfants, c'est d'abord un enfant, etc. Si pas d'enfants, de retour ce.

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

nextSibling - Le prochain fils de ce nœud, ou 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
    }
}

L'Itération

L'itération commence avec le bouton de gauche de la racine.

Puis inspectez le frère suivant.

• Si PAS NULL, la sœur de leftMostChild
• Si la valeur est NULL, le parent, et si le parent est NULLE, on a fini.

.

Ici est un Kotlin fonction d'itérateur.

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

Ici est la même fonction next (), mais sans le Kotlin d'abréviation pour traiter avec des valeurs NULLES, pour ceux qui ne sont pas de la hanche à la syntaxe.

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
}

OriginalL'auteur Steven Spungin