162 votes

Expliquer la traversée d'arbres en ordre de Morris sans utiliser de piles ou de récursivité

Quelqu'un peut-il m'aider à comprendre les éléments suivants Morris aussitôt l'arbre transversal de l'algorithme sans l'aide de piles ou de la récursivité ? J'essayais de comprendre comment il fonctionne, mais son vient de s'échapper de moi.

 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é de façon que l' current node, est faite de l' right child de la max node en right subtree et d'utiliser cette propriété pour afinde traversée. Mais au-delà, je suis perdu.

EDIT: Trouvé cet accompagnement de code c++. J'ai été un moment difficile de comprendre comment l'arbre est restaurée après qu'il est modifié. La magie réside dans la else clause, qui est touché une fois le droit de la feuille est modifié. 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 */
}

189voto

Talonj Points 897

Si je suis la lecture de l'algorithme de droite, ce devrait être un exemple de comment cela fonctionne:

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

Tout d'abord, X est la racine, de sorte qu'il est initialisé current. X a gauche de l'enfant, de sorte X est faite de l'extrême droite au droit de l'enfant d' X's sous-arbre gauche -- le prédécesseur immédiat X dans un afinde traversée. Donc, X est fait le droit de l'enfant d' B, alors current est définie à l' Y. L'arbre ressemble maintenant à ceci:

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

(Y) ci-dessus se réfère Y et tous ses enfants, qui sont omis pour la récursivité des questions. La partie importante est listé toute façon. Maintenant que l'arbre a un lien de retour vers X, la traversée se poursuit...

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

Ensuite, A est sorti, parce qu'il n'a pas laissé d'enfant, et current est retourné à l' Y, ce qui a été fait Adu droit de l'enfant à l'itération précédente. Sur la prochaine itération, Y a deux enfants. Cependant, la double condition de la boucle s'arrête quand il atteint lui-même, ce qui est une indication qu'il est sous-arbre gauche a déjà été parcouru. Donc, il imprime lui-même, et se poursuit avec son sous-arbre droit, qui est - B.

B imprime lui-même, et ensuite, current devient X, qui passe par le même processus de vérification en tant que Y ont, aussi réaliser que son sous-arbre gauche a été parcouru, en continuant avec l' Z. Le reste de l'arbre suit le même schéma.

Pas de récursivité est nécessaire, parce qu'au lieu de compter sur les retours en arrière par une cheminée, un lien de retour à la racine de la (sous -) arbre est déplacé vers le point où il serait accessible en récursif aussitôt l'arbre transversal de l'algorithme de toute façon, après son sous-arbre gauche est terminé.

3voto

Adeath Points 1
 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 des boucles infinies, ne devez pas utiliser la magie autrement. Il peut être facilement modifié en pré-commande.

2voto

Edgar Points 1

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 n'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é).

Prograide.com

Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.

Powered by:

X