|
|
#2
寒风中的细雨2010-12-05 22:22
# 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"); } |
# 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);
}