头歌（C语言）-数据结构与算法-树（共2关）_第1关:由双遍历序列构造二叉树

第1关：由双遍历序列构造二叉树

任务描述

本关任务：实现 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)
	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;
}

第2关：打印二叉树

任务描述

本关任务：请你实现 PrintTree.cpp 里的void PrintTreeRootLeft(TNode* r, int layer)函数。

相关知识

用二叉树的双指针结构存储二叉树，每个结点所含数据元素均为单个字母，试编程实现按树形状打印二叉树的算法。例如：图 1 的二叉树打印为右边的形状。

图 1 打印树结构示意图

图 1 中的二叉树打印出来的树结构实际上是一个6行4列的矩阵，如图 2 所示。

图 2 树结构打印矩阵

若由下往上收集结点，得到的序列刚好是该树的中序遍历序列，因此打印树结构相当于按照中序遍历序列的相反次序进行打印，每个结点打印一行；该例子中，打印出来的树结点共 4 列，与树的层数相同，每个结点在打印结果中所在的列号等于该结点在树中的层号。

为了便于看清打印结果，我们要求对于打印出的每一行，字母前的每个空格打印为“-----”，即连续5个’-‘；字母打印为形如”----A”的形式；字母后的空格不用打印。这样图 1 的树的打印结果应为：

1. ---------C
2. -------------------F
3. --------------E
4. ----A
5. --------------D
6. ---------B

树结点结构定义为：

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

编程要求

请你实现 PrintTree.cpp 里的void PrintTreeRootLeft(TNode* r, int layer)函数。

1. //PrintTree.cpp
2. #include <stdio.h>
3. #include <stdlib.h>
4. #include <string.h>
5. #include "PrintTree.h"
8. TNode* LayersToTree(char *A, int n)
9. /*
10. 功能：由补充虚结点（‘^’）的层序序列构造二叉树
11. 参数：`A`: 补充了虚结点（‘^’）的层序序列
12. `n`: 序列的长度
13. 输出: 所构造的二叉树的根指针，`NULL`表示没有构造出二叉树
14. */
15. {
16. TNode** pnode;
17. TNode* node;
18. int i;
19. if(n<=0)
20. return NULL;
21. pnode= new TNode*[n];
22. for(i=0; i<n; i++){
23. if(A[i]!='^'){
24. node=new TNode;
25. node->data=A[i];
26. node->left=NULL;
27. node->right=NULL;
28. pnode[i]=node;
29. }
30. else
31. pnode[i]=NULL;
32. }
33. for(i=0; i<n; i++){
34. if(pnode[i]==NULL) continue;
35. if(2*(i+1)<=n && pnode[2*(i+1)-1]!=NULL)
36. pnode[i]->left=pnode[2*(i+1)-1];
37. if(2*(i+1)+1<=n && pnode[2*(i+1)]!=NULL)
38. pnode[i]->right=pnode[2*(i+1)];
39. }
40. node=pnode[0];
41. delete pnode;
42. return node;
43. }
45. void PrintTreeRootLeft(TNode* r, int layer)
46. //r是树中一棵子树的根，打印以结点r为根的子树，
47. //layer是r在树中所处的层,约定树的根结点的层号为1
48. {
49. //在begin和end之间实现你的代码。
50. /******begin********/
52. /******end**********/
53. }
54. void DeleteTree(TNode* t)
55. {
56. if(t==NULL) return;
57. if(t->left) DeleteTree(t->left);
58. if(t->right) DeleteTree(t->right);
59. delete t;
60. }

测试说明

本关的测试过程如下：

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

输入格式： 输入层序序列

输出格式： 输出打印结果

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

样例输入： ABD^C^E

样例输出: Print (Root Left)： --------------E ---------D ----A --------------C ---------B

代码：

///
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "PrintTree.h"
/
 
/*=================================================
函数：TNode* LayersToTree(char *A, int n) 
功能：由补充虚结点（‘^’）的层序序列构造二叉树
参数：A: 补充了虚结点（‘^’）的层序序列
          n: 序列的长度
输出: 所构造的二叉树的根指针，NULL表示没有构造出二叉树
==================================================*/
TNode* LayersToTree(char *A, int n)
{
	TNode**  pnode;
	TNode* node;
	int i;
	if(n<=0)
		return NULL;
	pnode= new TNode*[n];
	for(i=0; i<n; i++){
		if(A[i]!='^'){
			node=new TNode;
			node->data=A[i];
			node->left=NULL;
			node->right=NULL;
			pnode[i]=node;
		}
		else 
			pnode[i]=NULL;
	}
	for(i=0; i<n; i++){
		if(pnode[i]==NULL) continue;
		if(2*(i+1)<=n && pnode[2*(i+1)-1]!=NULL)
			pnode[i]->left=pnode[2*(i+1)-1];
		if(2*(i+1)+1<=n && pnode[2*(i+1)]!=NULL)
			pnode[i]->right=pnode[2*(i+1)];
	}
	node=pnode[0];
	delete pnode;
	return node;
} 
 
void PrintTreeRootLeft(TNode* r, int layer)
//r是树中一棵子树的根，打印以结点r为根的子树，
//layer是r在树中所处的层,约定树的根结点的层号为1
{
    /*请在BEGIN和END之间实现你的代码*/
    /*****BEGIN*****/
    if (r->right)
	{
		PrintTreeRootLeft(r->right,layer+1);
	}
	printf("----");
	for (int i=1;i<layer;i++)
	printf("-----");
	printf("%c\n",r->data);
	if (r->left)
	{
		PrintTreeRootLeft(r->left,layer+1);
	}
    /******END******/
    /*请不要修改[BEGIN,END]区域外的代码*/
}
 
void DeleteTree(TNode* t)
{
	if(t==NULL) return;
	if(t->left) DeleteTree(t->left);
	if(t->right) DeleteTree(t->right);
	delete t;
}

以上内容仅供参考哟，大家还需独立完成，巩固知识点^-^