Morris 算法介绍

http://blog.csdn.net/mxw976235955/article/details/39829973

http://www.tuicool.com/articles/zA7NJbj

算法伪码：

MorrisInOrder()：

while 没有结束

如果当前节点没有左后代

 访问该节点

 转向右节点

否则

 找到左后代的最右节点，且使最右节点的右指针指向当前节点

 转向左后代节点

C++实现：

void bst_morris_inorder(struct bst_node *root) {

struct bst_node p = root, tmp;

while (p) {

   if (p->left == NULL) {  

       printf("%d ", p->key);  

       p = p->right;  

   }  

   else {  

       tmp = p->left;  

       while (tmp->right != NULL && tmp->right != p)  

           tmp = tmp->right;  

       if (tmp->right == NULL) {  

           tmp->right = p;  

           p = p->left;  

       }  

       else {  

           printf("%d ", p->key);  

           tmp->right = NULL;  

           p = p->right;  

       }  

   }  

}

}