习题里面要求用非递归中序遍历二叉树。
用栈的理解了，只要把递归树转换成栈的形式就行。
但是后来要求不用栈，在节点结构体中加入父节点指针做，试着写了下，可是总是有的情况无法正确遍历。

设定父节点是为了便于回溯到位探索节点处，这些都明白。

请问算法是什么样呢？谢谢。

这是我写的，这个只在一些情况下能正确遍历...


void inorder_itr(btree t){
     
     btree tmp=t;
     int cpt=1;
     int deepth_r=0;  /*探索的深度*/

     int i;
     while(cpt!=3){          /*遍历结束条件是用于遍历的指针3次遇到根节点指针*/

     
     while(tmp->lchild)tmp=tmp->lchild;          /*找到最左端节点*/
     
     printf("%d ",tmp->data);    /*打印该节点的值*/                    
     
     while(tmp->rchild){                         /*遍历该节点右子树*/
                       deepth_r++;               /*递增遍历深度*/
                       tmp=tmp->rchild;
                       printf("%d ",tmp->data);    /*依次打印数值*/     
     }
     
     for(i=deepth_r;i>=0;i--)tmp=tmp->parent;    /*返回到已经扩展的节点的上一层*/
     deepth_r=0;   

     if(!tmp){return;}
     
     while(!(tmp->rchild))                             {
                        printf("%d ",tmp->data);   
                        tmp=tmp->parent;
                        if(!tmp){return;}
     }
     
     if(tmp==t)cpt++;
     if(cpt==3)return;
     printf("%d ",tmp->data);   
     
     tmp=tmp->rchild;    /*遍历右子树*/
     if(tmp!=t->rchild)   
     deepth_r++;
                           
     
}     
}

希望请教一个好的算法，因为当时用栈时，是从递归树转换来的，所以算法很明确。
增加父节点指针是为了实现回溯的功能，但是具体实现起来挺闹心的。

谢谢大家。

[ 本帖最后由 刮目相看 于 2010-3-17 09:17 编辑 ]

刚刚学这部分，写的比较差，请别拍砖

请大家帮忙

不用栈的话，比较好的算法是怎么样的呢？

非递归的仍然可用栈，p=T;
1 遍历二叉树p=p->lchild,有左孩子则进栈，st[++top]=p,若无左孩子，退栈输出，p(st[--top])
2.看右孩子,p=p->rchild,若p不空，判断p所指向的结点的左孩子，若存在回到1.继续，否则退栈输出。

晕，我已经说明好几次，不用栈了。。。。。

只会用栈怎么办