数据结构课程设计---二叉排序树和平衡二叉树的判别
《数据结构课程设计---二叉排序树和平衡二叉树的判别》由会员分享,可在线阅读,更多相关《数据结构课程设计---二叉排序树和平衡二叉树的判别(8页珍藏版)》请在毕设资料网上搜索。
1、二叉排序树和平衡二叉树的判别二叉排序树和平衡二叉树的判别 1 引言引言 数据结构是软件工程的一门核心专业基础课程, 在我们专业的课程体系中起 着承上启下的作用, 学好数据结构对于提高理论认知水平和实践能力有着极为重 要的作用。学习数据结构的最终目的是为了获得求解问题的能力。对于现实世界 中的问题,应该能从中抽象出一个适当的数据模型,该数学模型在计算机内部用 相应的数据结构来表示,然后设计一个解此数学模型的算法,在进行编程调试, 最后获得问题的解答。 本次课程设计的题目是对二叉排序树和平衡二叉树的扩展延伸应用。 首先我 们得建立一个二叉树,二叉树有顺序存储结构和链式存储结构两种存储结构,此 次我
2、选用的是二叉链表的存储结构。对于判断平衡二叉树,需要求出其每个叶子 结点所在的层数,这里我采用的边遍历边求的方式,遍历采用的是先序遍历。二 叉树的建立以及二叉排序树和平衡二叉树的判别中都用到了递归思想。 2 2 需求分析需求分析 2.12.1在日常生活中,人们几乎每天都要进行“查找”工作。所谓“查找”即为 在一个含有众多的数据元素(或记录)的查找表中找出某个“特定的”数据元素 (或记录) ,即关键字。 2.22.2本程序意为对一个已经建立的动态查找表二叉树判断其是否是二 叉排序树和平衡二叉树。 3 3 数数据结构设计据结构设计 3.13.1抽象数据类型二叉树的定义如下: ADT BinaryT
3、ree 3.1.13.1.1数据对象 D:D 是具有相同特性的数据元素的集合。 3.1.23.1.2数据关系 R: 若 D=NULL,则 R=NULL,称 BinaryTree 为空的二叉树; 若 D!=NULL,则 R=H,H 是如下的二元关系: 3.1.2.13.1.2.1 在 D 中存在唯一的称为根的数据元素 root,它在关系 H 下无前驱; 3.1.2.23.1.2.2 若 D-root!=NULL,则存在 D-root=Dl,Dr,且 Dl 与 Dr 相交为空; 3.1.2.33.1.2.3 若 Dl!=NULL,则 Dl 中存在唯一的元素 xl,属于 H,且存在 Dl 上的关系
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中设计图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 课程设计 二叉排序树 平衡 二叉 判别
