第九组数据结构课程设计(二叉排序树实现).doc

1、 黄淮学院“数据结构”课程设计报告系 （ 院）： 信息工程学院 设计题目： 二叉排序树的实现 专业班级： 软件工程 15 级 小组成员： 唐二虎、赵梦娟、贾月 指导教师： 汪洋 完成时间： 2016.12.27 1二叉排序树的实现1.设计任务1）实现二叉排序树，包括生成、插入，删除；2）对二叉排序树进行先根、中根、和后根非递归遍历；3）每次对树的修改操作和遍历操作的显示结果都需要在用树的形状表示出来。4）分别用二叉排序树和数组去存储一个班(50 人以上)的成员信息(至少包括学号、姓名、成绩 3 项),对比查找效率，并说明为什么二叉排序树效率高（或者低） 。2.程序设计流程图（设计思想）对二叉排

2、序树 T 作中序遍历,并输出结果二叉链表作存储结构和顺序表作存储结构输入数列 L， 以回车(n)为输入结束标志生成二叉排序树 T；找到该节点x存在含 x 的结点，则删除该结点，并作中序遍历无结点 x输入元素 x，查找二叉排序树 T2详细设计思想：建立二叉排序树采用边查找边插入的方式。查找函数采用递归的方式进行查找。如果查找到相等的则插入其左子树。然后利用插入函数将该元素插入原树。对二叉树进行中序遍历采用递归函数的方式。在根结点不为空的情况下，先访问左子树，再访问根结点，最后访问右子树。删除结点函数，采用边查找边删除的方式。如果没有查找到，进行提示；如果查找到结点则将其左子树最右边的节点的数据传

3、给它，然后删除其左子树最右边的节点。3.函数模块：3.1.主函数 main 模块功能1.通过 bstreeCreatTree()操作建立二叉排序树。2.在二叉排序树 t 中通过操作 bstreeInsertBST(bstreet,intkey,nametypename,double grade)插入一个节点。3. 从二叉排序树 t 中通过操作 void Delete(bstreetypedef stringnametype;typedef unsigned long keytype;typedefstruct node /结点的结构体keytype key; nametype name; in

4、t grade;5struct node *lchild,*rchild;bstnode;typedefbstnode *bstree;/栈的定义/typedefstruct bstree *base;bstree *top;intstacksize;Sqstack;intInitStack (Sqstacks.top=s.base;return 1;int Push(Sqstacks.top=s.top+1;return 1;int Pop(Sqstackelses.top=s.top-1;e=*s.top;return 1;/非递归历遍并输出结点信息/*-先序非递归遍历-*/voidx_p

5、rint(node *t)Sqstack s;InitStack(s);bstnode *p;p=t;while(p|!(s.top=s.base)if(p)6 Push(s,p);coutkeynamegradelchild;elsePop(s,p);p=p-rchild;/*-中序非递归遍历-*/voidz_print(node *t)Sqstack s;InitStack(s);bstnode *p;p=t;while(p|!(s.top=s.base)if(p) Push(s,p);p=p-lchild;elsePop(s,p);coutkeynamegraderchild;/*-非递

6、归后序遍历-*/voidh_print(node *t)7Sqstack s;InitStack(s);node *p,*q;p=t;q=NULL;while(p | !(s.top=s.base)if(p)Push(s,p);p=p-lchild;elsep=*(s.top-1);if(p-rchild=q)Pop(s,q);p=NULL;coutkeynamegraderchild;q=NULL;/递归查找二叉树/*-归查找，若找到就返回指向该结点的指针，否则返回空-*/bstnode *SearchBST(bstreet,keytype key) if(t=NULL|key=t-key)

7、return t;if(keykey)returnSearchBST(t-lchild ,key);elsereturnSearchBST(t-rchild ,key);/-给定学生信息插入到二叉树中-/bstreeInsertBST(bstreet,intkey,nametypename,double grade)bstreep,q;if(t=NULL) 8t=new bstnode();t-key=key;t-name=name;t-grade=grade;t-lchild=t-rchild=NULL;elsep=t;while(p) q=p;if(p-keykey)p=q-lchild;

8、else if(p-keyrchild;elsecoutkey=key;p-name=name;p-grade=grade;p-lchild=p-rchild=NULL;if(q-keykey)q-lchild=p;elseq-rchild=p;return t;/-二叉树排序树的构建-/bstreeCreatTree() bstree t=NULL;keytype key;nametype name;double grade;9printf(“n*本系统由二胡科技所有成员公同组建！*nnn“);printf(“请输入-学号-姓名-成绩-（输入 0 时结束）:n“);cinkey;if(key

9、=0)return t;cinname;cingrade;while(key) t=InsertBST(t,key,name,grade);printf(“请输入-学号-姓名-成绩-（输入 0 时结束）:n“);cinkey;if(key=0)break;cinname;cingrade;return t;/-删除树中的结点-/void Delete(bstreeif(!p-rchild)q=p;p=q-lchild ;delete q;else if(!p-lchild)q=p;p=p-rchild;delete q;elseq=p;s=p-lchild;while(s-rchild)q=s;