#include<stdio.h>
#include<malloc.h>
#include<string.h>

struct node
{
	char data;
	int c;
	node *lc,*rc,*pre;//左孩子为子女,右孩子为兄弟姐妹,pre父亲 
};

struct sqelist 
{
	char data;
	int n;
	sqelist *next;
};
sqelist *lead;
node *creattree(char *str,int n,int m)//建树 
{
	node *newtree;
	newtree=NULL;
	if(n<strlen(str)&&str[n]!='0')
	{
		newtree=(node *)malloc(sizeof(node));
		newtree->data=str[n];
		newtree->c=m;
		newtree->lc=creattree(str,2*n,m+1);
		newtree->rc=creattree(str,2*n+1,m+1);
	}
	return newtree;
}

int s=0;

int creatlead(char d,int m)
{
	sqelist *newlead,*p;
	if(s<m)
	{
		s=m;
	}
	newlead=(sqelist *)malloc(sizeof(sqelist));
	newlead->data=d;
	newlead->n=m;
	newlead->next=NULL;
	if(lead==NULL)
	{
		lead=newlead;
	}
	else
	{
		p=lead;
		while(p->next!=NULL)
		{
			p=p->next;
		}
		p->next=newlead;
	}
}
int xpre(node *head)
{
	if(head!=NULL)
	{
		printf("%c",head->data);
		creatlead(head->data,head->c);
		xpre(head->lc);
		xpre(head->rc);
	}
}

int zpre(node *head)
{
	if(head!=NULL)
	{
		zpre(head->lc);
		printf("%c",head->data);
		zpre(head->rc);
	}
}

int hpre(node *head) 
{
	if(head!=NULL)
	{
		hpre(head->lc);
		hpre(head->rc);
		printf("%c",head->data);
	}
}
int cpre(sqelist *lead)
{
	int i;
	sqelist *p;
	for(i=1;i<=s;i++)
	{
		p=lead;
		while(p!=NULL)
		{
			if(p->n==i)
			{
				printf("%c",p->data);
			}
			p=p->next;
		}
		
	}
}

int main()
{
	node *head;
	char str[100]="0ab0cd0000ef000000000g";
	head=creattree(str,1,1);
	printf("\n******二叉树遍历*******\n");
	printf("先序:");
	xpre(head);
	printf("\n");
	printf("中序:");
	zpre(head);
	printf("\n");
	printf("后序:");
	hpre(head); 
	printf("\n");
	printf("层序:");
	cpre(lead);
	printf("\n");
}