http://chriszeng87.iteye.com/blog/1169619
有个二叉树,每个节点除了左右指针外,还有一个指向父节点的指针。
要求不用递归,中序遍历这棵树。另要求空间复杂度是O(1).
要求不用递归,中序遍历这棵树。另要求空间复杂度是O(1).
空间复杂度为O(1),摆明就是不让用堆栈模拟递归,所以想了想思路,也请教过好几个朋友,大家都基本想法都差不多,由于有指向父节点的指针,必定可以回溯,从而可以不需要堆栈来做记录.
但是实现起来,却发现很多细节需要完善,比如遍历的终止条件,现在我是用预先遍历到最后一个右子树,用这个指针作为终止条件.
- /*思路:
- 关于终止条件:中序遍历终止于最后的rchild,只能先遍历一遍,将该节点作为终止条件。
- 对遍历时候的 cur节点设置一个状态(0,1,2)
- 0标识其左,右节点情况尚未处理
- 1标识其左节点被处理(包括左节点不存在的情况)
- 2标识从右节点返回(包括右节点不存在的情况)
- 3种状态的判断用(post->parent->lchild == post)这样的方法判断。
- */
- void inorder_norecursive(LinkTree *root)
- {
- LinkTree * cur=root, * post, *fin;
- int cur_state = 0;
- while(cur != NULL) //查找终止条件
- {
- post = cur;
- cur = cur->rchild;
- }
- fin = post;
- cur = root;
- post = NULL;
- printf("fin data :%d /n",fin->data);
- while( !(cur == fin && cur_state >=1) )
- {
- while(cur != NULL && cur->lchild != NULL && cur_state != 2) //搜索:每次遍历,当前状态清零,找到可以打印的点,从右节点返回不应该继续向下遍历
- {
- cur_state = 0;
- cur = cur->lchild;
- }
- if( (cur == NULL && cur_state == 1) || cur_state == 2) //返回:右节点为空,返回的情况或者从右节点返回
- {
- cur = post;
- if(cur->parent->lchild == cur)
- cur_state = 1;
- else if(cur->parent->rchild == cur)
- cur_state = 2;
- cur = cur->parent;
- }
- if( cur->lchild == NULL && cur_state == 0)
- cur_state = 1;
- post = cur; //post针对cur遍历到NULL时候返回,记录有效节点
- if( cur_state == 1) //中序打印
- {
- printf(" %d ",cur->data);
- if(cur == fin) //打印最后一个,显式退出
- break;
- }
- else if(cur_state == 2) //节点的2个子节点已被处理,向上返回
- continue;
- if(cur->rchild == fin) //如果是fin节点的父节点,提前设置cur_state状态,防止while退出
- cur_state = 0;
- cur = cur->rchild;
- }
- }