#include <iostream>#include <string>using namespace std;/*给定前序，中序，重建树结构例如假定：前序：adbcef中序：dbaecf后序：dbefca*/struct NODE{    NODE *pLeft;    NODE *pRight;    char chValue;};//递归构建树NODE* Rebuild(char *pPreOrderStart,char* pPreOrderEnd,char* pInOrderStart,char *pInOrderEnd){    NODE *root = (NODE*)malloc(sizeof(NODE));    root->chValue = http://www.mamicode.com/pPreOrderStart[0];    root->pLeft = root->pRight = NULL;    //如果只剩下最后一个节点返回他    if (pPreOrderStart == pPreOrderEnd && pInOrderStart == pInOrderEnd)    {        return root;    }    char* rootInOrder = pInOrderStart;    while(rootInOrder != pInOrderEnd && *rootInOrder != root->chValue)rootInOrder++;    if(rootInOrder == pInOrderEnd && root->chValue != root->chValue)return NULL;    int leftLen = rootInOrder - pInOrderStart;    char* leftPreOrderEnd = pPreOrderStart+leftLen;    if (leftLen > 0)    {        root->pLeft = Rebuild(pPreOrderStart+1,leftPreOrderEnd,pInOrderStart,rootInOrder-1);    }    if (leftLen < pPreOrderEnd - pPreOrderStart)    {        root->pRight = Rebuild(leftPreOrderEnd+1,pPreOrderEnd,rootInOrder+1,pInOrderEnd);    }    return root;}//重建树void RebuildTree(char *pPreOrder,char *pInOrder,int nTreeLen,NODE** pRoot){    if(nTreeLen == 0 || pPreOrder == NULL || pInOrder == NULL)return;    //构建树    *pRoot = Rebuild(pPreOrder,pPreOrder+nTreeLen-1,pInOrder,pInOrder+nTreeLen-1);}//先根遍历void preRootView(NODE* root){    cout<<root->chValue;    if (root->pLeft != NULL )    {        preRootView(root->pLeft);    }    if (root->pRight != NULL )    {        preRootView(root->pRight);    }}//中根遍历void inRootView(NODE* root){    if (root->pLeft != NULL )    {        inRootView(root->pLeft);    }    cout<<root->chValue;    if (root->pRight != NULL )    {        inRootView(root->pRight);    }}//后根遍历void afRootView(NODE* root){    if (root->pLeft != NULL )    {        afRootView(root->pLeft);    }    if (root->pRight != NULL )    {        afRootView(root->pRight);    }    cout<<root->chValue;}int main(int argc, char **argv){    char *preOrder = "abdcef";    char *inOrder = "dbaecf";    NODE *pRoot = (NODE*)malloc(sizeof(NODE));    int len = strlen(preOrder);    pRoot->chValue = http://www.mamicode.com/*preOrder;    RebuildTree(preOrder,inOrder,len,&pRoot);    cout<<"先根遍历：";    preRootView(pRoot);    cout<<endl;    cout<<"中根遍历：";    inRootView(pRoot);    cout<<endl;    cout<<"后根遍历：";        afRootView(pRoot);    cout<<endl;    return 0;}