由双遍历序列构造二叉树(数组的形式)

任务描述

本关任务：实现 ConstructTree.cpp 里的TNode* InPreToTree(char *pa, char *ia, int p1, int p2, int i1, int i2)函数。

相关知识

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

树结点结构定义为：

1. struct TNode{
2. char data;
3. struct TNode* left;
4. struct TNode* right;
5. };

编程要求

本关任务是实现 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来申请结点空间。

1. //ConstructTree.cpp
2. #include <stdio.h>
3. #include <stdlib.h>
4. #include <string.h>
5. #include "ConstructTree.h"
7. /*
8. InPreToTree(): 由前序遍历序列和中序遍历序列构造二叉树
9. 前序序列为pa[p1:p2]
10. 中序序列为ia[i1:i2]
11. 返回所构造的二叉树的根指针
12. */
13. TNode* InPreToTree(char *pa, char *ia,
14. int p1, int p2, int i1, int i2)
15. {
16. //在begin和end之间添加你的代码
17. /********* begin **********/
19. /********* end ************/
20. }
22. void PrintPostTravel(TNode* t)
23. {
24. if(t==NULL) return;
25. if(t->left) PrintPostTravel(t->left);
26. if(t->right) PrintPostTravel(t->right);
27. printf("%c", t->data);
28. }
30. void DeleteTree(TNode* t)
31. {
32. if(t==NULL) return;
33. if(t->left) DeleteTree(t->left);
34. if(t->right) DeleteTree(t->right);
35. delete t;
36. }

测试说明

本关的测试过程如下：

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

输入格式： 输入前序序列 输入中序序列

输出格式： 输出后序序列

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

样例输入 ABDECFG DBEAFCG

样例输出 Post Travel Result：DEBFGCA

 源代码：

///

#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*****/

    TNode *root=new TNode;

    root->data=pa[p1];

    root->left=NULL;

    root->right=NULL;                  //递归终止条件:先序遍历中只有一个结点

    if(pa[p1]==pa[p2])

    return root;

                                      //数组元素名是其首地址

    int a=i1;

    while(ia[a]!=root->data&&a<=i2)    //中序里面

    a++;

    if(ia[a]!=root->data)             //数组2遍历完成

        exit(0);

    int leftlen=a-i1;  

    if(leftlen>0)                   //左子树的个数

    root->left=InPreToTree(pa,ia,p1+1,p1+leftlen,i1,a-1);

    

    int rightlen=i2-a;

    if(rightlen>0)

    root->right=InPreToTree(pa,ia,p2-rightlen+1,p2,a+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;

}