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

Ответ 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. Остальная часть дерева следует той же схеме.

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

Ответ 2

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

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

Когда мы перейдем к родительскому node, к которому нам понадобится обратный путь к → , мы найдем node, который нам нужно будет отменить и обновить его ссылку на родительский node.

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

Где мы возвращаемся? Примечание: к УСПЕХУ!

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

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

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

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

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

Вот мой код Java (Извините, это не С++)

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

Ответ 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
            }        
        }
    }

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

Ответ 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

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

Ответ 5

Я сделал анимацию для алгоритма здесь: https://docs.google.com/presentation/d/11GWAeUN0ckP7yjHrQkIB0WT9ZUhDBSa-WR0VsPU38fg/edit?usp=sharing

Надеюсь, это поможет понять. Синий круг - это курсор, а каждый слайд - итерация внешнего цикла while.

Вот код для обхода Морриса (я скопировал и изменил его из гиков для гиков):

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)