数据结构与算法实验报告
第六次实验
姓名：孙瑞霜
一、实验目的
1、熟练掌握学习的每种结构及其相应算法；
2、理论联系实际，会对现实问题建模并设计相应算法。
3、优化算法，使得算法效率适当提高
二、实验要求：
1． 认真阅读和掌握教材上和本实验相关的内容和算法；
2． 上机将各种相关算法实现；
3． 实现上面实验目的要求的功能，并能进行简单的验证。
三、实验内容
认真学习 学习通->数据结构->资料->数据结构实验指导书--陈越版，从第二章进阶实验1~10中任选一个来实现，编写程序，输入给定的数据，能得到给定的输出。总结算法思想、画出流程图，并思考程序有无改进空间，如何改进。
三、算法描述
我选择的是数据结构实验指导书中的第二章进阶中的第六个实验：是否同一颗二叉树。我需要完成的操作是：
1、创建一个二叉树：给定一个插入序列就可以唯一确定一棵二叉树。然而，一棵给定的二叉树却可以由多种不同的插入序列得到。例如分别按照序列{2, 1, 3}和{2, 3, 1}插入初始为空的二叉树，都得到一样的结果。于是对于输入的各种插入序列，需要判断它们是否能生成一样的二叉树。
2、输入包含若干组测试数据。每组数据的第1行给出两个正整数N (≤10)和L，分别是每个序列插入元素的个数和需要检查的序列个数。第2行给出N个以空格分隔的正整数，作为初始插入序列。最后L行，每行给出N个插入的元素，属于L个需要检查的序列。
简单起见，保证每个插入序列都是1到N的一个排列。
3、对每一组需要检查的序列，如果其生成的二叉树跟对应的初始序列生成的一样，输出“其生成的二叉树跟对应的初始序列生成的一样”，否则输出“其生成的二叉树跟对应的初始序列生成的不一样”。
四、详细设计
五、程序代码
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
typedef struct TreeNode *BinTree; //二叉树类型
struct TreeNode {
int Data; //结点数据
BinTree Left; //指向左子树
BinTree Right; //指向右子树
int Flag; //定义结点的标志
};
/*树结点的插入*/
BinTree Insert(int X, BinTree BST)
{
if(!BST) { //若树为空,则生成并返回一 个节点的二叉树
BST = (BinTree)malloc(sizeof(struct TreeNode));
BST->Data = X;
BST->Left = BST->Right = NULL;
BST->Flag = 0;
} else { //开始找到要插入的节点
if(X < BST->Data)
BST->Left = Insert(X, BST->Left);//递归插入左子树
else if(X > BST->Data)
BST->Right = Insert(X, BST->Right);//递归插入右子树
}
//如果元素X已存在，则什么都不做
return BST;
}
/*创建树:输入数据，将它加在树上*/
BinTree MakeTree(int num)
{
BinTree S = NULL;
int i, data;
for(i=0;i<num;i++) {
scanf("%d", &data);
S = Insert(data, S);
}
return S;
}
/*清除T的各结点的flag标记*/
void ResetT(BinTree S)
{
if(S->Left) ResetT(S->Left);
if(S->Right) ResetT(S->Right);
S->Flag = 0;
}
/*释放S的空间*/
void FreeTree(BinTree S)
{
if(S->Left) FreeTree(S->Left);
if(S->Right) FreeTree(S->Right);
free(S);
}
void InOrderTraversal(BinTree BT) //中序遍历
{
if(BT) {
InOrderTraversal(BT->Left);//指向左子树
printf("%d ", BT->Data);
InOrderTraversal(BT->Right);//指向右子树
}
}
/*检查函数*/
int Check(BinTree T, int data)
{
if(T->Flag) {
if(data < T->Data)
return Check(T->Left, data);
else if(data > T->Data)
return Check(T->Right, data);
else
return 0; /* 是否错误 */
} else {
if(data == T->Data) {
T->Flag = 1;
return 1;
} else
return 0;
}
}
/*判别函数*/
int Judge(BinTree T, int N)
{
int i, data, flag = 0;//flag：0代表目前还一致，1代表已经不一致
scanf("%d", &data);
if(data != T->Data)
flag = 1;
else
T->Flag = 1;
for(i=1;i<N;i++) {
scanf("%d", &data);
if((!flag)&&(!Check(T, data)))
flag = 1;
}
if(flag)
return 0;
else
return 1;
}
int main()//主函数
{
int N, L;
int i, j, data;
BinTree SourceTree, CompareTree;
while(1) {
scanf("%d", &N);
if(!N) break;
scanf("%d", &L);
SourceTree = MakeTree(N);
//printf("InOrder:");
// InOrderTraversal(SourceTree);
// printf("\n");
for(i=0;i<L;i++) {
if(Judge(SourceTree, N))
printf("其生成的二叉树跟对应的初始序列生成的一样\n");
else
printf("其生成的二叉树跟对应的初始序列生成的不一样\n");
ResetT(SourceTree);//清除T的标记flag
}
FreeTree(SourceTree);//释放结点空间
}
return 0;
}
六、测试和结果