#include<iostream> #define TREELEN  6 using namespace std;

struct Node {     char chValue; Node* pLeft; Node* pRight; };

void ReBuild(char* pPreOrder,char* pInOrder,int nTreeLen,Node** pRoot) //重建二叉树 {         if(pPreOrder==NULL || pInOrder==NULL)return ;      Node* pTemp=new Node();      pTemp->chValue=*pPreOrder;      pTemp->pLeft=NULL;      pTemp->pRight=NULL;   if(*pRoot==NULL)   {       *pRoot=pTemp;   }   if(nTreeLen==1)return;         char* pOrgInOrder=pInOrder;   char* pLeftEnd=pInOrder;   int nTempLen=0;   while(*pPreOrder!=*pLeftEnd)   {       if(pPreOrder==NULL || pLeftEnd==NULL)return;    nTempLen++;    if(nTempLen>nTreeLen)break;    pLeftEnd++;   }   int nLeftLen=0;//寻找左子树长度   nLeftLen=(int)(pLeftEnd-pOrgInOrder);   int nRightLen=0;//寻找右子树长度         nRightLen=nTreeLen-nLeftLen-1;   //重建左子树   if(nLeftLen>0)   {       ReBuild(pPreOrder+1,pInOrder,nLeftLen,&((*pRoot)->pLeft));   }   //重建右子树   if(nRightLen>0)   {       ReBuild(pPreOrder+nLeftLen+1,pInOrder+nLeftLen+1,nRightLen,&((*pRoot)->pRight));   } } void LastOrder(Node* pRoot) //后根遍历二叉树 {     if(pRoot==NULL)return; LastOrder(pRoot->pLeft); LastOrder(pRoot->pRight); cout<<pRoot->chValue<<" "; } int main() { char szPreOrder[TREELEN]={'a','b','d','c','e','f'}; char szInOrder[TREELEN]={'d','b','a','e','c','f'}; Node* pRoot=NULL; ReBuild(szPreOrder,szInOrder,TREELEN,&pRoot); LastOrder(pRoot); cout<<endl; system("pause"); return 0; }