#include <iostream> using namespace std; struct Node { Node() : lchild(0), rchild(0){ } Node(char v):val(v), lchild(0), rchild(0){ } char val; Node *lchild, *rchild; }; void Rebuild(char *pPreOrder, char * pInOder, int len, Node **pRoot) { if(!pPreOrder || !pInOder) return; if((*pRoot) == NULL && len >= 1) { *pRoot = new Node(*pPreOrder); } if(len <= 1) return; char *s = pInOder, *e = pInOder + len - 1; while(s <= e) { if(*s == *pPreOrder) break; s++; } if(s <= e) { Rebuild(pPreOrder+1, pInOder, s - pInOder, &((*pRoot)->lchild)); Rebuild(pPreOrder + (s - pInOder) + 1, s+1, e - s, &((*pRoot)->rchild)); } } void print(Node *root) { if(!root) return; cout << root->val << " "; print(root->lchild); print(root->rchild); } int main(void) { char pPreOder[] = "abdcef"; char pInOder[] = "dbaecf"; int len = strlen(pInOder); Node *root = NULL; Rebuild(pPreOder, pInOder, len, &root); print(root); return 0; }