不用栈实现二叉树非递归中序遍历

有个二叉树，每个节点除了左右指针外，还有一个指向父节点的指针。
要求不用递归，中序遍历这棵树。另要求空间复杂度是O(1).

?

空间复杂度为O(1),摆明就是不让用堆栈模拟递归,所以想了想思路,也请教过好几个朋友,大家都基本想法都差不多,由于有指向父节点的指针,必定可以回溯,从而可以不需要堆栈来做记录.

?

转自:?http://blog.csdn.net/hairetz/article/details/5069128

?

?

//?中序遍历伪代码：非递归版本，不用栈，增加指向父节点的指针

中序遍历的第二个非递归版本：采用指向父节点的指针回溯。这个与先序遍历是非常类似的，不同之处在于，先序遍历只要一遇到节点，那么没有被访问那么立即访问，访问完毕后尝试向左走，如果左孩子补课访问，则尝试右边走，如果左右皆不可访问，则回溯；中序遍历是先尝试向左走，一直到左边不通后访问当前节点，然后尝试向右走，右边不通，则回溯。（这里不通的意思是：节点不为空，且没有被访问

1. void?InOrder3(TNode*?root)
2. {????while?(?root?!=?NULL?)?//?回溯到根节点时为NULL，退出
3. ????{????????while?(?root->left?!=?NULL?&&?!root->left->bVisited?)
4. ????????{??????????????????//?沿左子树向下搜索当前子树尚未访问的最左节点???????????????????????root?=?root->left;
5. ????????}????????if?(?!root->bVisited?)
6. ????????{??????????????????//?访问尚未访问的最左节点????????????Visit(root);
7. ????????????root->bVisited=true;????????}
8. ????????if?(?root->right?!=?NULL?&&?!root->right->bVisited?)????????{??????????????????//?遍历当前节点的右子树??
9. ????????????root?=?root->right;????????}
10. ????????else????????{?????????????????//?回溯至父节点
11. ????????????root?=?root->parent;????????}
12. ????}}

?

这一部分转自：http://blog.csdn.net/kofsky/article/details/2886453

?