#include
#include
#define Status int
#define TElemType char
#define OVERFLOW -2
#define OK 1
#define ERROR -1
#define MAXSIZE 100
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef struct BiTNode {
TElemType data;
struct BiTNode *lchild ,*rchild;
}BiTNode,*BiTree;
typedef struct {
BiTNode *base;
BiTNode *top;
int stacksize;
}Stack;
Status FInOrderTraverse(BiTree T,Status(*Visit)(TElemType e));
Status print(TElemType e);
Status InitStack(Stack & S);
Status Push(Stack &S,BiTree e);
Status StackEmpty(Stack &S);
Status GetTop(Stack &S, BiTree &e);
Status Pop(Stack &S,BiTree &e);
int main(){
BiTree T;
printf("%d\n",CreateBiTree(T));
printf("中序非递归遍历:\n");
printf("\n%d\n",FInOrderTraverse(T,print));
getchar();
getchar();
return 0;
}
Status CreateBiTree(BiTree &T){
char ch;
scanf("%c",&ch);
if (ch=='#') T=NULL;
else{
if(!(T=(BiTree)malloc(sizeof(BiTNode))))
exit(OVERFLOW);
T->data=ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
return OK;
}
Status FInOrderTraverse(BiTree T,Status(*Visit)(TElemType e)){
Stack S;
InitStack(S);
Push(S,T);
while(!StackEmpty(S)){
BiTree p;
while(GetTop(S,p)&&p){
Push(S,p->lchild);
printf("ddddd\n");
}
printf("ddddd\n");
////////////////////////////////////////////////////////////////////////////////////////////////////////////////printf执行
Pop(S,p);printf("ddddd\n");/////////////////////////////////////////////////////printf不执行
if(!StackEmpty(S)){
Pop(S,p);
if(!Visit(p->data))
return ERROR;
Push(S,p->rchild);
}//if
}//while
return OK;
}
Status InitStack(Stack &S){
S.base=(BiTree)malloc(STACK_INIT_SIZE*sizeof(BiTNode));
if(!S.base) exit(OVERFLOW);
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return OK;
}
Status Push(Stack &S,BiTree e){
if (S.top-S.base>=S.stacksize){//
S.base=(BiTNode*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(BiTNode));
if(!S.base) exit(OVERFLOW);
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top=*e;
S.top++;
return OK;
}
Status StackEmpty(Stack &S){
return (S.top==S.base);
}
Status Pop(Stack &S,BiTree &e){
if(S.top==S.base) return ERROR;
e=(S.top-1);
return OK;
}
Status GetTop(Stack &S, BiTree &e){
if(S.top==S.base) return ERROR;
e=(S.top-1);
printf("ddddd\n");
return OK;
}
Status print(TElemType e){
printf("%c",e);
return OK;
}
检查下代码,是不是死循环了。