利用二叉排序树对顺序表进行排序

1、长 沙 学 院课程设计说明书题目 利用二叉排序树对顺序表进行排序系(部)专业(班级)姓名学号指导教师起止日期2015.12.82015.12.15课程设计任务书课程名称：数据结构与算法课程设计设计题目：为了充分调动学生的学习积极性与主动性，适应不同兴趣、不同程度的学生对课程设计的要求，本课程设计提供四个任选题。每个学生可以根据本人的兴趣及能力选择教师指定的选题，也可以自定其他的选题。1、一元多项式计算问题2、迷宫问题3、利用二叉排序树对顺序表进行排序4、交通咨询系统5、内部排序算法的比较已知技术参数和设计要求：需求说明及要求题目三：利用二叉排序树对顺序表进行排序问题描述：利用二叉排序树对顺序表

2、进行排序。基本要求：(1) 生成一个顺序表L;(2) 对所生成的顺序表L构造二叉排序树;(3) 利用栈结构实现中序遍历二叉排序树;(4) 中序遍历所构造的二叉排序树将记录由小到大输出。测试数据：用伪随机数产生程序产生，表长不小于20。选作内容：用实现二叉排序树的插入和删除操作。各阶段具体要求：1、需求分析阶段熟悉系统业务，从业务中抽取出系统的需求，形成完善的需求说明书。2、系统设计阶段根据需求，进行程序设计，包括定义系统的界面、定义系统数据的存储方式等，形成完善的设计说明书。3、编码实现阶段（1）完成代码编写 （2）要求代码编写规范4、系统测试阶段（1）完成功能调试（2）要求完成必要的测试工作

3、5、交付实施阶段（1）提交可正常执行的系统（2）提交系统需求说明书、设计说明书、程序代码（3）撰写课程设计报告书（4）要求规范地书写文档设计工作量：（1）软件设计：完成问题陈述中所提到的所有需求功能。（2）论文：要求撰写不少于3000字的文档，详细说明各阶段具体要求。工作计划：数据结构课程设计总学时数为2 周，其进度及时间大致分配如下：序号 设计内容 天数1 分析问题，给出数学模型，选择数据结构 12 设计算法，给出算法描述 23 给出源程序清单 14 编辑、编译、调试源程序 55 编写课程设计报告 1总 计 10注意事项n 提交文档Ø 长沙学院课程设计任务书（每学生1份）Ø

4、; 长沙学院课程设计鉴定表（每学生1份）Ø 长沙学院课程设计说明书（每学生1份）指导教师签名： 日期： 教研室主任签名： 日期：系主任签名： 日期：长沙学院课程设计鉴定表姓名学号 专业班级设计题目利用二叉排序树对顺序表进行排序指导教师指导教师意见：评定等级： 教师签名： 日期： 答辩小组意见：评定等级：答辩小组长签名：日期：教研室意见：教研室主任签名： 日期： 系（部）意见：系主任签名：日期：说明课程设计成绩分“优秀”、“良好”、“及格”、“不及格”四类；摘要数据结构是研究与数据之间的关系，我们称这一关系为数据的逻辑结构，简称数据结构。当数据的逻辑结构确定以后，数据在物理空间中的存储

5、方式，称为数据的存储结构。相同的逻辑结构可以具有不同的存储结构，因而有不同的算法。本次课程设计，是基于链式顺序表建立二叉排序树。主要功能有建立、重建、插入、删除以及遍历。关键词：二叉排序树、中序遍历、插入结点、删除结点目录第1章设计内容与要求71.1课程名称：数据结构与算法课程设计71.2 设计要求：7第2章需求分析82.1设计目的82.2 设计环境8第三章 概要设计93.1 功能结构93.2函数的结构体103.3系统主要的函数10第四章 详细设计124.1插入模块的设计124.2删除模块的设计134.3遍历模块设计144.4树型打印模块的设计154.5重建二叉树模块的设计15第五章 模块测试

6、165.1插入模块测试165.2删除插入模块测试175.3遍历模块测试185.4树型打印模块测试195.5二叉排序树重建模块测试20第六章 总结22第七章 附录源代码23第1章 设计内容与要求 1.1课程名称：数据结构与算法课程设计 设计题目： 利用二叉排序树对顺序表进行排序 问题描述：利用二叉排序树对顺序表进行排序。1.2 设计要求： (1) 生成一个顺序表L;(2) 对所生成的顺序表L构造二叉排序树;(3) 利用栈结构实现中序遍历二叉排序树;(4) 中序遍历所构造的二叉排序树将记录由小到大输出。测试数据：用伪随机数产生程序产生，表长不小于20。选作内容：用实现二叉排序树的插入和删除操作。第

7、2章 需求分析2.1设计目的 本次构造的是一个二叉排序树，主要的功能有二叉排序树的建立、节点的插入与删除，二叉树的中序遍历、树型打印、以及重建一个新的二叉排序树。 二叉排序树系统主菜单建立退出中序遍历树型打印删除插入 图2.1 系统功能模块图2.2 设计环境Windows 10系统、visual studio2015下编译运行第三章 概要设计 3.1 功能结构 本程序主要实现的有七个功能，首先创建二叉排序树，完成后出现菜单界面，菜单界面的功能有：二叉排序树的插入、删除、中序遍历、树形输出、二叉排序树的重建、退出。 创建二叉树Switch(1)插入结点删除结点重建二叉树树型打印Exit(0)退出

8、中序遍历Switch(2)Switch(3)Switch(4)Switch(5)Switch(6) 图3.1 主要功能结构流程图 3.2函数的结构体typedef int keytype;typedef int valuetype;typedef int listtype;/struct linklist struct linklist *next;int element; /参数的数值; /顺序表结点的结构体struct int_linklist struct linklist *head; /顺序表的头结点的定义int counts; /对顺序表的元素的多少进行统计;/typedef st

9、ruct BSTNode keytype data; /存放关键字的datastruct BSTNode *lchild, *rchild; /定义二叉排序树的指针BTNode, *Btree;/typedef Btree Selem;typedef struct snode Selem data; /定义栈的存储的数据struct snode *next; /栈的指针snode, *linkst;typedef struct linkstack linkst top; /定义栈的栈顶指针int count; /统计栈里面的元素linkstack; 3.3系统主要的函数struct int_l

10、inklist*init();/ 初始化链式顺序表void add(struct int_linklist*, int);/链式顺序表增加结点void printf_list(struct int_linklist *);/输出已经创建好的顺序表/void emptyMessage(char *);/输出错误的提示void initstack(linkstack *);/初始化链式栈void push_stacks(linkstack *, Selem );/进栈函数void pop_stacks(linkstack *,Selem&);/出栈函数bool empty_stack(li

11、nkstack *);/判断栈是否为空的函数/BTNode *init_BSTree(Btree);/初始化二叉排序树Btree BSTree_fund();/建立一个二叉排序树的函数bool Search_BSTree(Btree, keytype, BTNode&, BTNode&);/判断该值是否在二叉树存在bool insert_BSTree(Btree&, valuetype);/插入一个数值，返回0或1，判断是否插入成功bool Delete_BSTree(Btree&, keytype);/删除函数，找到要删除的数值，调用delete_value(

12、Btree &tree)，返回0或1判断删除是否成功 void delete_value(Btree &tree);/删除这个结点void inoder_rec(Btree);/中序非递归遍历二叉排序树void PrintTree(Btree, int);/按树状图就行输出/void menu(Btree);/函数的菜单界面第四章 详细设计4.1插入模块的设计 bool Search_BSTree(Btree tree, keytype value, Btree &parents, Btree &child) /寻找函数，判断二叉排序树中是否有该值，有返回1，无

13、返回0child = tree;/子节点等于根节点while (child) /如果子节点child不为空，则执行下面代码if (value = child->data) /如果值等于child->data，则表示找到，返回1return 1;else if (value < child->data) /如果该值小于child->data，则向左子树进行查找parents = child; /parents纪录child结点的上一个结点，相当于记录父节点child = child->lchild;else parents = child;child = ch

14、ild->rchild;return 0; /如果不执行上面一段代码，或者没有找到，返回0/ bool insert_BSTree(Btree &tree, keytype value) Btree parents, child; /定义指针if (!Search_BSTree(tree, value, parents, child) /如果二叉排序树找不到该值，则插入Btree S = (BTNode*)malloc(sizeof(BTNode); /申请一个结构体空间S->data = value; /赋值S->lchild = NULL;S->rchild

15、 = NULL;if (!tree) tree = S; /如果tree为空，则tree为s，设置根结点else if (value < parents->data) /如果value < parents->data，就插入到左子树parents->lchild = S;else parents->rchild = S; /反之，插入到右子树return 1;/ return tree;4.2删除模块的设计 bool Delete_BSTree(Btree &tree, keytype value) /删除函数if (!tree)return 0;

16、/tree为空，则表示删除功能不能执行else if (value = tree->data) /如果找到与value值相同的指针，调用delete_value函数进行删除delete_value(tree);return 1;else if (value < tree->data) /value小于结点的值，往左子树进行寻找return Delete_BSTree(tree->lchild, value);else return Delete_BSTree(tree->rchild, value);/printf("%dn", tree-&g

17、t;data);void delete_value(Btree &p) Btree q = NULL, s = NULL;if (p->lchild && p->rchild) /删除的结点，左右子树都不为空的情况q = p; s = p->lchild; /q记录,s设为删除结点的左结点while (s->rchild) q = s; s = s->rchild;/进行循环，找到最右边的那个结点p->data = s->data; /把找到的最右边结点的关键字赋值给p的关键字if (q != p) q->rchild =

18、 s->lchild; /挂接左右子树else q->lchild = s->lchild;/printf("%dt%dt%dt%dn", q->data, q->data, s->data, tree->data);free(s); /删除s这个结点else if (!p->rchild) /右子树为空，所以挂接到左子树上q = p; p = p->lchild; free(q);else q = p; p = p->rchild; free(q); /左子树为空，所以挂接到右子树上/printf("%

19、dt%dt%dn",q -> data,q -> data,tree->data);4.3遍历模块设计 void inoder_rec(Btree T) linkstack S ;initstack( &S);/初始化一个栈Selem e;Btree p = T;while (p | !(S.count = 0) /当栈不为空或者p不为空时执行while(p) push_stacks(&S, p); /p不为空，则进栈p = p->lchild; /对左子树进行遍历if(!empty_stack(&S) e = Get_top(S, e

20、); /当栈不为空时，取栈顶，输出栈顶指针所指向的data值printf("%dn",e -> data);pop_stacks(&S, p); /出栈，对右子树进行遍历p = p->rchild;/*if (T) inoder_rec(T->lchild);printf("%dn", T->data);inoder_rec(T->rchild);*/menu(tree);4.4树型打印模块的设计 void PrintTree(Btree bt, int nlayer) /采用先序遍历的方法，进行树型打印 if(bt

21、)PrintTree(bt->rchild, nlayer + 10);for (int i = 0; i<nlayer; i+)printf(" ");printf("%d n", bt->data);PrintTree(bt->lchild, nlayer + 10);4.5重建二叉树模块的设计 Btree BSTree_fund() struct int_linklist *lists = NULL;Btree tree = NULL;int n;lists = init();/初始化顺序表srand(unsigned)ti

22、me(NULL); /伪随机函数的初始化printf("please input how many numbers:n");scanf_s("%d", &n); /输入要插入多少的数for (int i = 0; i < n; i+) add(lists, rand();/构造顺序表struct linklist *p;/Btree tree = NULL;tree = init_BSTree(tree); /初始化二叉树p = lists->head->next;while (p != NULL) insert_BSTree(

23、tree, p->element);p = p->next;/调用insert_BSTree函数构造二叉树return tree; 第五章 模块测试5.1插入模块测试5.2删除插入模块测试5.3遍历模块测试5.4树型打印模块测试5.5二叉排序树重建模块测试第六章 总结通过这次课程设计，我对二叉排序树的整个构造流程更加了解了，同时也对顺序表和栈这两种数据结构做了一次复习，但同时也存在了很多问题。我在删除函数中因为有些指针没有用好，所以最开始只是跟我报错说是read()出错，我反复的检查许久一直找不到出错的地方在哪，不得已，只能重新写了一遍删除函数，发现我分成两个删除函数去执行（一个函

24、数去找那个需要删除的结点，另一个函数则是对这已经找到的结点进行删除），没有问题。而对于中序遍历函数，我先用递归做测试，先把其他功能做完善以后，再用栈来实现中序非递归遍历。第七章 附录源代码 #include<iostream>#include<malloc.h>#include<cstdio>#include<stdlib.h>#include<time.h>/#include<graphics.h>/using namespace std;/unsigned int n = 30;/typedef int keytype

25、;typedef int valuetype;typedef int listtype;/struct linklist struct linklist *next;int element;struct int_linklist struct linklist *head;int counts;/typedef struct BSTNode keytype data;struct BSTNode *lchild, *rchild;BTNode, *Btree;/typedef Btree Selem;typedef struct snode Selem data;struct snode *n

26、ext;snode, *linkst;typedef struct linkstack linkst top;int count;linkstack;/struct int_linklist*init();void add(struct int_linklist*, int);void printf_list(struct int_linklist *);/void emptyMessage(char *);void initstack(linkstack *);void push_stacks(linkstack *, Selem );void pop_stacks(linkstack *,

27、Selem&);bool empty_stack(linkstack *);/BTNode *init_BSTree(Btree);Btree BSTree_fund();bool Search_BSTree(Btree, keytype, BTNode&, BTNode&);bool insert_BSTree(Btree&, valuetype);bool Delete_BSTree(Btree&, keytype);void delete_value(Btree &tree);void inoder_rec(Btree);void Prin

28、tTree(Btree, int);/void menu(Btree);/、int main() Btree tree = NULL;/printf_list(lists);tree = BSTree_fund();/printf("n");/printf("%dn", tree->data);/printf("n");/inoder_rec(tree);menu(tree);return 0;/struct int_linklist* init() struct int_linklist*lists;lists = (stru

29、ct int_linklist*)malloc(sizeof(struct int_linklist*);lists->head = (struct linklist*)malloc(sizeof(struct linklist);lists->head->element = -1;lists->counts = 0;lists->head->next = NULL;return lists;void add(struct int_linklist *lists, int value) struct linklist *p;p = (struct linkl

30、ist *)malloc(sizeof(struct linklist);p->next = NULL;p->element = value;p->next = lists->head->next;lists->head->next = p;lists->counts+;/return lists;void printf_list(struct int_linklist *lists) struct linklist *p;p = lists->head->next;while (p != NULL) printf("%dn

31、", p->element);p = p->next;/void emptyMessage(char *s) printf("%sn", s);exit(1);void initstack(linkstack *stacks) /linkst *p;stacks->top = (linkst)malloc(sizeof(snode);if (stacks->top = NULL)emptyMessage("it is false");stacks->top = NULL;stacks->count = 0;/

32、stacks.top -> next = NULL;Selem Get_top(linkstack stacks, Selem &e) if (stacks.top = NULL)emptyMessage("it is empty");e = stacks.top->data;return e;void push_stacks(linkstack *stacks, Selem e) linkst p = (linkst)malloc(sizeof(snode);if (p = NULL)emptyMessage("False");p-

33、>data = e;p->next = stacks->top;stacks->top = p;stacks->count+;void pop_stacks(linkstack *stacks,Selem &e) linkst p;if (stacks->count = 0)emptyMessage("it is empty");e = stacks->top->data;p = stacks->top;/printf("%dn", p->data);stacks->top = s

34、tacks->top->next;free(p);stacks->count-;bool empty_stack(linkstack *stacks) if (stacks->count = 0)return 1;else return 0;/BTNode *init_BSTree(Btree tree) Btree root = tree;return root;bool Search_BSTree(Btree tree, keytype value, Btree &parents, Btree &child) /if(tree != NULL)chi

35、ld = tree;while (child) if (value = child->data) return 1;else if (value < child->data) parents = child;child = child->lchild;else parents = child;child = child->rchild;return 0;/ bool insert_BSTree(Btree &tree, keytype value) Btree parents, child;if (!Search_BSTree(tree, value, p

36、arents, child) Btree S = (BTNode*)malloc(sizeof(BTNode);S->data = value;S->lchild = NULL;S->rchild = NULL;if (!tree) tree = S;else if (value < parents->data) parents->lchild = S;else parents->rchild = S;return 1;/ return tree;/ menu(tree);Btree BSTree_fund() struct int_linklist

37、*lists = NULL;Btree tree = NULL;int n;lists = init();srand(unsigned)time(NULL);printf("please input how many numbers:n");scanf_s("%d", &n);for (int i = 0; i < n; i+) add(lists, rand();struct linklist *p;/Btree tree = NULL;tree = init_BSTree(tree);p = lists->head->nex

38、t;while (p != NULL) insert_BSTree(tree, p->element);p = p->next;return tree;bool Delete_BSTree(Btree &tree, keytype value) if (!tree)return 0;else if (value = tree->data) delete_value(tree);return 1;else if (value < tree->data) return Delete_BSTree(tree->lchild, value);else ret

39、urn Delete_BSTree(tree->rchild, value);printf("%dn", tree->data);void delete_value(Btree &p) Btree q = NULL, s = NULL;if (p->lchild && p->rchild) q = p; s = p->lchild;while (s->rchild) q = s; s = s->rchild;p->data = s->data;if (q != p) q->rchild =

40、s->lchild;else q->lchild = s->lchild;/printf("%dt%dt%dt%dn", q->data, q->data, s->data, tree->data);free(s);else if (!p->rchild) q = p; p = p->lchild; free(q);else q = p; p = p->rchild; free(q);/printf("%dt%dt%dn",q -> data,q -> data,tree->d

41、ata);void inoder_rec(Btree T) linkstack S ;initstack( &S);Selem e;Btree p = T;while (p | !(S.count = 0) while(p) push_stacks(&S, p);p = p->lchild;if(!empty_stack(&S) e = Get_top(S, e);printf("%dn",e -> data);pop_stacks(&S, p);p = p->rchild;/*if (T) inoder_rec(T->lchild);printf("%dn", T->data);inoder_rec(T->rchild);*/menu(tree);void PrintTree(Btree bt, int nlayer) /*if(bt=NULL