通过简单例子可以分析出,先由前序找出当前根,再通过中序找出左右子树序列,然后递归输出左右子树,最后输出根
#include "stdafx.h" #include <iostream> using namespace std; void GetEnOrder(char* startPreOrder,char* endPreOrder,char* startInOrder,char* endInOrder); void GetAll(char* preOrder,char* inOrder,int lenght) { if (preOrder==NULL||inOrder==NULL||lenght<=0) { return; } GetEnOrder(preOrder,preOrder+lenght-1,inOrder,inOrder+lenght-1); } void GetEnOrder(char* startPreOrder,char* endPreOrder,char* startInOrder,char* endInOrder) { if (startPreOrder<=endPreOrder) { char root=*startPreOrder; char* rootInOrder=startInOrder; while(rootInOrder<=endInOrder&&*rootInOrder!=root) { rootInOrder++; } if (rootInOrder==endInOrder+1) { throw std::exception("序列错误!"); } int leftLen=rootInOrder-startInOrder; int rightLen=endInOrder-rootInOrder; if (leftLen>0) { GetEnOrder(startPreOrder+1,startPreOrder+leftLen,startInOrder,rootInOrder-1); } if(rightLen>0) { GetEnOrder(startPreOrder+leftLen+1,endPreOrder,rootInOrder+1,endInOrder); } cout<<root; } } int _tmain(int argc, _TCHAR* argv[]) { char preOrder[]={'A','B','D','C'}; char inOrder[]={'B','D','A','C'}; GetAll(preOrder,inOrder,4); return 0; }