dgebfca
abcdefg
linux
xnuli

【code】

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 #include<string.h>
 4 typedef struct tree
 5 {
 6     char data;
 7     struct tree *l,*r;
 8 }tree;
 9 tree *creat(char *pre,char *in,int len)
10 {
11     int k;
12     if(len<=0)
13         return NULL;
14     tree*head;
15     head=(tree*)malloc(sizeof(tree));
16     head->data=*pre;
17     char *p;
18     for(p=in;p!=NULL;p++) 
19         if(*p==*pre)
20             break;// 在中序遍历的序列中得到与先序相同的节点 
21     k=p-in;
22     head->l=creat(pre+1,in,k);//递归得到左子树 
23     head->r=creat(pre+k+1,p+1,len-k-1);//得到右子树 
24     return head;
25 }
26 void postorder(tree*t)
27 {
28     if(t)
29     {
30         postorder(t->l);
31         postorder(t->r);
32         printf("%c",t->data);
33     }
34 }
35 void lorder(tree*t)
36 {
37     int front=0,rear=1;
38     tree*q[100];
39     q[0]=t;
40     while(front<rear)
41     {
42         if(q[front])
43         {
44             printf("%c",q[front]->data);
45             q[rear++]=q[front]->l;
46             q[rear++]=q[front]->r;
47             front++;
48         }
49         else
50             front++;
51     }
52 }
53 int main()
54 {
55     int t,len;
56     char pre[51],in[51];//存储先序和中序遍历的序列 
57     tree*h;
58     h=(tree*)malloc(sizeof(tree));
59     scanf("%d%*c",&t);
60     while(t--)
61     {
62         scanf("%s%s",pre,in);
63         len=strlen(pre);
64         h=creat(pre,in,len);
65         postorder(h);
66         printf("\n");
67         lorder(h);
68         printf("\n");
69     }
70     return 0;
71 }

1、从先序遍历中读入根节点
2、从中序遍历中找到与根节点相等的元素，将中序序列分成两个部分，左边的为二叉树的
左子树，右边为二叉树的右子树；
3、递归调用得到根节点的左右子树

层次遍历是看的别人的代码。。。

myblog：http://www.bearac.com

优质内容筛选与推荐>>
1、遥仰凰华重装系统后无法运行解决方法
2、3 Useful BookmarkLets for Debugging
3、K3Cloud 简单账表双表头解决方案以及35列解决方案
4、二分查找
5、Spring报错汇总笔记