头歌实训数据结构与算法-二叉树及其应用（第7关：由前序和中序遍历序列构造二叉树）

任务描述

本关任务要求采用前序遍历序列和中序遍历序列构造二叉树。

相关知识

给定一棵二叉树的前序遍历序列和中序遍历序列可以构造出这棵二叉树。例如前序序列是ABDECFG，中序序列是DBEAFCG，那么这颗二叉树的结构如图1所示。

树结点结构定义为：

struct BTNode{
        char data;
        struct BTNode* lchild;
        struct BTNode* rchild;
};

编程要求

本关任务是实现ConstructTree.cpp里的TNode* InPreToTree(char *pa, char *ia, int p1, int p2, int i1, int i2)。
该函数的功能是由前序遍历序列和中序遍历序列构造二叉树
前序序列为pa[p1:p2]
中序序列为ia[i1:i2]
返回所构造的二叉树的根指针
提示1：这是一个递归函数，在主程序中调用：
InPreToTree(pa,ia,0,n-1,0,n-1)，其中n是序列长度。
提示2：由于在DeleteTree()中是使用delete删除一个树结点，所以在InPreToTree()需要使用new来申请结点空间。

//ConstructTree.cpp
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include binary_tree.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 **********/
    
    /********* end ************/
}
void PrintPostTravel(BTNode* t)
{
    if(t==NULL) return;
    if(t->lchild) PrintPostTravel(t->lchild);
    if(t->rchild) PrintPostTravel(t->rchild);
    printf("%c", t->data);
}
void DeleteTree(BTNode* t)
{
    if(t==NULL) return;
    if(t->lchild) DeleteTree(t->lchild);
    if(t->rchild) DeleteTree(t->rchild);
    delete t;
}

测试说明
本关的测试过程如下：

平台编译step7/Main.cpp;
平台运行该可执行文件，并以标准输入方式提供测试输入；
平台获取该可执行文件的输出，然后将其与预期输出对比，如果一致则测试通过；否则测试失败。
输入格式：

输入前序序列
输入中序序列

输出格式：

输出后序序列

以下是平台对step7/Main.cpp的测试样例：

样例输入

ABDECFG
DBEAFCG

样例输出

Post Travel Result：DEBFGCA

开始你的任务吧，祝你成功！

测试代码： 

///
#include "binary_tree.h"
/


/**
	InPreToTree(): 由前序遍历序列和中序遍历序列构造二叉树
	前序序列为pa[p1:p2]
	中序序列为ia[i1:i2]
	返回所构造的二叉树的根指针
*/
BTNode* InPreToTree(char *pa, char *ia, int p1, int p2, int i1, int i2)
{
	/*请在BEGIN和END之间实现你的代码*/
	/*****BEGIN*****/

	/******END******/
}

 补充代码：

///
#include "binary_tree.h"
/


/**
	InPreToTree(): 由前序遍历序列和中序遍历序列构造二叉树
	前序序列为pa[p1:p2]
	中序序列为ia[i1:i2]
	返回所构造的二叉树的根指针
*/
BTNode* InPreToTree(char *pa, char *ia, int p1, int p2, int i1, int i2)
{
	/*请在BEGIN和END之间实现你的代码*/
	/*****BEGIN*****/
    BTNode *root=new BTNode;
    root->data=pa[p1];
    root->lchild=NULL;
    root->rchild=NULL;
    if(pa[p1]==pa[p2])
    return root;
    int a=i1;
    while(ia[a]!=root->data&&a<=i2)
    a++;
    if(ia[a]!=root->data)
        exit(0);
    int leftlen=a-i1;  
    if(leftlen>0)
    root->lchild=InPreToTree(pa,ia,p1+1,p1+leftlen,i1,a-1);
    int rightlen=i2-a;
    if(rightlen>0)
    root->rchild=InPreToTree(pa,ia,p2-rightlen+1,p2,a+1,i2);
    return root;
	/******END******/
}