题目： 将满二叉树转换为求和树
问题描述
给出满二叉树，编写算法将其转化为求和树
求和树：二叉树的求和树，是一颗同样结构的二叉树，其树中的每个结点将包含原始树中的左子树和右子树的和。
二叉树：
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域；
再就是求和函数注意题目要求