스택이나 재귀를 사용하지 않고 Morris inorder tree traversal을 설명하십시오.

스택이나 재귀를 사용하지 않고 Morris inorder tree traversal을 설명하십시오.

---

누군가 스택이나 재귀를 사용하지 않고 다음 Morris inorder tree traversal 알고리즘을 이해하도록 도와 줄 수 있습니까? 나는 그것이 어떻게 작동하는지 이해하려고 노력했지만 그저 나를 탈출했습니다.

 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와 중위 순회에 대해이 속성을 사용합니다. 하지만 그 이상으로 나는 길을 잃었습니다.

편집 :이 동반 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 */
}

---

알고리즘을 올바르게 읽고 있다면 이것이 작동 방식의 예가되어야합니다.

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

첫째, X루트이므로 current. X왼쪽 자식이 있으므로 의 왼쪽 하위 트리 X의 맨 오른쪽 자식이 X됩니다 X. 즉, inorder 순회에서 바로 전임자 입니다. 따라서 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에는 두 자식이 있습니다. 그러나 루프의 이중 조건으로 인해 루프가 자체에 도달하면 중지되며, 이는 왼쪽 하위 트리가 이미 통과했음을 나타냅니다. 따라서 자체 인쇄하고 오른쪽 하위 트리 인 .YAB

B자신을 인쇄 한 다음 current되고 X같은 검사 과정을 통과하는, Y또한 계속 그 왼쪽 서브 트리가 통과 된 것을 실현했다 Z. 나머지 트리는 동일한 패턴을 따릅니다.

재귀가 필요하지 않습니다. 스택을 통한 역 추적에 의존하는 대신 (하위) 트리의 루트로 돌아가는 링크가 어쨌든 재귀 적 순서 트리 순회 알고리즘에서 액세스되는 지점으로 이동하기 때문입니다. 왼쪽 하위 트리가 완료되었습니다.

---

재귀 순서 순회는 : (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;
}

---

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

I think this code would be better to understand, just use a null to avoid infinite loops, don't have to use magic else. It can be easily modified to preorder.

---

I hope the pseudo-code below is more revealing:

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

Referring to the C++ code in the question, the inner while loop finds the in-order predecessor of the current node. In a standard binary tree, the right child of the predecessor must be null, while in the threaded version the right child must point to the current node. If the right child is null, it is set to the current node, effectively creating the threading, which is used as a returning point that would otherwise have to be on stored, usually on a stack. If the right child is not null, then the algorithm makes sure that the original tree is restored, and then continues traversal in the right subtree (in this case it is known that the left subtree was visited).

---

I've made an animation for the algorithm here: https://docs.google.com/presentation/d/11GWAeUN0ckP7yjHrQkIB0WT9ZUhDBSa-WR0VsPU38fg/edit?usp=sharing

This should hopefully help to understand. The blue circle is the cursor and each slide is an iteration of the outer while loop.

Here's code for morris traversal (I copied and modified it from geeks for geeks):

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)

참고URL : https://stackoverflow.com/questions/5502916/explain-morris-inorder-tree-traversal-without-using-stacks-or-recursion