二叉树后序遍历和层次遍历

题目：http://acm.sdut.edu.cn/sdutoj/showproblem.php?pid=2137&cid=1184

有关博客：http://blog.sina.com.cn/s/blog_7dc67d520100t26n.html

http://www.cnblogs.com/shangyu/archive/2012/03/03/2378422.html

以前做过，现在做还是不会……

 1 #include<iostream>
 2  #include<stdio.h>
 3  #include<string.h>
 4  #include<stdlib.h>
 5  #include<queue>
 6 
 7  using namespace std;
 8 
 9  struct tree
10  {
11      char data;
12      struct tree *l,*r;
13  };

14 
15  struct tree* build(char *s1,char *s2,int n)
16  {
17      int p;
18      struct tree *t;
19      if(n<=0)  return NULL;
20 
21      t=(struct tree*)malloc(sizeof(struct tree));
22      t->data=s1[0];//先序的第一个节点是树根节点
23      p=strchr(s2,s1[0])-s2;//strchar函数，查找根节点在中序遍历中的位置，p代表左子树中节点的个数
24      t->l=build(s1+1,s2,p);//构建左子树
25      t->r=build(s1+p+1,s2+p+1,n-p-1);//同理 构建右子树
26 
27      return t;
28  };
29 
30  void postorder(struct tree *p)//后序遍历
31  {
32      if(p)
33      {
34          postorder(p->l);
35          postorder(p->r);
36          printf("%c",p->data);
37      }
38  };
39 
40  void levelorder(struct tree *t)//层次遍历
41  {
42      queue<tree*>q;
43      q.push(t);
44      while(!q.empty())
45      {
46          if(q.front())
47          {
48              printf("%c",(q.front())->data);
49              q.push(q.front()->l);
50              q.push(q.front()->r);
51              q.pop();
52          }
53          else
54              q.pop();
55      }
56  };
57 
58  int main()
59  {
60      int n;
61      char s1[100],s2[100];
62      struct tree *root;
63      scanf("%d%*c",&n);
64      while(n--)
65      {
66          gets(s1);
67          gets(s2);
68          root=build(s1,s2,strlen(s1));
69 
70          postorder(root);
71          printf("
");
72          levelorder(root);
73          printf("
");
74      }
75  }