二叉排序树及平衡二叉排序树基本操作实现.docx

《二叉排序树及平衡二叉排序树基本操作实现.docx》由会员分享，可在线阅读，更多相关《二叉排序树及平衡二叉排序树基本操作实现.docx（15页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、二叉排序树及平衡二叉排序树基本操作实现0/15编编号：号：B04900083课课 程程 设设 计计学学号：号：2教教 学学 院院计算机学院课程名称课程名称数据结构及算法题题目目二叉排序树及平衡二叉排序树基本操作的实现专专业业计算机科学及技术班班级级二班姓姓名名同组人员同组人员指导教师指导教师成俊2015 年12 月27日二叉排序树及平衡二叉排序树基本操作实现1/15课程设计任务书课程设计任务书20152016学年 第 1 学期学生姓名学生姓名:专业班级：专业班级：计科二计科二指导教师：指导教师：成俊成俊工作部门：工作部门：计算机学院计算机学院一、课程设计题目一、课程设计题目:二叉排序树及平衡二

2、叉排序树基本操作二、课程设计内容二、课程设计内容用二叉链表作存储结构,编写程序实现二叉排序树上的基本操作:以回车（n）为输入结束标志,输入数列 L，生成二叉排序树 T；对二叉排序树 T 作中序遍历；计算二叉排序树 T 的平均,输出结果；输入元素 x，查找二叉排序树T，若存在含 x 的结点，则删除该结点,并作中序遍历；否则输出信息“无结点x”；判断二叉排序树 T 是否为平衡二叉树；再用数列 L，生成平衡二叉排序树BT:当插入新元素之后，发现当前的二叉排序树 BT 不是平衡二叉排序树,则立即将它转换成新的平衡二叉排序树 BT；计算平衡的二叉排序树 BT 的平均查找长度,输出结果.三、进度安排三、进

3、度安排1分析问题，给出数学模型,选择数据结构。2设计算法，给出算法描述3给出源程序清单4.编辑、编译、调试源程序5.撰写课程设计报告四、基本要求四、基本要求编写 AVL 树判别程序，并判别一个二叉排序树是否为 AVL 树。二叉排序树用其先序遍历结果表示，如：5，2，1,3，7，8。实现 AVL 树的 ADT,包括其上的基本操作：结点的加入和删除;另外包括将一般二叉排序树转变为 AVL 树的操作。实现提示主要考虑树的旋转操作.二叉排序树及平衡二叉排序树基本操作实现2/15目录目录一、课程设计题目:二叉排序树及平衡二叉排序树基本操作.1二、课程设计内容.1三、进度安排.1四、基本要求.1一、概述.

4、31。课程设计的目的.32。课程设计的要求.3二、总体方案设计.4三、详细设计.61。课程设计总体思想.62.模块划分.73。流程图.8四、程序的调试及运行结果说明.9五、课程设计总结.14参考文献.14二叉排序树及平衡二叉排序树基本操作实现3/15一、概述一、概述1 1。课程设计的目的。课程设计的目的1.充分理解和掌握二叉树、平衡二叉树的相关概念和知识。2.掌握排序二叉树的生成、结点删除、插入等操作过程。3.并实现从键盘上输入一系列数据（整型），建立一棵平衡二叉树。4.任意插入或删除一个结点后判断是否为平衡二叉树。5将非平衡二叉树转换成平衡二叉树。6.按中序遍历输出这棵平衡二叉树.2.2.课

5、程设计的要求课程设计的要求用二叉链表作存储结构，编写程序实现二叉排序树上的基本操作：以回车（n)为输入结束标志,输入数列 L,生成二叉排序树 T；对二叉排序树 T 作中序遍历;计算二叉排序树 T 的平均查找长度,输出结果；输入元素 x，查找二叉排序树 T,若存在含 x 的结点，则删除该结点，并作中序遍历；否则输出信息“无结点 x；判断二叉排序树 T 是否为平衡二叉树;再用数列 L,生成平衡二叉排序树 BT:当插入新元素之后，发现当前的二叉排序树 BT 不是平衡二叉排序树,则立即将它转换成新的平衡二叉排序树BT；计算平衡的二叉排序树BT的平均查找长度，输出结果.编写 AVL 树判别程序，并判别一

6、个二叉排序树是否为 AVL 树。二叉排序树用其先序遍历结果表示,如：5，2，1，3，7，8。实现 AVL 树的 ADT,包括其上的基本操作：结点的加入和删除；另外包括将一般二叉排序树转变为 AVL 树的操作.实现提示主要考虑树的旋转操作。二叉排序树及平衡二叉排序树基本操作实现4/15二、总体方案设计二、总体方案设计1）建立二叉排序树,编写二叉排序树 T 作中序遍历.2）查找删除二叉排序树函数。3）编写判断二叉排序树 T 是否为平衡二叉树函数，把非平衡二叉排序树转换成平衡二叉排序树。4）编写计算二叉树 BT 的平均查找长度函数。我负责的是第一部分，二叉排序树或者是一棵空树，或者是具有下列性质的二

7、叉树：1.若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值；2.若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；3。它的左、右子树也分别为二叉排序树。以链表存储结构创建二叉排序树，以回车(n）为输入结束标志,输入数列 L，生成二叉排序树 T；对二叉排序树 T 作中序遍历。中序遍历二叉树算法的框架是：若二叉树为空，则空操作;否则(1）中序遍历左子树（L）；（2)访问根结点（V）;(3）中序遍历右子树（R)。函数 1:中序遍历二叉树中序遍历二叉树也采用递归函数的方式，先访问左子树 2i，然后访问根结点 i，最后访问右子树 2i+1。先向左走到底再层层返回，直至所有的结点都

8、被访问完毕。（谢石林)函数 2:平均查找长度计算二叉排序树的平均查询长度时，可采用类似中序遍历的递归方式，用 s 记录总查询长度，j 记录每个结点的查询长度，s 值初值为 0,采用累加的方式最总得到总查询长度 s，平均查询长度等于 s/i（i 为树中结点个数）。（吴进）函数 3：查找删除二叉排序树函数输入元素 x，查找二叉排序树 T，若存在含 x 的结点,则删该结点,并作中序遍历（执行函数 1)；否则输出信息“无 x”。（张常勋）函数 4：判断二叉排序树 T 是否为平衡二叉树，若不是则用数列 L,生成平衡排序二叉树 BT；最后调用函数 6，接着调用函数 5.判断二叉排序树是否为平衡二叉树的函数

9、也是采用递归函数的方式，分别判定以树中每个节点二叉排序树及平衡二叉排序树基本操作实现5/15为根节点的子树是否为平衡二叉树。只要有一个子树不为平衡二叉树，则该树便不是平衡二叉树.函数 5：在平衡二叉树 BT 上插入新元素,若发现当前的二叉排序树 BT 不是平衡二叉排序树，则立即将它转换成新的平衡二叉排序树 BT。二叉排序树及平衡二叉排序树基本操作实现6/15三、详细设计三、详细设计1 1。课程设计总体思想。课程设计总体思想1。生成二叉排序树：建立二叉排序树采用的是边查找边插入的方式。查找函数采用递归的方式进行查找。查找是按照二叉排序树的性质进行的，通过比较要插入元素的关键字及当前结点关键字的大

10、小来决定我们是遍历当前结点的哪个子树.如果小于当前结点关键字，则遍历它的左子树；大于当前结点关键字,则遍历它的右子树；等于当前关键字，则此元素不插入原树。我们按照这样的规律，一直向下遍历，知道它的子树为空，则返回当前结点的上一个结点。然后利用插入函数将该元素插入原树。2。中序遍历：对二叉排序树进行中序遍历采用递归函数的方式。在根节点不为空的情况下,先访问左子树,在访问根结点，最后访问右子树。3.平均查找长度：计算二叉排序树的平均查找长度，仍采用类似中序遍历的递归方式，用 s记录总查找长度,j 记录每个结点的查找长度,s 置初值为 0，采用累加的方式最终得到总查找长度 s，平均查找长度就等于 s

11、/j（i 为树中结点的总个数）。4。删除结点：删除结点函数，采用边查找变删除的方式.如果没有查找到，则不对树做任何的修改：如果查找到结点，则分四种情况分别进行讨论：（1）该结点左右子树均为空；（2）该结点仅左子树为空;（3）该结点仅右子树为空；(4)该结点左右子树都不为空；5用数列 L，生成平衡的二叉排序树 BT;当插入新元素之后，发现当前的二叉排序树 BT 不是平衡二叉排序树，则立即将它转换成新的平衡的二叉排序树 BT。我所负责的模块函数定义如下void TraverseOrderDSTable(BSTree DT，void(*Visit）（ElemType）/按中序遍历详细的程序代码如下：

12、typedef struct BSTNode/二叉排序树类型 ElemType data;二叉排序树及平衡二叉排序树基本操作实现7/15struct BSTNode*lchild,rchild;BSTNode,BSTree;Status InitDSTable（BSTree&DT）/构造一个空的动态 BST 查找表 DTDT=NULL；return 1;void TraverseOrderDSTable(BSTree DT,void(*Visit)(ElemType)/按中序遍历对 DT 的每个结点调用函数 Visit()一次且至多一次if（DT)TraverseOrderDSTable(DT

13、lchild，Visit）；Visit（DTdata)；TraverseOrderDSTable(DTrchild，Visit);2 2。模块划分。模块划分Main:主函数模块，在主函数中调用其他函数：（1）Status InsertBST(BSTree&T,ElemType e）/创建二叉排序树（2）void TraverseOrderDSTable(BSTree DT,void(Visit)(ElemType）void TraverseOrderDSTable（AVLTree DT，void(*Visit）（ElemType）)/中序遍历二叉排序树和平衡二叉排序树(3）void asl(）

14、/计算平均长度（4)BSTree SearchBST(BSTree T,KeyType key）void SearchBST(BSTree T，KeyType key，BSTree f,BSTree&p，Status&flag)void Delete（BSTree p）Status DeleteBST(BSTree&T，KeyType key)/查找并删除结点（5）Status InsertAVL(AVLTree T，ElemType e，Status taller）/创建平衡二叉排序树void RightBalance(AVLTree T）/对以p 为根的二叉排序树作右旋处理，处理之后 p

15、指向新的树根结点,即旋转处理之前的左子树的根结点void LeftBalance（AVLTree T)/对以*p 为根的二叉排序树作左旋处理，处理之后 p 指向新的树根结点，即旋转处理之前的右子树的根结点二叉排序树及平衡二叉排序树基本操作实现8/15AVLTree SearchAVL(AVLTree T，KeyType key)/衡二叉排序树中进行查找.3.3.流程图流程图二叉排序树及平衡二叉排序树基本操作实现9/15四、程序的调试及运行结果说明四、程序的调试及运行结果说明主函数代码：void main（)int num,i，select,t，*depth,max，flag;KeyType j

16、;Status k;ElemType r,*tempr,tempbst,tempavl；BSTree bst,p；AVLTree avl,q;doprintf（”请输入要输入的数据的总数，总数要大于 0:);scanf(d”,&num）;if(num=0）printf(”n 输入的总数要大于 0，请重新输入：”);while（num=0);gl_count=num;r=（ElemType*）malloc（gl_count*(sizeof(ElemType)）)；printf(请输入生成二叉树的整型数据，前后数据用空格隔开:n”）；for(i=0;igl_count;i+)scanf（”%d”,

17、&ri.key)；ri.order=i+1；printf（”n 用户输入的数据及序号如下：n”）;for(i=0；i gl_count;i+)print（ri）；if(（i+1)%6=0)printf(”n）;select=0；flag=0；InitDSTable（bst);for(i=0;igl_count；i+）InsertBST（bst,ri);printf（”n 按中序遍历该二叉排序树的结果如下：n);TraverseOrderDSTable（bst，print）；cout endlendl”以下是对二叉排序树的基本操作:”endl1。查找一个节点 endl”2。插入一个节点”endl

18、二叉排序树及平衡二叉排序树基本操作实现10/153。删除一个节点endl”4。判别二元查找树是否为平衡二叉树”endl5.二叉树转换为平衡二叉树”endl6。退出系统”endl;doif（flag=6）;printf（n 请输入二叉排序树基本操作的选项：)；scanf（”%d”,&select)；switch（select)case 1:printf（”请输入待查找的数据:”）;scanf（d，&j）;p=SearchBST（bst，j）;if（p）printf（”n 二叉排序树中存在此值：”)；print(pdata）；elseprintf(n 二叉排序树中不存在此值.”)；break；ca

19、se 2:printf(”请输入需插入的数据：）;scanf（”%d,&j）;p=SearchBST（bst,j）;if(p)printf（”n 二叉排序树中存在此值：”）;print（p data)；elsetempr=(ElemType）（malloc(gl_count*sizeof(ElemType)）;for（i=0；i gl_count；i+)tempr i。key=ri.key;tempri。order=ri.order；tempbst。key=j；tempbst.order=+gl_count;r=(ElemType)(malloc（gl_countsizeof（ElemType

20、)）)；for(i=0;i gl_count-1;i+）二叉排序树及平衡二叉排序树基本操作实现11/15ri。key=tempri.key;ri。order=tempri.order；ri。key=tempbst.key;ri。order=tempbst.order；InsertBST（bst，tempbst）；printf（”数据已经插入二叉排序树中。)；printf（n 按中序遍历该二叉排序树的结果如下:n”);TraverseOrderDSTable（bst,print）；break;case 3:printf（”请输入需删除的数据：”）；scanf(”d”,&j);p=SearchBS

21、T（bst，j）;if(p)tempr=(ElemType ）（malloc（gl_count sizeof（ElemType）)；for(i=0；i gl_count；i+)tempri。key=ri。key；tempri.order=ri.order；DeleteBST（bst，j）；gl_count;r=(ElemType*）（malloc（gl_countsizeof(ElemType)）；for（i=0,t=0；i gl_count;i+)if(tempri.key!=j)rt。key=tempri.key;rt.order=tempri。order;t+;printf(”二叉排序树

22、中该数据已经删除。”）;TraverseOrderDSTable（bst,print）；elseprintf(需删除的数据不存在于二叉树中。”)；break；case 4:depth=(int）malloc（gl_count*（sizeof（int)）；二叉排序树及平衡二叉排序树基本操作实现12/15BST_DepthDiff（bst,depth）;max=depth0;for(i=1；igl_count;i+)if（max depthi）max=depthi；if(max 2)printf（”n 该二叉排序树是平衡二叉树。);else printf（n 该二叉排序树不是平衡二叉树。）;if（

23、max 4）printf（”n 该二叉排序树有结点的左右子树之差大于 4,系统建议您将该二叉排序树转换成平衡二叉树.);break；case 5:InitDSTable(avl)；for(i=0；i gl_count；i+）InsertAVL（avl，ri,k）;printf(”该二叉排序树转换成了平衡二叉树”）；TraverseOrderDSTable(avl，print);flag=6;break;case 6：break；default:printf(”您输入的选项是错误的，请重新输入！);break;while（select！=6);初始提示输入节点数；输入数据用空格符隔开；随后系统会

24、自动对数据进行中序遍历；功能菜单；二叉排序树及平衡二叉排序树基本操作实现13/15执行节点的查找功能；执行插入功能；执行删除功能；判断是否为平衡二叉树如果不是可执行转换功能.二叉排序树及平衡二叉排序树基本操作实现14/15五、课程设计总结五、课程设计总结本次的数据结构课程设计,让我们独立完成一个小系统，组员们从选题到任务分派，都全身心投入。在本次数据结构课程实验中,我们一方面对数据结构有了更好的认识,对数据结构语法上面的知识有了一个应用性的复习，同时对文件操作有了更好的学习，另一方面组员们对编程的一些良好习惯也有了认识，编程上的细节处理也有了了解，总之这次训练让我学到很多，对自己也是一个考验和

25、锻炼。通过这次数据结构实训，我们不仅巩固了课本中所学习的知识，还加强了对知识的运用能力,学会了如何用多种方法解决问题，同时也激发了我们对数据结构的学校兴趣，相信在以后应用中我们会去的更好的成绩，利用 VC 知识去修改、编写更多的程序去解决生中的问题,为人们的衣食住行提供方便。这次课程设计，我们组内先分配了各自的任务，然后分别执行。这种方式让我们思路清晰，使设计过程简单化快捷化，且让我们认识到了团队合作的重要性。在这次程序设计中，我负责的是主函数和二叉排序树的创建。刚得到任务时，确实不知从何处搞起，通过不断学习和请教他人，我逐渐摸清了思路，最后搞出来了。说白了,就是采用边建立二插排序树采用边查找边插入的方式.查找函数采用递归的方式进行查找.如果查找成功则不应再插入原树，否则返回当前结点的上一个结点.然后利用插入函数将该元素插入原树。就是这么简单。对函数的构造以及调用有了更进一步的掌握，让我在调试 程序是有了一定的经验。多考虑算法的可行性。在遇到问题是认真考虑.同时让 我意识到数据结构在编程中的重要作用.算法的优越性对程序的重要性.让我在 调试程序是有了一定的经验。参考文献参考文献1 谭浩强，C 程序设计题解及上机指导（第二版），北京，清华大学出版社,2000 年 9月。2 李春葆。数据结构习题及解析M。2 版.北京：清华大学出版社，2004 附录