二叉树的中序非递归遍历

Question

#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 20
typedef char TElemType;
typedef struct BiNode{
    TElemType date;
    struct BiNode *lchild,*rchild;
}BiNode,*BiTree;
typedef struct{
    TElemType *base,*top;
    int StackSize;
}Stack;
InitTree(BiTree *t)
{
    *t=NULL;
}
InitStack(Stack *s)
{
    s->base=(TElemType*)malloc(sizeof(TElemType)*MAXSIZE);
    if(!s->base) exit(-1);
    s->top=s->base;
    s->StackSize=MAXSIZE; 
}
int Creat(BiTree *t)
{
    TElemType ch;
    scanf("%c",&ch);
    if(ch!='#'){
        (*t)=(BiNode*)malloc(sizeof(BiNode));
        (*t)->date=ch;
        Creat(&(*t)->lchild);
        Creat(&(*t)->rchild);
    }
    else *t=NULL;
}
int visit(BiTree t)//遍历 
{
    if(t!=NULL) printf("%c ",t->date);
    return 0;
}
int Push(Stack **s,BiNode *p)
{
    if((*s)->top-(*s)->base==(*s)->StackSize){
        printf("栈满，入栈失败！");    
        return 0;
    }
    *(*s)->top++=p;
}
int Pop(Stack **s)
{
    if((*s)->top-(*s)->base==0){
        printf("栈空，出栈失败！");
        return 0;
    }
    return *(*s)->top--;
}
int InTraverse(BiTree t,Stack *s)
{
    while(s->top-s->base!=0&&t!=NULL)
        if(t!=NULL){
            Push(&(*s),t);
            t=t->lchild;
        }
        else{
            t=Pop(&(*s));
            visit(t);
            t=t->rchild;
        }
} 
int main()
{
    BiTree T;
    Stack S;
    InitTree(&T);
    InitStack(&S);
    Creat(&T);
    printf("\n中序遍历的非递归算法：");
    InTraverse(T,&S);
}

Answer 1

改好了，主要问题还是在push函数，不能将top指向树节点，因为堆栈有自己的内存空间，只能进行内容复制
其它也有不少问题

#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 20
typedef char TElemType;
typedef struct BiNode{
    TElemType date;
    struct BiNode *lchild,*rchild;
}BiNode,*BiTree;
typedef struct{
    BiNode *base,*top;
    int StackSize;
}Stack;
void InitTree(BiTree *t)
{
    *t=NULL;
}
void InitStack(Stack *s)
{
    s->base=(BiNode*)malloc(sizeof(BiNode)*MAXSIZE);
    if(!s->base) exit(-1);
    s->top=s->base;
    s->StackSize=MAXSIZE; 
}
int Creat(BiTree *t)
{
    TElemType ch;
    scanf("%c",&ch);
    if(ch!='#'){
        (*t)=(BiNode*)malloc(sizeof(BiNode));
        (*t)->lchild  = NULL;
        (*t)->rchild  = NULL;
        (*t)->date=ch;
        Creat(&(*t)->lchild);
        Creat(&(*t)->rchild);
    }
    else *t=NULL;
    return 0;
}
int visit(BiTree t)//遍历 
{
    if(t!=NULL) printf("%c ",t->date);
    return 0;
}
int Push(Stack **s,BiNode *p)
{
    if((*s)->top-(*s)->base==(*s)->StackSize){
        printf("栈满，入栈失败！");    
        return 0;
    }
    (*s)->top++;
    (*s)->top->date = p->date;
    (*s)->top->lchild = p->lchild;
    (*s)->top->rchild = p->rchild;
    return 1;
}
BiNode* Pop(Stack **s)
{
    if((*s)->top-(*s)->base==0){
        printf("栈空，出栈失败！");
        return 0;
    }
    BiNode * p= (*s)->top;
    (*s)->top--;
    return p;
}
int InTraverse(BiTree t,Stack *s)
{
    while((s->top-s->base!=0) || t!=NULL)
    {
        if(t!=NULL){
            Push(&s,t);
            t=t->lchild;
        }
        else{
            t=Pop(&s);
            visit(t);
            t=t->rchild;
        }
    }
    return 1;
} 
int main()
{
    BiTree T;
    Stack S;
    InitTree(&T);
    InitStack(&S);
    Creat(&T);
    printf("\n中序遍历的非递归算法：");
    InTraverse(T,&S);
}