nyoj 756 重建二叉树

重建二叉树主要是给你一颗二叉树的前序遍历的结果和中序遍历的结果或者后序遍历的结果或者中序遍历的结果，让你求出其中的后序遍历的结果或者前序遍历的结果，这里知道其中的两个就能求出第三个，但是知道的两个必须要有中序遍历，求这样的问题主要有两种方式，一种是把树建立起来，然后在遍历就行了，还有一种常用的方式是不用建树直接遍历。

第一种方式: 建立二叉树，然后进行遍历

 1  
 2 #include <stdio.h>
 3 #include <stdlib.h>
 4 #include <string.h>
 5 
 6 typedef struct Node{
 7     char data;
 8     struct Node *lchild, *rchild;
 9 }Node, *PNode;
10 
11 void buildTree(PNode *root, char *post, char *in, int len)/*root表示根节点， 
12 post表示后序遍历的结果，in表示中序遍历的结果，len表示当前子树的长度*/ 
13 {
14     if(len == 0)
15     {
16         *root = NULL;
17         return;
18     }
19     PNode node = (PNode)malloc(sizeof(Node));
20     node->data = post[len - 1];
21     node->lchild = node->rchild = NULL;
22     *root = node;
23     char *ptr = strchr(in, node->data);//找到根节点在中序遍历中的位置 
24     int leftlen = strlen(in) - strlen(ptr);//左子树的长度 
25     int rightlen = len - leftlen - 1;//右子树的长度 
26     buildTree(&(*root)->lchild, post, in, leftlen);//递归建左子树 
27     buildTree(&(*root)->rchild, post + leftlen, ptr + 1, rightlen);//递归建立右子树 
28 }
29 
30 void preOrderTraverse(PNode root)//前序遍历 
31 {
32     if(root == NULL)
33         return ;
34     printf("%c", root->data);
35     preOrderTraverse(root->lchild);
36     preOrderTraverse(root->rchild);
37 }
38 int main()
39 {
40     char post[100], in[100];
41     while(scanf("%s %s", post, in) != EOF)
42     {
43         PNode root = NULL;
44         buildTree(&root, post, in, strlen(in));
45         preOrderTraverse(root);
46         printf("
");
47     }
48     return 0;
49 }

第二种方式: 不建立二叉树，直接遍历

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <stdlib.h>
 4 //这里是不建树的方式，代码比较简洁 
 5 //post代表后序遍历的结果， in代表中序遍历的结果，ans存放前序遍历的结果， n是当前节点的个数 
 6 void Traverse(int n, char *post, char *in, char *ans)
 7 {
 8     if(n <= 0)
 9         return;
10     int p = strchr(in, post[n - 1]) - in;/*因为后序的最后一个是当前子树的根节点，
11     所以找到根节点在中序遍历中的位置 让它减去in获得它在中序遍历中的位置 */ 
12     
13     Traverse(p, post, in, ans + 1);/*递归它的左子树，左子树的长度为p, 
14     后序的开始位置为还是为post，中序的开始位置也是一样，把保存前序的数组加一 */ 
15     
16     Traverse(n - p - 1, post + p, in + p + 1, ans + p + 1);/*递归它的右子树，
17     其中后序的开始位置就是post+p，因为后续的根节点在最后，所以不用加一，但是中序的要加一，因为中间有个根节点要跳过它，ans当然是+p+1了*/ 
18     ans[0] = post[n - 1];//将当前子树的根节点赋值给ans， 
19 }
20 int main()
21 {
22     char str1[100], str2[100]; 
23     while(scanf("%s %s", str1, str2) != EOF)
24     {
25         char ans[100];
26         int len = strlen(str2);
27         Traverse(len, str1, str2, ans);
28         ans[len] = '';
29         puts(ans);
30     }
31     return 0;
32 }

下面这个是已知前序和中序求后续，建树的比较简单，下面是不建树的方法:

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <stdlib.h>
 4 //这里不建树， 直接将其后序保存到数组ans中
 5 void buildTree(int n, char *preOder, char *inOrder, char *ans)
 6 {
 7     if(n <= 0)
 8         return;
 9     int p = strchr(inOrder, preOder[0]) - inOrder;
10     buildTree(p, preOder + 1, inOrder, ans);
11     buildTree(n - p - 1, preOder + p + 1, inOrder + p + 1, ans + p);
12     ans[n - 1] = preOder[0];//由于是后序，所以n - 1, preOrder[0]为根节点
13 }
14 int main()
15 {
16     char str1[100], str2[100];
17     while(scanf("%s %s", str1, str2) != EOF)
18     {
19         char ans[100];
20         int len = strlen(str2);
21         buildTree(len, str1, str2, ans);
22         ans[len] = '';
23         puts(ans);
24     }
25     return 0;
26 }