不要栈实现二叉树非递归中序遍历
不用栈实现二叉树非递归中序遍历
有个二叉树,每个节点除了左右指针外,还有一个指向父节点的指针。
要求不用递归,中序遍历这棵树。另要求空间复杂度是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;
- }
- }
转自: http://blog.csdn.net/hairetz/article/details/5069128
// 中序遍历伪代码:非递归版本,不用栈,增加指向父节点的指针
中序遍历的第二个非递归版本:采用指向父节点的指针回溯。这个与先序遍历是非常类似的,不同之处在于,先序遍历只要一遇到节点,那么没有被访问那么立即访问,访问完毕后尝试向左走,如果左孩子补课访问,则尝试右边走,如果左右皆不可访问,则回溯;中序遍历是先尝试向左走,一直到左边不通后访问当前节点,然后尝试向右走,右边不通,则回溯。(这里不通的意思是:节点不为空,且没有被访问
- void InOrder3(TNode* root)
- {
- while ( root != NULL ) // 回溯到根节点时为NULL,退出
- {
- while ( root->left != NULL && !root->left->bVisited )
- { // 沿左子树向下搜索当前子树尚未访问的最左节点
- root = root->left;
- }
- if ( !root->bVisited )
- { // 访问尚未访问的最左节点
- Visit(root);
- root->bVisited=true;
- }
- if ( root->right != NULL && !root->right->bVisited )
- { // 遍历当前节点的右子树
- root = root->right;
- }
- else
- { // 回溯至父节点
- root = root->parent;
- }
- }
- }
这一部分转自:http://blog.csdn.net/kofsky/article/details/2886453