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

Question

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

 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

Я понимаю, что дерево модифицируется таким образом, что current node, становится right child из max node в right subtree и использую это свойство для обхода по порядку. Но помимо этого я потерян.

EDIT: Нашел этот сопроводительный код 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 */
}

Answer 1

Если я правильно читаю алгоритм, это должно быть примером того, как он работает:

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

Во-первых, X - это корень, поэтому он инициализируется как current.У X есть левый потомок, поэтому X становится самым правым правым потомком левого поддерева X - непосредственного предшественника X в обходе по порядку.Таким образом, X становится правильным потомком B, тогда current устанавливается на Y.Дерево теперь выглядит так:

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

(Y) выше относится к Y и всем его дочерним элементам, которые опущены для проблем рекурсии.В любом случае важная часть указана.Теперь, когда дерево имеет ссылку на X, обход продолжается ...

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

Затем выводится A, поскольку у него нет левого потомка, а current возвращается в Y, который был сделан правым потомком A в предыдущей итерации.На следующей итерации Y имеет обоих потомков.Тем не менее, двойное условие цикла заставляет его останавливаться, когда он достигает себя, что указывает на то, что его левое поддерево уже пройдено.Таким образом, он печатает сам и продолжает свое правое поддерево, которое B.

B печатает себя, а затем current становится X, что проходит тот же процесс проверки, что и Y сделал, также понимая, что его левое поддерево было пройдено, продолжая с Z.Остальная часть дерева следует той же схеме.

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

Answer 2

Рекурсивный обход в порядке: (in-order(left)->key->in-order(right)).(это похоже на DFS)

Когда мы выполняем DFS, нам нужно знать, куда возвращаться (именно поэтому мы обычно храним стек).

Когда мы проходим через родительский узелна который нам нужно будет вернуться -> мы найдем узел, с которого нам нужно будет вернуться и обновить его ссылку на родительский узел.

Когда мы вернемся назад?Когда мы не можем идти дальше.Когда мы не можем идти дальше?Когда не осталось ни одного ребенка.

Куда мы возвращаемся?Примечание: для SUCCESSOR!

Итак, следуя узлам по левостороннему пути, на каждом шаге устанавливаем предшественника, чтобы он указывал на текущий узел.Таким образом, у предшественников будут ссылки на преемников (ссылка для возврата).

Мы следуем налево, пока можем, пока нам не нужно возвращаться.Когда нам нужно вернуться назад, мы печатаем текущий узел и следуем по правой ссылке на преемника.

Если мы только что вернулись назад -> мы должны следовать за правым потомком (мы закончили с левым потомком).

Как узнать, вернулись ли мы только что?Получить предшественник текущего узла и проверить, имеет ли он правильную ссылку (на этот узел).Если есть - чем мы следовали за этим.удалите ссылку, чтобы восстановить дерево.

Если левой ссылки не было =>, мы не возвращались назад, и нам следует продолжить, следуя левым дочерним элементам.

Вот мой код Java (Извините, это не 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;
}

Answer 3

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

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

Answer 4

Надеюсь, приведенный ниже псевдокод более показателен:

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

Ссылаясь на код C ++ в вопросе, внутренний цикл while находит предшественника по порядку текущего узла. В стандартном двоичном дереве правый дочерний элемент предшественника должен быть нулевым, в то время как в многопоточной версии правый дочерний элемент должен указывать на текущий узел. Если правый дочерний элемент равен нулю, он устанавливается на текущий узел, фактически создавая threading , который используется как точка возврата, которая в противном случае должна была бы храниться, обычно в стеке. Если правый дочерний элемент равен , а не null, то алгоритм проверяет, восстановлено ли исходное дерево, и затем продолжает обход в правом поддереве (в этом случае известно, что было посещено левое поддерево).