319将满二叉树转化为求和树

题目： 将满二叉树转换为求和树

问题描述

给出满二叉树，编写算法将其转化为求和树

求和树：二叉树的求和树，是一颗同样结构的二叉树，其树中的每个结点将包含原始树中的左子树和右子树的和。

二叉树：

10

/     \

-2       6

/    \    /  \

8      -4  7    5

求和树：

20(4-2+12+6)

/      \

4(8-4)     12(7+5)

/   \      /   \

0      0    0    0

二叉树给出先序和中序遍历序列，求和树要求输出中序遍历序列；

所有处理数据不会大于int类型范围。

输入格式

输入共3行：第一行为满二叉树中结点个数n（n<1024）；第二行为n个整数，表示二叉树的先序遍历序列；第三行也有n个整数，表示二叉树的中序遍历序列。整数间以空格分割。

输出格式

输出1行整数，表示求和树的中序遍历序列。整数间以空格分割。

样例输入

    7

10 -2 8 -4 6 7 5

8 -2 -4 10 7 6 5

样例输出

0 4 0 20 0 12 0

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<stdlib.h>
 4 typedef struct treenode{
 5     int data;
 6     struct treenode *lchild;
 7     struct treenode *rchild;
 8     int sum=0;
 9 }treenode,*tree;
10 
11 tree createTree(int *preorder,int *inorder,int n);
12 void postorderTraverse(tree t);
13 void sumarize(tree t);
14 int main()
15 {
16     int n;//the number of the vertex
17     scanf("%d",&n);
18     
19     int preorder[1024],inorder[1024];
20     int i,j,k;
21     for(i=0;i<n;i++)
22     {
23         scanf("%d",&preorder[i]);
24     }
25     for(j=0;j<n;j++)
26     {
27         scanf("%d",&inorder[j]);
28     }
29     
30     tree t,sumt;
31     t=createTree(preorder,inorder,n);
32     sumarize(t);
33     postorderTraverse(t);
34     return 0;
35 }
36 tree createTree(int *pre,int *in,int n)
37 {
38     int k;
39     int *p;
40     if(n<=0) return NULL;
41     
42     treenode *b=(treenode*)malloc(sizeof(treenode));
43     b->data=*pre;
44     for(p=in;p<in+n;p++)
45     {
46         if(*p==*pre) break;
47     }
48     
49     k=p-in;
50     b->lchild=createTree(pre+1,in,k);
51     b->rchild=createTree(pre+k+1,p+1,n-k-1);
52     return b;
53     
54 }
55 void postorderTraverse(tree t)
56 {
57     /*if(!t) printf("EMPTY\n");
58     else
59     {
60         postorderTraverse(t->lchild);
61         postorderTraverse(t->rchild);
62         printf("%d ", t->data);
63     }*/
64     if(t)
65     {
66         postorderTraverse(t->lchild);
67         printf("%d ", t->sum);
68         postorderTraverse(t->rchild);
69         
70     }
71 }
72 void sumarize(tree t)
73 {
74     if(t->lchild&&t->rchild) 
75     {
76         if(t->rchild) sumarize(t->rchild);
77         if(t->lchild) sumarize(t->lchild);
78         t->sum=t->lchild->data+t->rchild->data+
79                      t->lchild->sum+t->rchild->sum;
80     }
81     else t->sum=0;
82 }

core：

给treenode增加一个sum域；

再就是求和函数注意题目要求