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

1、A长沙学院课程设计说明书题目利用一叉排序树对顺序表进行排序系（部)专业（班级）姓名学号指导教师起止日期2015.12.8 2015.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字的文档，详细说明各阶段具体要求。序号设计内容1分析问题，给出数学模型，选择数据结构2设计算法，给出算法描述3给出源程序清单4编辑、编译、调试源程序5编写课程设计报告总计10工作计划：数据结构课程设计总学时数为 2周，其进度及时间大致分配如下:天数12151注意事项提交文档（每学生1份）（每学生1份）（每学生1份）?长沙学院课程设计任务书 ? 长沙学院课程设计鉴

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

5、的算法。本次课程设计，是基于链 式顺序表建立二叉排序树。主要功能有建立、重建、插入、删除以及遍历。关键词：二叉排序树、中序遍历、插入结点、删除结点目录第1章设计内容与要求61.1课程名称：数据结构与算法课程设计 61.2设计要求：6第2章需求分析72.1设计目的72.2 设计环境8第三章概要设计83.1功能结构83.2函数的结构体 93.3系统主要的函数 10第四章详细设计114.1插入模块的设计 114.2删除模块的设计124.3遍历模块设计134.4树型打印模块的设计 144.5重建二叉树模块的设计 15第五章模块测试165.1插入模块测试 165.2删除插入模块测试 175.3遍历模块测

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

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

8、功能结构流程图3.2函数的结构体typedef int keytype;typedef int valuetype; typedef int listtype;/struct lin klist struct lin klist *n ext;int eleme nt; /参数的数值；/顺序表结点的结构体struct in t_li nklist struct lin klist *head; /顺序表的头结点的定义int cou nts; /对顺序表的元素的多少进行统计/typedef struct BSTNode keytype data; /存放关键字的datastruct BSTNod

9、e *lchild, *rchild; /定义二叉排序树的指针BTNode, *Btree; 一|/typedef Btree Selem;typedef struct snode Selem data; / 定义栈的存储的数据struct snode *next; /栈的指针 |sno de, *li nkst;typedef struct li nkstack linkst top; /定义栈的栈顶指针|int count; /统计栈里面的元素li nkstack;3.3系统主要的函数struct i nt li nklist*i ni t();/初始化链式顺序表void add(stru

10、ct in t li nklist*, in t);/链式顺序表增加结点void prin tf_list(struct in t_li nklist *);/输出已经创建好的顺序表/void emptyMessage(char *);/输出错误的提示void in itstack(li nkstack *);/初始化链式栈void push_stacks(l in kstack *, Selem );/进栈函数void pop stacks(l in kstack *,Sele m&);/出栈函数Abool empty_stack(l in kstack *);/判断栈是否为空的函数/BTN

11、ode *in it_BSTree(Btree);/初始化二叉排序树Btree BSTree_fu nd();/建立一个二叉排序树的函数bool Search_BSTree(Btree, keytype, BTNode&, BTNode&);/判断该值是否在二叉树存在bool in sert_BSTree(Btree&, valuetype);/插入一个数值，返回0或1判断是否插入成功bool Delete_BSTree(Btree&, keytype);/删除函数，找到要删除的数值，调用delete_value(Btree &tree) ，返回0或 1判断删除是否成功void delete_

12、value(Btree &tree);/删除这个结点void ino der_rec(Btree);/中序非递归遍历二叉排序树 void Prin tTree(Btree, in t);/按树状图就行输出 / void menu (Btree);/函数的菜单界面第四章详细设计4.1插入模块的设计bool Search_BSTree(Btree tree, keytype value, Btree &pare nts, Btree &child) /寻找函数，判断二叉排序树中是否有该值，有返回 1,无返回0child = tree;/子节点等于根节点while (child) / 如果子节点ch

13、ild不为空，则执行下面代码if (value = child-data) /如果值等于 child-data ，则表示找到，返回 1return 1;Aelse if (value data) /如果该值小于child-data，则向左子树进仃查找pare nts = child; /pare nts纪录child结点的上一个结点，相当于记录父节点child = child-lchild;else pare nts = child;child = child-rchild;return 0; /如果不执行上面一段代码，或者没有找到，返回0/ bool in sert_BSTree(Btree

14、 &tree, keytype value) Btree pare nts, child; /定义指针if (!Search_BSTree(tree, value, pare nts, child) /如果二叉排序树找不到该值，则插入Btree S = (BTNode*)malloc(sizeof(BTNode); /申请一个结构体空间S-data = value; / 赋值S-lchild = NULL;S-rchild = NULL;if (!tree) tree = S; /如果tree为空，则tree为s，设置根结点else if (value data) /女口果 value dat

15、a，就插入至 U左子树pare nts-lchild = S;return 1;/ return tree;4.2删除模块的设计bool Delete_BSTree(Btree &tree, keytype value) /删除函数if (!tree)return 0; /tree为空，则表示删除功能不能执行else if (value = tree-data) /如果找到与value值相同的指针，调用delete value函数进行删除delete value(tree);return 1;else if (value data) /value小于结点的值，往左子树进行寻找retur n D

16、elete_BSTree(tree-lchild, value);while (p | !(S.cou nt = 0) /当栈不为空或者p不为空时执行else return Delete BSTree(tree-rchild, value);/prin tf(%dn, tree-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 =

17、s; s = s-rchild;/进行循环，找到最右边的那个结点p-data = s-data; /把找到的最右边结点的关键字赋值给p的关键字if (q != p) q-rchild - s-lchild; /挂接左右子树else q-lchild = s-lchild;/prin tf(%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

18、; free(q); /左子树为空，所以挂接到右子树上/prin tf(%dt%dt%dn,q - data,q - data,tree-data);4.3遍历模块设计void ino der_rec(Btree T) lin kstack S ;in itstack( & S);/初始化一个栈Selem e;Btree p = T;while(p) push stacks(&S, p); /p 不为空，则进栈 p = p-lchild; /对左子树进行遍历if(!empty_stack(&S) data 值e = Get_top(S, e); /当栈不为空时，取栈顶，输出栈顶指针所指向的pr

19、intf(%dn”,e - data);pop_stacks(&S, p); /出栈，对右子树进行遍历p = p-rchild;/*if (T) ino der rec(T-lchild); prin tf(%dn, T-data);ino der rec(T-rchild); */men u(tree);4.4树型打印模块的设计void PrintTree(Btree bt, int nlayer) /采用先序遍历的方法，进行树型打印if(bt)Prin tTree(bt-rchild, nlayer + 10);for (int i = 0; idata);Prin tTree(bt-lc

20、hild, n layer + 10); A4.5重建二叉树模块的设计Btree BSTree fu nd() struct in t_li nklist *lists = NULL;Btree tree = NULL;int n;lists = i nit();初始化顺序表sran d(u nsig ned)time(NULL); /伪随机函数的初始化prin tf(please in put how many nu mbers:n);scan f_s(%d, &n); /输入要插入多少的数for (int i = 0; i head-n ext;while (p != NULL) in s

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

22、一个函数去找那个需要删除的结点，另一个函数则是对这已经找到的结点进行删除)，没有问题。而对于中序遍历函数，我先用递归做测试，先把其他功能做 完善以后，再用栈来实现中序非递归遍历。A第七章附录源代码#in clude#in clude#in clude#i nclude _| #in clude#in clude /us ing n amespace std; /un sig ned int n = 30;/typedef int keytype;typedef int valuetype;typedef int listtype;/struct li nklist struct lin kli

23、st *n ext;int eleme nt;struct i nt_li nklist struct lin klist *head; int coun ts;/typedef struct BSTNode |keytype data;struct BSTNode *lchild, *rchild;BTNode, *Btree;/typedef Btree Selem;typedef struct snode Selem data;struct snode *next;sno de, *li nkst;typedef struct lin kstack lin kst top;int cou

24、nt;li nkstack;/struct i nt li nklist*i nit();void add(struct in t li nklist*, in t);void prin tf_list(struct in t_li nklist *);/void emptyMessage(char *);void in itstack(li nkstack *);void push_stacks(l in kstack *, Selem ); void pop_stacks(l in kstack *,Sele m&); bool empty_stack(l in kstack *);/BT

25、Node *i ni t_BSTree(Btree);Btree BSTree_fu nd();bool Search_BSTree(Btree, keytype, BTNode&, BTNode&);bool in sert BSTree(Btree&, valuetype);bool Delete_BSTree(Btree&, keytype);void delete_value(Btree &tree);void ino der rec(Btree);void Prin tTree(Btree, in t); / void menu (Btree);/ 、int mai n() Btre

26、e tree = NULL;/prin tf_list(lists);tree = BSTree fu nd();/prin tf(n ”);/prin tf(%dn, tree-data);/prin tf(n ”);/ino der_rec(tree);men u(tree);return 0;/struct int linklist* init() struct in t_li nklist*lists;lists = (struct in t li nklist*)malloc(sizeof(struct in t li nklist*);lists-head = (struct li

27、n klist*)malloc(sizeof(struct lin klist);lists-head-eleme nt = -1;lists-co unts = 0;lists-head- next = NULL;return lists;void add(struct in t_li nklist *lists, int value) struct lin klist *p;p = (struct lin klist *)malloc(sizeof(struct lin klist); p-next = NULL;p-eleme nt = value;p-next = lists-head

28、-n ext;lists-head-n ext = p;lists-co un ts+;/return lists;void printf_list(struct int_linklist *lists) struct lin klist *p;p = lists-head-n ext; while (p != NULL) printf(%dn, p-element); p = p_n ext;/void emptyMessage(char *s) prin tf(%sn, s);exit(1);void in itstack(li nkstack *stacks) /li nkst *p;s

29、tacks-top = (li nkst)malloc(sizeof(s no de);if (stacks-top = NULL)emptyMessage(it is false);stacks-top = NULL;stacks-co unt = 0;/stacks.top - next = NULL;Selem Get top(l in kstack stacks, Selem &e) if (stacks.top = NULL)emptyMessage(it is empty);e = stacks.top-data;return e;void push stacks(l in kst

30、ack *stacks, Selem e) lin kst p = (li nkst)malloc(sizeof(s no de); if (p = NULL)emptyMessage(False); p-data = e;p-next = stacks-top; stacks-top = p;stacks-co un t+;void pop_stacks(l in kstack *stacks,Selem &e) lin kst p;if (stacks-co unt = 0)emptyMessage(it is empty);e = stacks-top-data;p = stacks-t

31、op;/prin tf(%dn, p-data);stacks-top = stacks-top-n ext;free(p);stacks-co un t-;bool empty_stack(l in kstack *stacks) if (stacks-co unt = 0)retur n 1; else return 0;/BTNode *i ni t_BSTree(Btree tree) Btree root = tree;return root;bool Search BSTree(Btree tree, keytype value, Btree &pare nts, Btree &c

32、hild) if(tree != NULL)child = tree;while (child) if (value = child-data) return 1;else if (value data) pare nts = child;child = child-lchild;else pare nts = child;child = child-rchild;return 0;/ bool in sert BSTree(Btree &tree, keytype value) Btree pare nts, child;if (!Search BSTree(tree, value, par

33、ents, child) Btree S = (BTNode*)malloc(sizeof(BTNode);S-data = value;S-lchild = NULL;S-rchild = NULL;if (!tree) tree = S;else if (value data) pare nts-lchild = S;return 1;/ return tree;/ men u(tree);Btree BSTree_fu nd() struct in t_li nklist *lists = NULL;Btree tree = NULL;int n;lists = in it();sran

34、 d( un sig ned)time(NULL);prin tf(please in put how many nu mbers:n); scan f s(%d, &n);for (int i = 0; i head-n ext;while (p != NULL) in sert_BSTree(tree, p-eleme nt); p = pn ext;return tree;bool Delete_BSTree(Btree &tree, keytype value) if (!tree)return 0;else if (value = tree-data) delete value(tr

35、ee);return 1;retur n 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 = s-lchild;else q-lchild = s-lchild;/prin tf(%dt%dt%

36、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);./prin tf(%dt%dt%dn,q - data,q - data,tree-data);void ino der_rec(Btree T) lin kstack S ;ini tstack( & S);Selem e;Btree p = T;while (p | !(S.cou nt = 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) ino der_