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