Expliquer Morris aussitôt l'arbre transversal sans l'aide de piles ou de la récursivité

Le récursive dans l'ordre de la traversée à l'est : (in-order(left)->key->in-order(right)). (ceci est similaire à DFS)

Quand nous faisons de la DFS, nous avons besoin de savoir où le retour en arrière (c'est pourquoi nous avons l'habitude de garder une pile).

Que nous allons par le biais d'un nœud parent pour lequel nous aurons besoin de revenir en arrière à l' -> nous de trouver le nœud que nous aurons besoin de revenir en arrière et de mettre à jour son lien avec le nœud parent.

Lorsque nous revenir en arrière? Quand nous ne pouvons pas aller plus loin. Quand nous ne pouvons pas aller plus loin? Quand, ni gauche actuelle de l'enfant.

Où nous revenir? Avis: pour SUCCESSEUR!

Donc, comme nous suivre nœuds le long de la gauche-enfant chemin, mis le prédécesseur à chaque étape pour pointer vers le nœud courant. De cette façon, les prédécesseurs aura des liens vers des successeurs (un lien pour le backtracking).

Nous suivons à gauche alors que nous pouvons jusqu'à ce que nous avons besoin de revenir en arrière. Lorsque nous avons besoin de revenir en arrière, nous imprimons le nœud courant et suivez le lien pour le successeur.

Si nous avons juste fait marche arrière -> il faut suivre le droit des enfants (nous en aurons fini avec la gauche de l'enfant).

Comment savoir si nous avons juste fait marche arrière? Obtenir le prédécesseur de l'actuel nœud et de vérifier si elle a un bon lien (à ce nœud). Si c'est le cas - que nous l'avons suivie. supprimer le lien pour restaurer l'arbre.

Si il n'y avait pas de lien de gauche => nous n'avons pas revenir en arrière et devrait continuer en suivant des enfants à gauche.

Voici mon code Java (Désolé, c'est pas du C++)

public static <T> List<T> traverse(Node<T> bstRoot) {
Node<T> current = bstRoot;
List<T> result = new ArrayList<>();
Node<T> prev = null;
while (current != null) {
//1. we backtracked here. follow the right link as we are done with left sub-tree (we do left, then right)
if (weBacktrackedTo(current)) {
assert prev != null;
//1.1 clean the backtracking link we created before
prev.right = null;
//1.2 output this node's key (we backtrack from left -> we are finished with left sub-tree. we need to print this node and go to right sub-tree: inOrder(left)->key->inOrder(right)
result.add(current.key);
//1.15 move to the right sub-tree (as we are done with left sub-tree).
prev = current;
current = current.right;
}
//2. we are still tracking -> going deep in the left
else {
//15. reached sink (the leftmost element in current subtree) and need to backtrack
if (needToBacktrack(current)) {
//15.1 return the leftmost element as it's the current min
result.add(current.key);
//15.2 backtrack:
prev = current;
current = current.right;
}
//4. can go deeper -> go as deep as we can (this is like dfs!)
else {
//4.1 set backtracking link for future use (this is one of parents)
setBacktrackLinkTo(current);
//4.2 go deeper
prev = current;
current = current.left;
}
}
}
return result;
}
private static <T> void setBacktrackLinkTo(Node<T> current) {
Node<T> predecessor = getPredecessor(current);
if (predecessor == null) return;
predecessor.right = current;
}
private static boolean needToBacktrack(Node current) {
return current.left == null;
}
private static <T> boolean weBacktrackedTo(Node<T> current) {
Node<T> predecessor = getPredecessor(current);
if (predecessor == null) return false;
return predecessor.right == current;
}
private static <T> Node<T> getPredecessor(Node<T> current) {
//predecessor of current is the rightmost element in left sub-tree
Node<T> result = current.left;
if (result == null) return null;
while(result.right != null
//this check is for the case when we have already found the predecessor and set the successor of it to point to current (through right link)
&& result.right != current) {
result = result.right;
}
return result;
}

J'espère que le pseudo-code ci-dessous est plus révélateur:

node = root
while node != null
if node.left == null
visit the node
node = node.right
else
let pred_node be the inorder predecessor of node
if pred_node.right == null /* create threading in the binary tree */
pred_node.right = node
node = node.left
else         /* remove threading from the binary tree */
pred_node.right = null 
visit the node
node = node.right

Se référant au code C++ de la question, l'intérieure de la boucle while trouve les dans l'ordre prédécesseur de l'actuel nœud. Au standard d'un arbre binaire, le droit de l'enfant de son prédécesseur, doit être nulle, alors que dans la version letée le droit de l'enfant doit pointer vers le nœud courant. Si le droit de l'enfant est null, il est défini pour le noeud courant, créant effectivement le filetage, qui est utilisé comme point de retour qui, autrement, auraient à être stocké, généralement sur une pile. Si le droit de l'enfant est pas null, alors l'algorithme permet de s'assurer que l'arbre d'origine est restauré, et puis continue la traversée dans le sous-arbre droit (dans ce cas, il est connu que le sous-arbre gauche a été visité).