Wyjaśnij przemierzanie drzewa w kolejności Morrisa bez używania stosów lub rekursji

Czy ktoś może mi pomóc zrozumieć następujący algorytm przemierzania drzewa Morrisa bez używania stosów lub rekurencji? Próbowałem zrozumieć, jak to działa, ale po prostu mi to wymyka.

 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

Rozumiem, że drzewo jest modyfikowane w taki sposób, że current nodejest uczynił right childz max nodew right subtreei wykorzystać tę właściwość dla Inorder przechodzenia. Ale poza tym jestem zagubiony.

EDYCJA: Znaleziono ten towarzyszący kod C ++. Trudno mi było zrozumieć, w jaki sposób drzewo jest przywracane po modyfikacji. Magia tkwi w elseklauzuli, która jest uderzana po zmodyfikowaniu prawego liścia. Zobacz kod po szczegóły:

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

Jeśli dobrze czytam algorytm, powinien to być przykład tego, jak to działa:

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

Najpierw Xjest katalog główny, więc jest inicjowany jako current. Xma lewe dziecko, więc Xjest prawe skrajne prawe dziecko Xlewego poddrzewa - bezpośredniego poprzednika Xw wewnętrznym przechodzeniu. Więc Xstaje się właściwym dzieckiem B, a następnie currentjest ustawione na Y. Drzewo wygląda teraz następująco:

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

(Y)powyżej odnosi się do Yi wszystkich jego elementów podrzędnych, które są pomijane w przypadku problemów z rekursją. Ważna część jest jednak wymieniona. Teraz, gdy drzewo ma łącze z powrotem do X, przeglądanie jest kontynuowane ...

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

Następnie Ajest wyprowadzane, ponieważ nie ma lewego dziecka, i currentjest zwracane, do Yktórego zostało utworzone Aprawe dziecko w poprzedniej iteracji. W następnej iteracji Y ma dwoje dzieci. Jednak podwójny stan pętli powoduje jej zatrzymanie, gdy osiągnie samą siebie, co wskazuje, że jej lewe poddrzewo zostało już przekroczone. Tak więc drukuje się i kontynuuje z odpowiednim poddrzewem, którym jest B.

Bdrukuje się, a następnie currentstaje się X, który przechodzi przez ten sam proces sprawdzania, co Yzrobił, zdając sobie również sprawę, że jego lewe poddrzewo zostało przekroczone, kontynuując proces Z. Reszta drzewa ma ten sam wzór.

Rekurencja nie jest konieczna, ponieważ zamiast polegać na cofaniu się przez stos, łącze z powrotem do korzenia (pod) drzewa jest przenoszone do punktu, w którym byłby dostępny w rekurencyjnym algorytmie przechodzenia przez drzewo w kolejności - po jego zakończenie lewego poddrzewa.

Rekurencyjne in-order przechodzenie jest: (in-order(left)->key->in-order(right)). (jest to podobne do DFS)

Kiedy wykonujemy DFS, musimy wiedzieć, dokąd się cofnąć (dlatego zwykle trzymamy stos).

Kiedy przechodzimy przez węzeł nadrzędny, do którego będziemy musieli cofnąć się -> znajdujemy węzeł, z którego będziemy musieli cofnąć się i aktualizujemy jego łącze do węzła nadrzędnego.

Kiedy się cofniemy? Kiedy nie możemy iść dalej. Kiedy nie możemy iść dalej? Kiedy nie ma pozostawionego dziecka.

Gdzie wracamy? Uwaga: do SUKCESORA!

Tak więc, gdy podążamy za węzłami wzdłuż ścieżki po lewej stronie, ustaw poprzednik na każdym kroku tak, aby wskazywał na bieżący węzeł. W ten sposób poprzednicy będą mieli linki do następców (łącze do cofania).

Idziemy w lewo, dopóki możemy, dopóki nie będziemy musieli się wycofać. Kiedy musimy się cofnąć, drukujemy bieżący węzeł i podążamy za odpowiednim łączem do następcy.

Jeśli właśnie się wycofaliśmy -> musimy podążać za prawym dzieckiem (skończyliśmy z lewym dzieckiem).

Jak sprawdzić, czy właśnie się wycofaliśmy? Pobierz poprzednika bieżącego węzła i sprawdź, czy ma poprawne łącze (do tego węzła). Jeśli tak - to postępowaliśmy zgodnie z nim. usuń łącze, aby przywrócić drzewo.

Jeśli nie było lewego linku => nie cofaliśmy się i powinniśmy kontynuować za lewymi dziećmi.

Oto mój kod Java (przepraszam, to nie jest 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;
}

Animację dla algorytmu zrobiłem tutaj: https://docs.google.com/presentation/d/11GWAeUN0ckP7yjHrQkIB0WT9ZUhDBSa-WR0VsPU38fg/edit?usp=sharing

Miejmy nadzieję, że to pomoże zrozumieć. Niebieskie kółko to kursor, a każdy slajd to iteracja zewnętrznej pętli while.

Oto kod dla morris traversal (skopiowałem i zmodyfikowałem go z maniaków dla maniaków):

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

Myślę, że ten kod lepiej byłoby zrozumieć, po prostu użyj wartości null, aby uniknąć nieskończonych pętli, nie musisz używać innych magii. Można go łatwo zmodyfikować, aby zamówić w przedsprzedaży.

Znalazłem bardzo dobre obrazkowe wyjaśnienie Morrisa Traversala .

Mam nadzieję, że poniższy pseudokod jest bardziej pouczający:

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

Odnosząc się do kodu C ++ w pytaniu, wewnętrzna pętla while znajduje poprzednika w kolejności bieżącego węzła. W standardowym drzewie binarnym prawe dziecko poprzednika musi mieć wartość null, podczas gdy w wersji z wątkami prawe dziecko musi wskazywać na bieżący węzeł. Jeśli prawe dziecko ma wartość null, jest ustawiane na bieżący węzeł, skutecznie tworząc wątek , który jest używany jako punkt powrotu, który w przeciwnym razie musiałby być przechowywany, zwykle na stosie. Jeśli prawe dziecko nie jest zerowe, algorytm upewnia się, że oryginalne drzewo zostało przywrócone, a następnie kontynuuje przeglądanie w prawym poddrzewie (w tym przypadku wiadomo, że odwiedzono lewe poddrzewo).

Złożoność czasowa rozwiązania Pythona: O (n) Złożoność przestrzeni: O (1)

Doskonałe wyjaśnienie przejścia 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

PFB Wyjaśnienie przejścia Morris w kolejności.

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