Объясните обход дерева порядка Морриса без использования стеков или рекурсии.

Может ли кто-нибудь помочь мне понять следующий алгоритм обхода дерева порядка Морриса без использования стеков или рекурсии? Я пытался понять, как это работает, но это просто ускользало от меня.

 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

Я понимаю, что дерево изменено таким образом, что текущий узел , делается правым потомком узла max в правом поддереве и использует это свойство для обхода в порядке. Но помимо этого, я потерялся.

РЕДАКТИРОВАТЬ: Нашел этот сопровождающий код C ++. Мне было трудно понять, как дерево восстанавливается после модификации. Магия заключается в предложении else , которое выполняется после изменения правого листа. Подробнее см. В коде:

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