http://poj.org/problem?id=2255
前序遍历的第一个字符为树的根节点;
找到根节点字符在中序遍历中的位置,则该位置的左边的字符串为左子树的中序遍历串,右边为右子树中序遍历串;
根节点在中序遍历首位,无左子树
根节点在中序遍历末位,无右子树
#include <iostream> #include <cstdio> #include <cstring> using namespace std; const int maxn = 30; char pre[maxn], in[maxn]; struct Node { Node *l, *r; char val; }*root; int Find(char ch, char *p) { int len = strlen(p); for (int i = 0; i < len; i++) if (ch == p[i]) return i; return -1; } void Copy(int l, int r, char *p, char *t) { int i, j; for (i = l, j = 0; i <= r; i++, j++) t[j] = p[i]; t[j] = '\0'; } void build(char *preStr, char *inStr, Node *rt) { //cout << preStr << " " << inStr << endl; int len = strlen(preStr); if (len <= 1) { //长度为1,到达叶子节点 rt->l = rt->r = NULL; return; } int x = Find(preStr[0], inStr); //在中序遍历中找根的位置 if (x > 0 && x < len) { //判断是否存在左子树 char *lpre = new char [x+1]; char *lin = new char [x+1]; Copy(1, x, preStr, lpre);//求左子树前序遍历串 Copy(0, x-1, inStr, lin);//求左子树中序遍历串 Node *lrt = new Node; lrt->val = lpre[0]; rt->l = lrt; build(lpre, lin, lrt); } else rt->l = NULL;//无左子树 if (x >= 0 && x < len-1) {//判断是否存在右子树 char *rpre = new char [len-x]; char *rin = new char [len-x]; Copy(x+1, len-1, preStr, rpre); Copy(x+1, len-1, inStr, rin); Node *rrt = new Node; rrt->val = rpre[0]; rt->r = rrt; build(rpre, rin, rrt); } else rt->r = NULL;//不存在右子树 } void output(Node *rt) { if (rt == NULL) return; output(rt->l); output(rt->r); putchar(rt->val); } int main() { while (scanf ("%s", pre) != EOF) { scanf ("%s", in); root = new Node; root->l = root->r = NULL; root->val = pre[0]; build(pre, in, root); output(root); putchar('\n'); } return 0; }