帮忙看下这个非递归树的中序遍历算法

Question

Status InOrderTraverse(BiTree T,Status(*Visit)(TElemType e)){
//采用二叉链表存储结构,visit是对数据元素操作的应用函数.
//中序遍历二叉树T的非递归算法,对每个数据元素调用函数visit.
InitStack();push(S,T);//根指针进栈
while(!StackEmpty(S)){
while(GetTop(S,p)&&p)Push(S,p->lchild);//向左走到尽头
Pop(S,p); //空指针退栈
if(!StackEmpty(s)){ //访问结点，向右一步
Pop(S,p);if(!Visit(p->data))return ERROR;
Push(S,p->rchild);
}
}
书上是上面这么写的，可我总觉得Push(S,p->lchild)应该写成Push(S,p=p->lchild)
Push(S,p->rchild)应该写成Push(S,p=p->lchild)
是书写错了，还是我理解错了，没必要改？

Answer 1

没必要改。
注意看这一句：while(GetTop(S,p)&&p)Push(S,p->lchild);//向左走到尽头
当Push(S,p->lchild)之后，p虽然没有改变，但立即就会再执行while(GetTop(S,p)&&p)，这里会先执行GetTop(S,p)，意思是将栈S中最顶端的那个值赋值给p。这样，p的新值就成为老p的lchild了。（因为p->lchild刚被push到栈的顶端了）。

Answer 2

#include<stdio.h> #include<stdlib.h> #define SIZE 8 typedef struct BTree{ char data; struct BTree *LChild; struct BTree *RChild; }BTree; typedef struct Stack{ BTree *bt; }Stack; void createBTree(){ BTree *bt,*root,*p,*q; char ch; int top=-1; Stack s[SIZE]; ch=getchar(); root=bt=(BTree*)malloc(sizeof(BTree)); //先创建根结点 bt->data=ch; top++; s[top].bt=bt; //根结点地址入栈 do{ while(bt!=NULL){ //若当前结点不为空则,创建左孩子 ch=getchar(); if(ch==' '){ //若输入空格,则代表结点为空 bt->LChild=NULL; bt=bt->LChild; } else { bt->LChild=(BTree*)malloc(sizeof(BTree));//若输入的不为空格 bt->LChild->data=ch; //则分配空间,建立左结点 top++; s[top].bt=bt->LChild; //并将创建的结点地址入栈 bt=bt->LChild; //让bt指向当前刚创建的结点 } }; // 若上面的循环结束,此时左孩子创建完毕/ if(top!=-1){ //出栈 bt=s[top].bt; top--; ch=getchar(); if(ch==' '){ bt->RChild=NULL; bt=bt->RChild; } else { //若输入的字符不是空格,则对刚出栈的结点创建右子树 bt->RChild=(BTree*)malloc(sizeof(BTree)); bt->RChild->data=ch; top++; s[top].bt=bt->RChild; //并将刚创建的结点地址入栈 bt=bt->RChild; //让bt指向当前刚创建的结点 } } //只要bt不为空,或者top不等于-1,就继续做循环 }while(bt!=NULL||top!=-1); printf("二叉树创建完毕!\n"); //中序非递归遍历 top=-1; //创建完二叉树,栈已经为空了,故可以重复利用 printf("中序非递归遍历结果\n"); p=root; //将根结点赋给p do{ //只要p不为空,或者top不等于-1,就继续做循环 while(p!=NULL){ top++; s[top].bt=p;//结点入栈 p=p->LChild;//继续遍历,直到左孩子为空 }; if(top!=-1){ p=s[top].bt; //根出栈 top--; printf(" %c",p->data);//访问根结点 p=p->RChild; //若有右孩子,则访问 } }while(p!=NULL||top!=-1); printf("\n"); printf("前序非递归遍历结果\n"); top=-1; p=root; do{ while(p!=NULL){ printf(" %c",p->data);//访问根结点 top++; s[top].bt=p; p=p->LChild; //中序遍历左子树 }; if(top!=-1){ p=s[top].bt; top--; p=p->RChild;//中序遍历右子树 } }while(p!=NULL||top!=-1); printf("\n"); printf("后序非递归遍历结果\n"); //后序非递归遍历 top=-1; q=NULL; p=root; while(p!=NULL||top!=-1){ while(p!=NULL){ top++; s[top].bt=p; p=p->LChild; }; if(top!=-1){ p=s[top].bt; if((p->RChild==NULL)||(p->RChild==q)){ printf(" %c",p->data); q=p; top--; p=NULL; } else p=p->RChild; } }; printf("\n"); } void main(){ printf("输入非空字符代表非叶结点，输入空格代表叶节点\n"); createBTree(); }
更多数据结构及算法请参考 http://blog.csdn.net/yong369044325

Answer 3

没必要。GetTop(S,p) 和Pop(S,p)会对p进行更新