树的存储与遍历.doc

# include# include# include# define NULL 0# define LEN sizeof(struct node)struct nodestruct node *child;char data;struct node *brother;/树的建立函数struct node *setuptree(char s1)struct node *stack1100;/栈1char stack2100;/栈2struct node *p,*root;int i=0,top1=0,top2=0,length;root=p=(struct node *)malloc(LEN);p-child=NULL;p-data=0;p-brother=NULL;/初始化结构体p-data=s10;stack1top1=p;stack2top2=s10;/进栈length=strlen(s1);while(ichild=NULL;p-data=0;p-brother=NULL;/初始化结构体stack2top2=s1i;else if(s1i=,)top2+;p=(struct node *)malloc(LEN);p-child=NULL;p-data=0;p-brother=NULL;/初始化结构体stack2top2=s1i;else if(s1i=)while(stack2top2!=()top2-;top2-;while(stack1top1-data)!=stack2top2)top1-;elsep-data=s1i;if(stack2top2=()stack1top1-child=p;top1=top1+1;stack1top1=p;top2=top2+1;stack2top2=s1i;else if(stack2top2=,)stack1top1-brother=p;stack1top1=p;top2=top2-1;stack2top2=s1i;i+;return(root);/树的先根遍历函数void firstroot(struct node *root)struct node *stack1300;/栈1struct node *p;int top1=0;p=root;printf(%c ,p-data);stack1top1=p;p=p-child;while(top1=0|p!=NULL)while(p!=NULL)top1+;printf(%c ,p-data);stack1top1=p;p=p-child;p=stack1top1-brother;top1-;/树的层次遍历函数void layer(struct node *root)struct node *queue1300=NULL;/栈1struct node *p;int top1=0,head=0;p=root;queue1head=p;while(queue1head!=NULL|p!=NULL)while(p!=NULL)if(p!=root)top1+;printf(%c ,p-data);queue1top1=p;p=p-brother; p=queue1head-child; head+;/主函数void main()char s1100;struct node *root;printf(请输入所要建立的树：);gets(s1);root=setuptree(s1);printf(实验结果如下：n);