# include <stdio.h>
# include<malloc.h>
typedef struct BiTNode
{
    char data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

typedef struct
{
    BiTree base;
    BiTree top;
}SqStack;

SqStack InitStack(SqStack S)
{
    S.base=(struct BiTNode *)malloc(100*sizeof(struct BiTNode));
    S.top=S.base;
    return S;
}

int GetTop(SqStack S,BiTree e)
{
    S.top--;
    e=S.top;
    S.top++;
    return 1;
}

SqStack Push(SqStack S,BiTree e)
{
       S.top=e;
       S.top++;
       return S;
}

void visit(char e)
{
    printf("%c",e);
}
int StackEmpty(SqStack S)
{
    if(S.base==S.top)
        return 1;
    else
        return 0;
}
SqStack Pop(SqStack S,BiTree e)
{
    e=--S.top;
    return S;
}
void InOrderTraverse(BiTree T)
{
    BiTree p;
    SqStack S;
    S=InitStack(S);
    S=Push(S,T);
    while(!StackEmpty(S))
    {
        while(GetTop(S,p)&&p) S=Push(S,p->lchild);
        S=Pop(S,p);
        if(!StackEmpty(S))
        {
            S=Pop(S,p);
            visit(p->data);
            S=Push(S,p->rchild);
        }
    }
}
BiTree CreateBiTree(BiTree T)
{
    char ch;
    scanf("%c",&ch);
    if(ch==' ') T=NULL;
    else
    {
        T=(BiTNode *)malloc(sizeof(BiTNode));
        T->data=ch;
        T->lchild=CreateBiTree(T->lchild);
        T->rchild=CreateBiTree(T->rchild);
    }
    return T;
}
void main()
{
        BiTree T;
        T=(BiTNode *)malloc(sizeof(BiTNode));
        T=CreateBiTree(T);
        InOrderTraverse(T);
}

# include <stdio.h>
# include<malloc.h>
typedef struct BiTNode
{
    char data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

typedef struct
{
    BiTree *base;
    BiTree *top;
}SqStack;

SqStack InitStack(SqStack S)
{
    S.base=(BiTree *)malloc(100*sizeof(BiTree));
    S.top=S.base;
    return S;
}

int GetTop(SqStack S,BiTree *e)
{
 //   S.top--;
    *e=*(S.top-1);
    //S.top++;
    return 1;
}

SqStack Push(SqStack S,BiTree e)
{
       *S.top = e;
       S.top++;
       return S;
}

void visit(char e)
{
    printf("%c ",e);
}
int StackEmpty(SqStack S)
{
    if(S.base==S.top)
        return 1;
    else
        return 0;
}
SqStack Pop(SqStack S,BiTree *e)
{
    *e=*--S.top;
    return S;
}
void InOrderTraverse(BiTree T)
{
    BiTree p;
    SqStack S;
    S=InitStack(S);
    S=Push(S,T);
    while(!StackEmpty(S))
    {
        while( GetTop(S,&p) && p )
            S=Push(S,p->lchild);
        S=Pop(S,&p);
        if(!StackEmpty(S))
        {
            S=Pop(S,&p);
            visit(p->data);
            S=Push(S,p->rchild);
        }
    }
}
BiTree CreateBiTree(BiTree T)
{
    char ch;
    scanf("%c",&ch);
    getchar();
    if(ch==' ')
        T=NULL;
    else
    {
        T=(BiTNode *)malloc(sizeof(BiTNode));
        T->data=ch;
        T->lchild=CreateBiTree(T->lchild);
        T->rchild=CreateBiTree(T->rchild);
    }
    return T;
}
void main()
{
        BiTree T;
        //T=(BiTNode *)malloc(sizeof(BiTNode));
        T=CreateBiTree(T);
        InOrderTraverse(T);
        printf("\n");
}

收到的鲜花

• tzhg555 于 2010-12-06 12:49 送鲜花  3朵  

非常感谢。。。CreateBiTree里面的getchar（）好像不需要啊。。。现在出来了，真的非常感谢！！！

对