学步园

先序遍历中第一个结点必然是根结点，利用该结点在中序遍历中的位置，将树分为左子树和右子树，然后递归重建左子树和右子树，代码如下

#include <iostream>
using namespace std;

struct Node {
  char value;
  Node* left;
  Node* right;
  Node() { };
  Node(char c, Node* l = NULL, Node* r = NULL): value(c), left(l), right(r) { }
};

Node* build(int n, char* s1, char* s2){
  //s1表示的是先序遍历,s2表示的是中序遍历,s3表示的是后续遍历
  if (n <= 0)
    return NULL;
  // 分别求左右子树的大小
  int leftn = strchr(s2, s1[0]) - s2;
  int rightn = n - leftn - 1; //到这里为止，起始可以加两条二层的for循环判断是否可以重建子树，原理是左(右)子树的所有结点在先序和后序中相同，次序可以不一
  //重建左子树
  Node* root = new Node(s1[0]);
  root->left = build(leftn, s1+1, s2);
  //重建右子树
  root->right = build(rightn, s1 + 1 + leftn, s2 + 1 + leftn);
  return root;
}

//用前序遍历测试二叉树是否重新创建
void PreOrder (Node* root) {
  if (root) {
    printf("%c", root->value);
    PreOrder(root->left);
    PreOrder(root->right);
  }
}

//用中序遍历测试二叉树是否重新创建
void InOrder (Node* root) {
  if (root) {
    InOrder(root->left);
    printf("%c", root->value);
    InOrder(root->right);
  }
}

//用后续遍历测试二叉树是否重新创建
void PostOrder (Node* root) {
  if (root) {
    PostOrder(root->left);
    PostOrder(root->right);
    printf("%c", root->value);
  }
}
int main() {
  char s1[100], s2[100];
  while (scanf("%s%s", s1, s2) == 2) {
    int n = strlen(s1);
    Node* root = build(n, s1, s2);
    printf("前序遍历序列为: ");
    PreOrder(root);
    printf("\n");

    printf("中序遍历序列为: ");
    InOrder(root);
    printf("\n");

    printf("后序遍历序列为: ");
    PostOrder(root);
    printf("\n");
  }
  return 0;
}