数据结构课程设计文档

1、题目：（二叉搜索树）开始一个数n，（1<=n<=20）表示有n个序列需要判断，n=0的时候输入结束。接下去一行是一个序列，序列长度小于10，包含（09）的数字，没有重复数字，根据这个序列可以构造出一颗二叉搜索树。接下去的n行有n个序列，每个序列格式跟第一个序列一样，请判断这两个序列是否能组成同一棵二叉搜索树。如果序列相同则输出YES，否则输出NO。 要求：（1） 序列个数范围为120.（2） 序列长度小于10，没有重复数字。1、问题分析和任务定义 从题目可知，需要输入多个序列，而且序列中没有重复数字。用第一个序列与剩下的几个序列分别比较，判断两个序列能不能组成同一个序列。 在编程中

2、需要建立二叉树，如何判断两个二叉树能不能组成同一棵二叉搜索树是一个关键问题。由于所有二叉搜索树的先序编列都是递增的，而且中序遍历可以用来区分二叉树，所以用中序遍历来判断两个序列能否组成同一棵二叉树，同时用数组来存储中序遍历后的序列。 因此解决问题的方案是：先序遍历二叉树，用数组存储先序遍历后的序列，用数组来判断两个序列能否组成同一棵二叉搜索树。2、数据结构的选择和概要设计 由于二叉树无法直接比较，所以先先序遍历二叉搜索树，同时用数组存储。 我的设计思路是：先建立一个二叉树，然后先序遍历它，由于数组可以比较，所以用数组存储。数组中的数分别对应先序遍历二叉树后的序列中的数所以把数组中对应的数分别比

3、较，同时定义一个整型常量f，如果数组中对应的数相同，f+，否则退出。用f值与数组长度比较，如果相等，则两个系列能组成同一棵二叉搜索树，否则，不能。3、详细设计和编码 程序的核心流程为：建立二叉树 先序遍历二差树数组存储遍历二叉树的序列数组比较程序的核心即为先序遍历二叉树和数组存储如下：preorder(Bstnode *T) /先序遍历二叉树 if(T) printf("%4d",T->key); i+;ai=T->key;/printf(" ");/printf("数组的下标i=%d",i);preorder(T->

4、;lchild);preorder(T->rchild); f=1; /利用数组存储并比较/printf("f=%dn",f); for(e=b;e<d;e+) if(af=ae) f+; else break; /printf("f=%dn",f); /printf("f=%d",f); if(f=d-b+1) printf("yes"); else printf("no"); printf(" "); /printf("i=%d",i);4

5、、上机调试过程问题：序列是无法比较的，故无法直接判断两个序列能否组成同一棵二叉树；在循环时无法直接退出必须人工退出。解决方法：用数组存储，用数组知识来判断两个序列能否组成同一棵二叉搜索树。先序遍历二叉树得到一个新的序列，同时定义一个全局变量数组用来存储先序遍历二叉树后得到的序列，这样可以直接通过数组的比较来间接判断两个序列能否组成同一个二叉搜索树。至于第二个问题，只要定义一个整型常量n，利用while循环，以n！=0为循环条件来直接退出运行过后的界面。部分程序： while(scanf("%d",&n)!=EOF&&n!=0) /以while循环作为

6、循环结束的标志t1=CreateBst();printf("先序排列后的序列:n");preorder(t1);putchar('n'); printf("以数组形式存储:n"); for(i=1;i<10;i+) printf("%2d",ai); putchar('n');b=i+1; /printf("输入需要与第一个序列比较的序列个数:");/scanf("%d",&n); printf("请输入%d个序列,比较完后以0退出，否则继

7、续输入序列:n",n) ;for(c=0;c<n;c+) /printf("第二个树"); t2=CreateBst(); printf("先序排列后:n"); preorder(t2); putchar('n'); printf("以数组形式存储:n"); for(d=b;d<b+9;d+) printf("%2d",ad); putchar('n'); f=1;/printf("f=%dn",f); for(e=b;e<d;e+)

8、if(af=ae) f+; else break; /printf("f=%dn",f); /printf("f=%d",f); if(f=d-b+1) printf("yes"); else printf("no"); printf(" "); /printf("i=%d",i); b=i+1; 5、测试结果及其分析测试数据1：测试数据2：6、用户使用说明 输入一个数字n（1<=n<=20）表示需要与被比较的序列的序列个数，先输入被比较序列，先序遍历它同时以数组

9、形式存储。然后输入需要与被比较序列比较的序列，也是先遍历序列在以数组形式存储。在比较过程中如果两个序列能组成同一棵二叉搜索树，则输出yes，否则输出no。7参考文献1王昆仑，李红。数据结构与算法。北京：铁道工业出版社，2007年5月第一版2徐孝凯。数据结构实用教程。北京：清华大学出版社。1999年12月第一版8、附录#include "stdio.h"#include "malloc.h"#include "string.h"#define NULL 0#define endflag -1 int a10;int i=0; typed

10、ef struct nodeint key;/int other;struct node *lchild,*rchild;Bstnode;Bstnode *insertBst(Bstnode *t,int x)Bstnode *s,*p,*f;p=t;while(p!=NULL)f=p;if(x=p->key) return t;if(x<p->key) p=p->lchild;else p=p->rchild;s=(Bstnode *)malloc(sizeof(Bstnode);s->key=x;s->lchild=NULL;s->rchil

11、d=NULL;if(t=NULL) return s;if(x<f->key) f->lchild=s;else f->rchild=s;return t;Bstnode *CreateBst()Bstnode *t;int key;t=NULL;scanf("%d",&key);while(key!=endflag)t=insertBst(t,key);scanf("%d",&key);return t;preorder(Bstnode *T) if(T) printf("%4d",T->

12、;key); i+;ai=T->key;/printf(" ");/printf("数组的下标i=%d",i);preorder(T->lchild);preorder(T->rchild);void main() int b,c,d,e,f; Bstnode *t1,*t2; int n; printf("请输入需要与被比较序列的序列个数(1<=n<=20),然后再输入被比较序列:"); /scanf("%dn",&n); while(scanf("%d"

13、,&n)!=EOF&&n!=0) t1=CreateBst();printf("先序排列后的序列:n");preorder(t1);putchar('n'); printf("以数组形式存储:n"); for(i=1;i<10;i+) printf("%2d",ai); putchar('n');b=i+1; /printf("输入需要与第一个序列比较的序列个数:");/scanf("%d",&n); printf("

14、;请输入%d个序列,比较完后以0退出，否则继续输入序列:n",n) ;for(c=0;c<n;c+) /printf("第二个树"); t2=CreateBst(); printf("先序排列后:n"); preorder(t2); putchar('n'); printf("以数组形式存储:n"); for(d=b;d<b+9;d+) printf("%2d",ad); putchar('n'); f=1;/printf("f=%dn",f); for(e=b;