解释Morris inorder树遍历而不使用堆栈或recursion
有人可以帮助我理解下面的Morris inorder树遍历algorithm，而不使用堆栈或recursion？ 我试图了解它是如何工作的，但它只是逃避我。
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, ie, 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, ie, current = current->left 我知道树被修改的方式是将current node作为right child right subtree max node的right subtree max node ，并将该属性用于中序遍历。 但除此之外，我迷路了。
编辑：发现这个随附的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 ie, 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 */ }
如果我正在阅读algorithm，这应该是一个如何工作的例子：
X / \ YZ / \ / \ ABCD
首先， X是根，所以它被初始化为current 。 X有一个左边的孩子，所以X成为X的左子树的右边最右边的孩子 – 在顺序遍历中X的直接前辈。 所以X是B的右边的子，那么current是Y 树现在看起来像这样：
Y / \ AB \ X / \ (Y) Z / \ CD
(Y)是指Y及其所有的孩子，因为recursion问题而被忽略。 无论如何，重要的部分是列出的。 现在树有一个链接回到X，遍历继续…
A \ Y / \ (A) B \ X / \ (Y) Z / \ CD
然后A被输出，因为它没有离开孩子，并且current被返回到Y ，这在先前的迭代中被作为A的右边的孩子。 在下一个迭代中，Y有两个孩子。 然而，循环的双重条件使它在到达自身时停止，这表明它的左子树已经被遍历了。 所以，它打印自己，并继续其正确的子树，这是B 。
B打印自己，然后current变成X ，它经历了和Y一样的检查过程，也意识到它的左子树已经被遍历，继续Z 树的其余部分遵循相同的模式。
没有recursion是必要的，因为不是依靠通过堆栈回溯，而是返回到（子）树的根的链接被移动到它将被访问的地点，无论如何在recursion中序树遍历algorithm中 – 左子树已经结束。
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 } } }
我认为这个代码会更好理解，只是使用null来避免无限循环，不必使用其他的魔法。 它可以很容易地修改为预定。
我希望下面的伪代码更具启发性：
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 ++代码，inner while循环find当前节点的有序前辈。 在一个标准的二叉树中，前导的右侧子节点必须为空，而在线程化版本中，右侧子节点必须指向当前节点。 如果右侧的子元素为空，则将其设置为当前节点，从而有效地创build线程 ，该线程将用作返回点，否则该线程必须存储在堆栈中。 如果右边的子元素不为空，那么algorithm确保原始树被恢复，然后继续在右子树中遍历（在这种情况下，已知左子树被访问）。
recursion按序遍历是:( (in-order(left)->key->in-order(right)) 。 （这与DFS相似）
当我们做DFS时，我们需要知道在哪里回溯（这就是为什么我们通常保持堆栈）。
当我们通过一个父节点，我们将需要回溯到 – >我们find我们将需要回溯并更新其链接到父节点的节点。
当我们回溯？ 当我们不能进一步。 当我们不能进一步？ 当没有离开孩子的时候。
我们回到哪里？ 注意：对于SUCCESSOR！
所以，当我们跟随左子path上的节点时，在每一步设置前驱指向当前节点。 这样，前辈们就可以和后继者build立联系（回溯链接）。
我们沿着左边，我们可以，直到我们需要回溯。 当我们需要回溯时，我们打印当前节点并按照正确的链接inheritance。
如果我们只是回溯 – >我们需要跟随正确的孩子（我们完成了左边的孩子）。
如何判断我们是否只是回溯？ 获取当前节点的前任，并检查它是否有正确的链接（到这个节点）。 如果它 – 比我们跟着它。 删除链接来恢复树。
如果没有左边的链接=>我们没有回去，应该继续跟随左边的孩子。
这是我的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; }
