同PKU2255 Tree Recovery可以说是一道题目了
本题题目描述：链接
仿照PKU2255写的代码，一不小心给过了。
先由前序 中序建树，再后序遍历 62MS 1360K（内存有点大啊）
代码 #include < stdio.h > #include < stdlib.h > struct node{ int value; struct node * left, * right;}; int index,n; void make_tree( int * pre, int plen, int * in , int ilen, struct node * root){ int flag = 0 ,flag1 = 0 ; int i; struct node * ptr1, * ptr2; for (i = 0 ; in [i] != pre[ 0 ];i ++ ); // 找到根节点在中序中的位置 if (i != 0 ) // 判断左子树是否存在 flag = 1 ; if (i != plen - 1 ) // 判断右子树是否存在 flag1 = 1 ; if (flag) // 构建该根的左子树 { ptr1 = ( struct node * )malloc( sizeof ( struct node)); ptr1 -> value = pre[ 1 ]; root -> left = ptr1; // 该根与左子树建立联系 if (flag1 == 0 ) root -> right = NULL; make_tree(pre + 1 ,i, in ,i,ptr1); // 已知左子树的前序和中序，构建左子树 } if (flag1) // 构建该根的右子树 { ptr2 = ( struct node * )malloc( sizeof ( struct node)); ptr2 -> value = pre[i + 1 ]; root -> right = ptr2; // 该根与右子树建立联系 if (flag == 0 ) root -> left = NULL; make_tree(pre + i + 1 ,plen - i - 1 , in + i + 1 ,ilen - i - 1 ,ptr2); // 根据它的前序和中序，构建右子树 } if (plen == 1 ) root -> left = root -> right = NULL;} void visit( struct node * p) // 后序遍历树 { if (p == NULL) return ; visit(p -> left); visit(p -> right); if (index != n) printf( " %d " ,p -> value); else printf( " %d\n " ,p -> value); index ++ ;} #define N 1002 int main(){ int pre[N], in [N],i; while (scanf( " %d " , & n) != EOF) { for (i = 0 ;i < n;i ++ ) scanf( " %d " , & pre[i]); for (i = 0 ;i < n;i ++ ) scanf( " %d " , & in [i]); struct node * root; root = ( struct node * )malloc( sizeof ( struct node)); root -> value = pre[ 0 ]; make_tree(pre,n, in ,n,root); index = 1 ; visit(root); } return 0 ;}见了队友William用深搜建树，虽然知道和上述方法是同一个道理，运用递归思想，既然写了也贴一下，做对比78MS 1364K
要理解啊，请教了William我算理解了其真谛了吧 ^_^
代码 #include < stdio.h > #include < stdlib.h > typedef struct node{ int data; int index; struct node * left, * right;}bitree, * Tree; int n,pre[ 1005 ],mid[ 1005 ]; void dfs(Tree & root, int index){ if (root == NULL) { root = (Tree)malloc( sizeof (bitree)); root -> data = mid[index]; root -> index = index; root -> left = NULL; root -> right = NULL; } else { if (index < root -> index) dfs(root -> left,index); else dfs(root -> right,index); }} void creatbitree(Tree & root){ int i,j,index; root = (Tree)malloc( sizeof (bitree)); for (i = 1 ;i <= n;i ++ ) { if (mid[i] == pre[ 1 ]) { root -> data = pre[ 1 ]; root -> index = i; root -> left = NULL; root -> right = NULL; break ; } } index = i; for (i = 2 ;i <= n;i ++ ) { for (j = 1 ;j <= n;j ++ ) if (mid[j] == pre[i]) { if (j < index) dfs(root -> left,j); else dfs(root -> right,j); break ; } }} void post(Tree & root, int x){ if (root == NULL) return ; post(root -> left,x + 1 ); post(root -> right,x + 1 ); if (x == 0 ) printf( " %d " ,root -> data); else printf( " %d " ,root -> data);} int main(){ int i; while (scanf( " %d " , & n) != EOF) { Tree root; for (i = 1 ;i <= n;i ++ ) scanf( " %d " , & pre[i]); for (i = 1 ;i <= n;i ++ ) scanf( " %d " , & mid[i]); creatbitree(root); post(root, 0 ); printf( " \n " ); } return 0 ;}下面贴一个很牛的代码（至少和前两个比），46MS 160K,而且37lines实现的，受教了！
递归的时候模拟一个栈，把树按根，右子树，左子树存入，再LIFO输出
代码 #include < stdio.h > #define M 1001 int stack[M]; int top; void Create( int * pre, int plen, int * in , int ilen){ int index; if (plen) { stack[top ++ ] = pre[ 0 ]; for (index = 0 ; in [index] != pre[ 0 ];index ++ ); Create(pre + index + 1 ,plen - index - 1 , in + index + 1 ,ilen - index - 1 ); Create(pre + 1 ,index, in ,index); }} int main(){ int n,i; int pre[M], in [M]; while (scanf( " %d " , & n) !=- 1 ){ for (i = 0 ;i < n;i ++ ) scanf( " %d " ,pre + i); for (i = 0 ;i < n;i ++ ) scanf( " %d " , in + i); top = 0 ; Create(pre,n, in ,n); while (top -- ) { if (top == 0 ){ printf( " %d\n " ,stack[top]); break ; } printf( " %d " ,stack[top]); } } return 0 ;}
转载于:https://www.cnblogs.com/DreamUp/archive/2010/07/20/1781191.html
相关资源：垃圾分类数据集及代码