谢谢
想要输入:1 2 4 0 5 0 3 6 0
结果:1 2 4 5 3 6
#include"stdio.h"
#include"malloc.h"
#define MAX_NODE 100
#define EXPANSIONFLAG 0
typedef struct node
{
int data;
struct node *Lchild;
struct node *Rchild;
}BiTree;
BiTree *creat_preorder();
void PreorderTraverse( BiTree *T);
void InorderTraverse( BiTree *t );
int main()
{
BiTree *T;
BiTree *creat_preorder(T);
PreorderTraverse(T);
return 0;
}
BiTree *creat_preorder()
{
BiTree *T, *s, *p, *stack[MAX_NODE];
int x;
int top = 0;
int flag = 0;
scanf( "%d",&x );
if( x == EXPANSIONFLAG )
{
T = NULL;
return T;
}
T = ( struct node * )malloc( sizeof(BiTree) );
T->data = x;
T->Lchild = NULL;
T->Rchild = NULL;
p = T;
while( 1 )
{
scanf( "%d",&x );
if( x != EXPANSIONFLAG )
{
s = ( struct node * )malloc( sizeof(BiTree) );
s->data = x;
s->Lchild = NULL;
s->Rchild = NULL;
if( flag == 1 )
{
p->Rchild = s;
flag = 0;
}
else
{
p->Lchild = s;
stack[ top++ ] = p;
}
p = s;
}
else
{
scanf( "%d",&x );
if( x != EXPANSIONFLAG )
{
s = ( struct node * )malloc( sizeof(BiTree) );
s->data = x;
s->Lchild = NULL;
s->Rchild = NULL;
p->Rchild = s;
p = s;
}
else
{
if( top > 0 )
{
p = stack[ --top ];
flag = 1;
}
else
break;
}
}
}
return( T );
}
void PreorderTraverse( BiTree *T)
{
BiTree *Stack[MAX_NODE] , *p, *q;
int top=0 ;
p = T;
if( T==NULL )
{
printf( "Binary Tree is Empty!\n");
return;
}
while (p!=NULL)
{
printf( "%d,", p->data );
q = p->Rchild;
if( q != NULL )
Stack[++top] = q;
p = p->Lchild;
if( p == NULL && top > 0 )
p = Stack[top--];
}
}