编程之美--根据遍历结果重建二叉树
学过数据结构和算法的人都能很快的写出二叉树的三种遍历次序。
那么如果已经知道了遍历的结果，能不能把一颗二叉树重新构造出来呢？
给定一颗二叉树，假设每个节点都用唯一的字符来表示，具体结构如下：
struct Node{ struct Node* pLeft; struct Node* pRight; char value;};
假设已经有了前序和中序遍历结果，希望通过一个算法重建这个二叉树。
分析：先回忆一下前序和中序遍历的定义。
前序遍历：先访问当前结点，然后以前序遍历顺序访问左子树和右子树。
中序遍历：以中序遍历顺序访问左子树，接着访问当前节点，然后以中序遍历顺序访问右子树。
根据定义，可以发现如下规律：
前序遍历的每一个节点，都是当前子树的根节点。同时，以对应的结点为边界，就会把中序遍历结果
分为左子树和右子树。
前序：a b d c e f a是根节点
中序：d b a e c f a是根节点，把字符串分成左右两个子树
实现：
/**///定义树的长度#define TREELEN 6#include<iostream>using namespace std;struct Node{ struct Node* pLeft; struct Node* pRight; char value;};void Rebuild(char *pPreOrder,//前序遍历结果 char *pInorder,//中序遍历结果 int nTreeLen,//树的长度 Node **pRoot)//根节点{ //检查边界条件 if(pPreOrder==NULL ||pInorder==NULL) { return ; } //获得前序遍历的第一个结点 Node *pt=new Node ; pt->value=*pPreOrder; pt->pLeft=NULL; pt->pRight=NULL; //如果根节点为空，将该节点设置为根节点，首次会调用 if(*pRoot==NULL) { *pRoot=pt; } //如果深度为1，那么已经是叶节点了 if(nTreeLen==1) { return; } //在中序遍历中寻找左子树 char *pOrgInOrder=pInorder; char *pLeftEnd=pInorder; int ntemp=0; //找到左子树的结尾 while(*pPreOrder!=*pLeftEnd) { if(pPreOrder==NULL||pLeftEnd==NULL) { return; } ntemp++; if(ntemp>nTreeLen) { return; } 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)); }}int main(){ char PreOrder[]={'a','b','d','c','e','f'}; char InOrder[]={'d','b','a','e','c','f'}; Node *root=NULL; Rebuild(PreOrder,InOrder,TREELEN,&root);}