///
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "ConstructTree.h"
/
/*
InPreToTree(): 由前序遍历序列和中序遍历序列构造二叉树
前序序列为pa[p1:p2]
中序序列为ia[i1:i2]
返回所构造的二叉树的根指针
*/
TNode* InPreToTree(char *pa, char *ia, int p1, int p2, int i1, int i2)
{
/*请在BEGIN和END之间实现你的代码*/
/*****BEGIN*****/
if(p1>p2){
return NULL;
}
TNode* root=new TNode;
root->data=pa[p1];//将前序数组中第一个元素赋给data，前序数组第一个值都是根节点。
root->left=NULL;
root->right=NULL;
int i=0;
while(ia[i]!=pa[p1]){
i++;
}//查找根节点在中序数组中的位置。
//递归，每次缩小范围，将树一次一次细分。
int llen=i-i1;//存储左子树长度
root->left=InPreToTree(pa,ia,p1+1,p1+llen,i1,i-1);//每个根节点左右子树依次递推下去，双亲和子树的递推方法都是一样的。
int rlen=i2-i;//存储右子树长度，两个分开存储会更好
root->right=InPreToTree(pa,ia,p2-rlen+1,p2,i+1,i2);
return root;
/******END******/
/*请不要修改[BEGIN,END]区域外的代码*/
}
void PrintPostTravel(TNode* t)
{
if(t==NULL) return;
if(t->left) PrintPostTravel(t->left);
if(t->right) PrintPostTravel(t->right);
printf("%c", t->data);
}
void DeleteTree(TNode* t)
{
if(t==NULL) return;
if(t->left) DeleteTree(t->left);
if(t->right) DeleteTree(t->right);
delete t;
}
