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

有个二叉树，每个节点除了左右指针外，还有一个指向父节点的指针。
要求不用递归，中序遍历这棵树。另要求空间复杂度是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

 

 

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

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

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

 

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