sicily_1935_重建二叉树解题报告

传送门：http://soj.sysu.edu.cn/1935

主要的思路是我已经得到先序遍历序列和中序遍历序列，如何将这个树分成三部分：根，左子树，右子树。
而区分的之后，先把根插入树中，再左子树和右子树进行递归，直到所有元素都已经插入到树中即可。

// Copyright (c) Junjie_Huang@SYSU(SNO:13331087). All Rgights Reserved.// 1000_sicily_1935.cpp: http://soj.sysu.edu.cn/1935#include #include #include #include #include #define MAX_SIZE 1000#define STRING_SIZE 50using std::cin;using std::string;using std::queue;// Pre:// @|tree[]|: the array needs to traverse// @|pre|: the string printed by traversing a tree in pre-order// @|mid|: the string printed by traversing a tree in mid-order// @|index|: the index of parent node in the |tree[]|.// Post: None// Usage: finds the root node of a tree and sperates the |mid| with root so we// can point out the left sub-tree and the right one. Recurses the function// until all the elements are insert to the |tree|void rebuild(char tree[], string pre, string mid, int index = 0) {  // records the left child |left| and the right child |right|  // of the parent node  int left = 2 * index + 1, right = 2 * index + 2;  if (pre.length()) {  // Recursions end when all the elements are inserted.    tree[index] = pre[0];  // insert the data of the parent node    // finds the position of root node from |mid|    int temp = mid.find(pre[0]);    // Recursions. Seperates the tree to its left sub-tree and the right one.    // and the |left| and |right| will be the new parent nodes.    rebuild(tree, pre.substr(1, temp), mid.substr(0, temp), left);    rebuild(tree, pre.substr(temp + 1), mid.substr(temp + 1), right);  }}// Pre:// @|tree[]|: the binary tree we want to traverse with BFS. Here because// we use an array to store the data, so we just need to traverse the array// by the index.// Post: Nodevoid BFS_visit(char tree[]) {  for (int i = 0; i < MAX_SIZE; i++) {    if (tree[i]) printf("%c", tree[i]);  }  printf("\n");}int main() {  int n = 0;  char tree[MAX_SIZE + 10];  for (scanf("%d", &n); n; n--) {    memset(tree, 0, sizeof(tree));    string pre_order, mid_order;    cin >> pre_order >> mid_order;    rebuild(tree, pre_order, mid_order);    BFS_visit(tree);  }  return 0;}

以上代码使用的树是以数组形式储存的，整棵树的树根为tree[0]，节点i的左子节点为2i+1， 右子节点为2i+2

还用一种用链表建树的方法，请参考：http://acmer.diandian.com/post/2011-07-15/2921418

sicily_1935