Expliquer Morris dans l'ordre de la traversée des arbres sans utiliser de piles ni de récursivité

Quelqu'un peut-il s'il vous plaît m'aider à comprendre l'algorithme de traversée d'arbre inorder Morris suivant sans utiliser de piles ni de récursivité? J'essayais de comprendre comment ça marche, mais ça m'échappe.

 1. Initialize current as root
 2. While current is not NULL
  If current does not have left child     
   a. Print current’s data
   b. Go to the right, i.e., current = current->right
  Else
   a. In current's left subtree, make current the right child of the rightmost node
   b. Go to this left child, i.e., current = current->left

Je comprends l'arbre est modifiée de façon que le current node, est fait la right childde max nodedans right subtreeet d' utiliser cette propriété pour afinde traversal. Mais au-delà de ça, je suis perdu.

EDIT: trouvé ce code C ++ d'accompagnement. J'avais du mal à comprendre comment l'arbre est restauré après sa modification. La magie réside dans la elseclause, qui est frappée une fois que la feuille de droite est modifiée. Voir le code pour plus de détails:

/* Function to traverse binary tree without recursion and
   without stack */
void MorrisTraversal(struct tNode *root)
{
  struct tNode *current,*pre;

  if(root == NULL)
     return; 

  current = root;
  while(current != NULL)
  {
    if(current->left == NULL)
    {
      printf(" %d ", current->data);
      current = current->right;
    }
    else
    {
      /* Find the inorder predecessor of current */
      pre = current->left;
      while(pre->right != NULL && pre->right != current)
        pre = pre->right;

      /* Make current as right child of its inorder predecessor */
      if(pre->right == NULL)
      {
        pre->right = current;
        current = current->left;
      }

     // MAGIC OF RESTORING the Tree happens here: 
      /* Revert the changes made in if part to restore the original
        tree i.e., fix the right child of predecssor */
      else
      {
        pre->right = NULL;
        printf(" %d ",current->data);
        current = current->right;
      } /* End of if condition pre->right == NULL */
    } /* End of if condition current->left == NULL*/
  } /* End of while */
}

Si je lis bien l'algorithme, cela devrait être un exemple de son fonctionnement:

     X
   /   \
  Y     Z
 / \   / \
A   B C   D

Tout d'abord, Xest la racine, elle est donc initialisée en tant que current. Xa un enfant à gauche, il Xdevient donc l'enfant le plus à droite du Xsous-arbre gauche de 's - le prédécesseur immédiat de Xdans une traversée en ordre. Ainsi Xest fait le bon enfant de B, puis currentest mis à Y. L'arbre ressemble maintenant à ceci:

    Y
   / \
  A   B
       \
        X
       / \
     (Y)  Z
         / \
        C   D

(Y)ci-dessus fait référence à Yet à tous ses enfants, qui sont omis pour les problèmes de récursivité. La partie importante est de toute façon répertoriée. Maintenant que l'arbre a un lien vers X, le parcours continue ...

 A
  \
   Y
  / \
(A)  B
      \
       X
      / \
    (Y)  Z
        / \
       C   D

Puis Aest sorti, car il n'a pas d'enfant gauche, et currentest retourné à Y, qui a été créé Apour l'enfant droit dans l'itération précédente. À l'itération suivante, Y a les deux enfants. Cependant, la double condition de la boucle la fait s'arrêter lorsqu'elle atteint elle-même, ce qui indique que son sous-arbre gauche a déjà été traversé. Ainsi, il s'imprime et continue avec son sous-arbre droit, qui est B.

Bs'imprime, puis currentdevient X, qui passe par le même processus de vérification que l'a Yfait, réalisant également que son sous-arbre gauche a été traversé, en continuant avec le Z. Le reste de l'arbre suit le même schéma.

Aucune récursivité n'est nécessaire, car au lieu de s'appuyer sur un retour en arrière à travers une pile, un lien vers la racine du (sous) arbre est déplacé vers le point auquel il serait accessible dans un algorithme de traversée d'arbre inorder récursif de toute façon - après son le sous-arbre de gauche est terminé.

Le traversal dans l'ordre récursif est: (in-order(left)->key->in-order(right)). (c'est similaire à DFS)

Lorsque nous faisons le DFS, nous devons savoir vers où revenir en arrière (c'est pourquoi nous gardons normalement une pile).

En passant par un nœud parent vers lequel nous devrons revenir en arrière -> nous trouvons le nœud à partir duquel nous devrons revenir en arrière et mettre à jour son lien vers le nœud parent.

Quand on fait marche arrière? Quand on ne peut pas aller plus loin. Quand on ne peut pas aller plus loin? Quand aucun enfant n'est présent.

Où revenons-nous? Avis: au SUCCESSEUR!

Ainsi, lorsque nous suivons les nœuds le long du chemin de l'enfant gauche, définissez le prédécesseur à chaque étape pour qu'il pointe vers le nœud actuel. De cette façon, les prédécesseurs auront des liens vers les successeurs (un lien pour revenir en arrière).

Nous suivons à gauche tant que nous le pouvons jusqu'à ce que nous ayons besoin de revenir en arrière. Lorsque nous avons besoin de revenir en arrière, nous imprimons le nœud actuel et suivons le bon lien vers le successeur.

Si nous venons de revenir en arrière -> nous devons suivre le bon enfant (nous en avons terminé avec l'enfant gauche).

Comment savoir si nous venons de revenir en arrière? Récupérez le prédécesseur du nœud actuel et vérifiez s'il a un bon lien (vers ce nœud). Si c'est le cas, nous l'avons suivi. supprimez le lien pour restaurer l'arborescence.

S'il n'y avait pas de lien gauche => nous n'avons pas fait marche arrière et devrions continuer en suivant les enfants laissés.

Voici mon code Java (Désolé, ce n'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'ai fait une animation pour l'algorithme ici: https://docs.google.com/presentation/d/11GWAeUN0ckP7yjHrQkIB0WT9ZUhDBSa-WR0VsPU38fg/edit?usp=sharing

Cela devrait, espérons-le, aider à comprendre. Le cercle bleu est le curseur et chaque diapositive est une itération de la boucle while externe.

Voici le code pour morris traversal (je l'ai copié et modifié à partir de geeks pour geeks):

def MorrisTraversal(root):
    # Set cursor to root of binary tree
    cursor = root
    while cursor is not None:
        if cursor.left is None:
            print(cursor.value)
            cursor = cursor.right
        else:
            # Find the inorder predecessor of cursor
            pre = cursor.left
            while True:
                if pre.right is None:
                    pre.right = cursor
                    cursor = cursor.left
                    break
                if pre.right is cursor:
                    pre.right = None
                    cursor = cursor.right
                    break
                pre = pre.right
#And now for some tests. Try "pip3 install binarytree" to get the needed package which will visually display random binary trees
import binarytree as b
for _ in range(10):
    print()
    print("Example #",_)
    tree=b.tree()
    print(tree)
    MorrisTraversal(tree)

public static void morrisInOrder(Node root) {
        Node cur = root;
        Node pre;
        while (cur!=null){
            if (cur.left==null){
                System.out.println(cur.value);      
                cur = cur.right; // move to next right node
            }
            else {  // has a left subtree
                pre = cur.left;
                while (pre.right!=null){  // find rightmost
                    pre = pre.right;
                }
                pre.right = cur;  // put cur after the pre node
                Node temp = cur;  // store cur node
                cur = cur.left;  // move cur to the top of the new tree
                temp.left = null;   // original cur left be null, avoid infinite loops
            }        
        }
    }

Je pense que ce code serait mieux à comprendre, utilisez simplement un null pour éviter les boucles infinies, ne devez pas utiliser la magie autrement. Il peut être facilement modifié en précommande.

J'ai trouvé une très bonne explication picturale de Morris Traversal .

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

En se référant au code C ++ de la question, la boucle while interne trouve le prédécesseur dans l'ordre du nœud actuel. Dans une arborescence binaire standard, le bon enfant du prédécesseur doit être nul, tandis que dans la version threadée, le bon enfant doit pointer vers le nœud actuel. Si le bon enfant est nul, il est défini sur le nœud actuel, créant effectivement le thread , qui est utilisé comme un point de retour qui devrait autrement être stocké, généralement sur une pile. Si le bon enfant n'est pas nul, alors l'algorithme s'assure que l'arborescence d'origine est restaurée, puis continue la traversée dans le sous-arbre de droite (dans ce cas, on sait que le sous-arbre de gauche a été visité).

Complexité temporelle de la solution Python: O (n) Complexité spatiale: O (1)

Excellente explication de la traversée de Morris Inorder

class Solution(object):
def inorderTraversal(self, current):
    soln = []
    while(current is not None):    #This Means we have reached Right Most Node i.e end of LDR traversal

        if(current.left is not None):  #If Left Exists traverse Left First
            pre = current.left   #Goal is to find the node which will be just before the current node i.e predecessor of current node, let's say current is D in LDR goal is to find L here
            while(pre.right is not None and pre.right != current ): #Find predecesor here
                pre = pre.right
            if(pre.right is None):  #In this case predecessor is found , now link this predecessor to current so that there is a path and current is not lost
                pre.right = current
                current = current.left
            else:                   #This means we have traverse all nodes left to current so in LDR traversal of L is done
                soln.append(current.val) 
                pre.right = None       #Remove the link tree restored to original here 
                current = current.right
        else:               #In LDR  LD traversal is done move to R  
            soln.append(current.val)
            current = current.right

    return soln

Explication PFB de Morris In-order Traversal.

  public class TreeNode
    {
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null)
        {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    class MorrisTraversal
    {
        public static IList<int> InOrderTraversal(TreeNode root)
        {
            IList<int> list = new List<int>();
            var current = root;
            while (current != null)
            {
                //When there exist no left subtree
                if (current.left == null)
                {
                    list.Add(current.val);
                    current = current.right;
                }
                else
                {
                    //Get Inorder Predecessor
                    //In Order Predecessor is the node which will be printed before
                    //the current node when the tree is printed in inorder.
                    //Example:- {1,2,3,4} is inorder of the tree so inorder predecessor of 2 is node having value 1
                    var inOrderPredecessorNode = GetInorderPredecessor(current);
                    //If the current Predeccessor right is the current node it means is already printed.
                    //So we need to break the thread.
                    if (inOrderPredecessorNode.right != current)
                    {
                        inOrderPredecessorNode.right = null;
                        list.Add(current.val);
                        current = current.right;
                    }//Creating thread of the current node with in order predecessor.
                    else
                    {
                        inOrderPredecessorNode.right = current;
                        current = current.left;
                    }
                }
            }

            return list;
        }

        private static TreeNode GetInorderPredecessor(TreeNode current)
        {
            var inOrderPredecessorNode = current.left;
            //Finding Extreme right node of the left subtree
            //inOrderPredecessorNode.right != current check is added to detect loop
            while (inOrderPredecessorNode.right != null && inOrderPredecessorNode.right != current)
            {
                inOrderPredecessorNode = inOrderPredecessorNode.right;
            }

            return inOrderPredecessorNode;
        }
    }