《计算机科学与技术课程设计》由会员分享，可在线阅读，更多相关《计算机科学与技术课程设计（19页珍藏版）》请在金锄头文库上搜索。
1、 一、课程设计题目 二叉平衡排序树摘要 问题描述：从一棵空树开始创立，在创立过程中，保证树的有序性，同时还要针对树的平衡性做些调整。最终要把创立好的二叉排序树转换为二叉平衡排序树。 根本要求：1.创立插入、调整、改组 开发工具:windows XP操作系统,Microsoft visual c+ 6.0 编译系统;关键词：C+ ; 二、设计主要目的及意义 目的:2.熟悉二叉树的创立(插入、调整、改组),输出以及把二叉排序树转换为二 叉平衡排序树3. 更进一步掌握有关二叉排序树的操作意义: 软件课程设计是计算机科学与技术专业软件方向的一个重要环节，是语言类课程学习的总结。通过课程设计使我们加深对
2、程序设计的理解，掌握程序开发的根本方法，深化学生面向对象的编程设计思想和新一代程序设计的逻辑思维方式，把课堂上所学到的多个单元串到一起，提高我们在软件设计过程中分析问题和解决问题的实际动手能力，使我们的理论知识和实践技能得到共同开展，最终提高我们解决问题和分析问题的能力。为我们踏上工作岗位之前提供了一次专业研究和工程开发的珍贵实践时机，为今后的工作积累经验。 三、 课程设计的过程主要算法说明:1. 主要数据结构定义 typedef struct node node ; Struct node Node*parent; Node*left; Node*right; Int balance;/左右
3、子树高度之差 Int key;2. 主要函数说明Int scarchNode(int key, node* root, node*parent):按key查找结点Node* minNode(node* root):树root的最小结点Node* maxNode(node* root):树root的最大结点Node* preNode(node* target):求前驱结点Node* nextNode(node* targer):求后继结点node* adjustAVL(node* root, node* parent, node* child);调整,保证二叉树的平衡性Node* insertN
4、ode(int key, node* root):插入Node* deletevode(int key, node* root):删除Node*createAVL(int* data, int size):创立新的二叉树Void interordertraverse (node*root):中序遍历Void preordertraverse(node* root):先序遍历3. 二叉排序树的插入和删除a. 二叉排序树的插入在二叉排序树插入新结点,要保证插入后的二叉树仍符合二叉排序树的定义插入过程:假设二叉排序树正存在,那么返回根结点;当结点不存在时,将待插入到根结点的关键字key和树根关键字p
5、arent-key 进行比拟.假设keykey,那么插入到根的左子树中,否那么,插入到根的右子树中.而子树中的插入过程和在树中的插入过程相同,如此进行下去,直到把结点作为一个新的树叶插入到二叉排序树中或者直到发现树已有相同关键字的结点为止,并且注意二叉树的平衡,时刻调整.假设在二叉排序树上被删结点为*tp,其双亲结点为*parent,且不失一般性,可设*parent是*parent-left的左孩子.下面分了3种情况进行讨论:(1) .假设*parent结点为叶子结点,即PL和PR均为空树.由于删去叶子结点不破坏整棵树的结构,那么只需要修改其双亲,结构点的指针即可.(2) .假设*parent
6、结点凡有左子树PL或者只有右子树PR,此时只要令PL或PR直接成为其双亲结点*f的左子树即可.显然,作此修改也不破坏二叉排序树的特性.(3) .假设*parent结点的左子树均不空,并且注意二叉树的平衡性,时刻调整.4. 中序遍历和先序遍历Void interordertraverse(node* root)/中序遍历 If(root 1=NULL) Interordertraverse(root-left); Printf(%d,%dn,root-key,root-balance); Interordertraverse(root-right); Void preordertraverse
7、(node* root)/先序遍历 If (root!=NULL)Printf(%d,%dn,root-key,root-balance);Preorderstraverse(root-left);Preorderstraverse(root-right); 5.动态平衡技术的概念Adelson-Velskii 和 Landis 提出了一个动态地保持二叉排序树平衡的方法，其根本思想是：在构造二叉排序树的过程中，每当插入一个结点时，首先检查是否因插入而破坏了树的平衡性，如果是因插入结点而破坏了树的平衡性，那么找出其中最小不平衡子树，在保持排序树特性的前提下，调整最小不平衡子树中各结点之间的连接关
8、系，以到达新的平衡。通常将这样得到的平衡二叉排序树简称为 AVL 树。为了保证二叉排序树的高度为lgn，从而保证二叉排序树上实现的插入、删除和查找等根本操作的平均时间为O(lgn)，在往树中插入或删除结点时，要调整树的形态来保持树的平衡。使之既保持BST性质不变又保证树的高度在任何情况下均为O(lgn)，从而确保树上的根本操作在最坏情况下的时间均为O(lgn)。6. 最小不平衡子树的概念以离插入结点最近、且平衡因子绝对值大于 1 的结点作根结点的子树。为了简化讨论，不妨假设二叉排序树的最小不平衡子树的根结点为 A ，那么调整该子树的规律可归纳为以下四种情况：图3平衡调整的4种根本类型结点旁的数
9、字是平衡因子1 LL 型：新结点 X 插在 A 的左孩子的左子树里。调整方法见图3a。图中以 B 为轴心，将 A 结点从 B 的右上方转到 B 的右下侧，使 A 成为 B 的右孩子。2RR 型：新结点 X 插在 A 的右孩子的右子树里。调整方法见图 3(b) 。图中以 B 为轴心，将 A 结点从 B 的左上方转到 B 的左下侧，使 A 成为 B 的左孩子。3LR 型：新结点 X 插在 A 的左孩子的右子树里。调整方法见图 3(c) 。分为两步进行：第一步以 X 为轴心，将 B 从 X 的左上方转到 X 的左下侧，使 B 成为 X 的左孩子， X 成为 A 的左孩子。第二步跟 LL 型一样处理
10、( 应以 X 为轴心 ) 。4RL 型：新结点 X 插在 A 的右孩子的左子树里。调整方法见图3(d) 。分为两步进行：第一步以 X 为轴心，将 B 从 X 的右上方转到 X 的右下侧，使 B 成为 X 的右孩子， X 成为 A 的右孩子。第二步跟 RR 型一样处理 ( 应以 X 为轴心 ) 。Node* adjustAVL(node* root,node* parent, node*child)主要有四种调整类型根据平衡因子主要有LR,LL,RL,RR.(1) 根据parent-balance的值为2时,child-balance =-1时是LR型,否那么为LL型.(2) Parent-ba
11、lance的值为-2时,child-balance =1时是RL型,否那么为RR型.8.程序代码设计：(代码局部详见附录)9. 运行界面运行界面如以下图所示:【注：运行时所执行的操作标注在截图的上方】选择1，输入序列13，24，37，90，53创立一刻二叉平衡树，以0为结尾；序列输入完成以后按回车，再选择4，中序输出该树；继续其它操作，选择2，插入一个新结点，其值为1，插入后选择4中序输出该树；继续其它操作，选择3删除一个结点，这里删除结点1，删除后先序输出该树；继续其它操作，输入6，6不是15中的树，程序自动退出；注：程序存在缺陷结点删除后的平衡问体，某种状态下删除特殊位置的结点会出现异常，
12、有待弥补。四、 重点及难点重点:1) 任一结点的左右子树的高度均相同(如满二叉树)，那么二叉树是完全平衡的。通常，只要二叉树的高度为O(1gn)，就可看作是平衡的。2) 平衡的二叉排序树指满足BST性质的平衡二叉树。3) AVL树中任一结点的左、右子树的高度之差的绝对值不超过1。在最坏情况下，n个结点的AVL树的高度约为1.44lgn。而完全平衡的二叉树度高约为lgn，AVL树是接近最优的。难点:平衡二叉树的生成是数据结构中一个重要的存储结构。由于本程序的输入较多，所以输入数据时必须小心细致。本程序比拟复杂，需要使用结构体并使用了指针。必须将程序分解为多个子程序以降低编写难度。想起了软工老师的
13、一句话：难事破与易，再复杂的事，拆成一个个简单的小局部，逐个击破，在拼凑起来，复杂的事也变的简单了。适当使用全局常量可以控制有效控制内存溢出。由于程序较大，调试时多人协作能更容易易找出程序并成功修改。五、 主要结论通过平衡二叉树的生成程序的设计，我们很好的理解了平衡二叉树的生成和各项操作的相关知识，同时还较好的掌握了动态查找相关概念。 六、致谢本课程设计的完成，首先感谢母校河北工程大学的辛勤培育之恩。本系统是在刘云老师直接指导下完成的，刘老师从论文的选题，设计方案的安排到具体功能的实现，以及说明书的撰写直至定稿的全过程都给予了精心的指导和严格的要求，对本论文的最后完成给予了莫大的帮助。在设计过
14、程中刘云老师在百忙中挤出时间屡次给予指导，提出了许多珍贵的修改意见。在这里首先要感谢刘云老师。其次要感谢程天明和付向飞同学，他们利用自己的珍贵时间与我一起研究系统的设计方面的问题，并且结合自己的经验，给我提出的珍贵的意见和建议，使我的系统得以进一步的完善。在此也向他们表示由衷的感谢。然后还要感谢大学以来所有的老师，为我们打下计算机专业知识的根底；同时还要感谢所有的同学们，正是因为有了你们的支持和鼓励。此次课程设计才会顺利完成。七、参考文献1 王春红，梁普选，王建亮. Delphi程序开发. 北京：机械工业出版社 20032 张基温，杨晓玲. Visual Basic程序开发教程.北京：清华大学出版社，20043 陈俊源. Delphi程序设计实用教程. 北京：电子工业出版社， 20004 段兴. Delphi 7程序设计教程M. 北京：清华大学出版社， 2003 5 张宏林，陆华，王思学. Delphi6 编程指南M. 北京：人民邮电出版社，2000 八、 附录：程序清单 #include #include /cout#include /setw
