Coding Recipies: Morris Inorder-Traversal

Morris Traversal is based on the concept of Threaded Binary Trees.
A binary tree is threaded by making all right child pointers that would normally be null point to the inorder successor of the node (if it exists) , and all left child pointers that would normally be null point to the inorder predecessor of the node."

Advantages:

1. Avoids recursion, which uses a call stack and consumes memory and time.
2. The node keeps a record of its parent.

Disadvantages:

1. The tree is more complex.
2. It is more prone to errors when both the children are not present and both values of nodes point to their ancestors.

Morris traversal is an implementation of in-order traversal that uses threading:

1. Create links to the in-order successor
2. Print the data using these links
3. Revert the changes to restore original tree.

http://www.cnblogs.com/AnnieKim/archive/2013/06/15/MorrisTraversal.html

1. 如果当前节点的左孩子为空，则输出当前节点并将其右孩子作为当前节点。

2. 如果当前节点的左孩子不为空，在当前节点的左子树中找到当前节点在中序遍历下的前驱节点。

   a) 如果前驱节点的右孩子为空，将它的右孩子设置为当前节点。当前节点更新为当前节点的左孩子。

   b) 如果前驱节点的右孩子为当前节点，将它的右孩子重新设为空（恢复树的形状）。输出当前节点。当前节点更新为当前节点的右孩子。

3. 重复以上1、2直到当前节点为空。

Code http://ideone.com/f3lN0T

public void inorderMorrisTraversal(Node root){

  

 if(root==null)

  return ;

  

 Node current=root;

 while(current!=null){

   

  if(current.left == null)

  {

   System.out.println(current.data);

   current = current.right;

  }

  else

  {

   Node pre =  current.left;

   while(pre.right != null && pre.right!=current)

    pre = pre.right;

    

   //pre = predessor of current node

    

   if(pre.right==null) //make the link

   {

    pre.right = current ;

    current = current.left;

   }

   else //Break the link

   {

    pre.right = null ;

    System.out.println(current.data);

    current = current.right;

   }

  }

 }

}

Read full article from Coding Recipies: Morris Inorder-Traversal