
程序代码:
仅供参考
#include <stdio.h >
#include <stdlib.h>
#define OVERFLOW 0
#define OK 1
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef char SElemType ;
typedef int Status ;
typedef struct BiTNode
{ SElemType data ;
struct BiTNode *lchild ,*rchild ; //左右孩子指针
} BiTNode , *BiTree ;
typedef struct {
BiTree *base ;
BiTree *top ;
int stacksize ;
} SqStack ;
Status StackEmpty (SqStack s )
{ if (s.base==s.top) return 1;
else return 0 ;
} //stackempty
Status InitStack (SqStack &s)
{ s.base=(BiTree *)malloc (STACK_INIT_SIZE *sizeof (BiTree )) ;
if (!s.base) exit (OVERFLOW ) ;
s.top = s.base ;
s.stacksize =STACK_INIT_SIZE ;
return OK ;
}//initstack
Status Push (SqStack &s , BiTree e )
{ if (s.top -s.base >=s.stacksize )//栈满,追加存储空间
{ s.base = (BiTree *) realloc (s.base,(s.stacksize +STACKINCREMENT)
*sizeof (BiTree ) ) ;
if (!s.base) exit ( OVERFLOW ) ;//存储分配失败
s.stacksize +=STACKINCREMENT ;
}
*s.top++=e ;
return OK ;
}//push
Status Pop (SqStack &s , BiTree *e)
{ if (s.top==s.base ) return 0 ;
*e =*--s.top ;
return OK ;
}// pop
Status createBiTree (BiTree T )
{ char ch ;
scanf ("%c", &ch ) ;
if (ch==' ') T=NULL ;
else {
if (!(T=(BiTNode *)malloc (sizeof (BiTNode )))) exit (0) ;
T->data = ch ;
createBiTree (T->lchild) ;
createBiTree (T->rchild) ;
}
return OK ;
}
Status printelement (char e )
{ printf ("%c",e) ;
return 1 ;
}
Status inorderrtaverse (BiTree T )
{ SqStack s ;
InitStack ( s ) ;
BiTree p;
p=T ;
while (p||!StackEmpty ( s ))
{
if (p) { Push (s, p); p=p->lchild ; }
else
{
Pop (s,&p) ;
if (!printelement(p->data)) return 0 ;
p=p->rchild ;
}/*else */
}// while
return OK ;
} // inordertraverse
main ()
{ BiTree T ;
createBiTree ( T );
inorderrtaverse ( T ) ;
}