数据结构课程设计

广州大学松田学院。

数据结构。课程设计。

课程设计任务书。

学生姓名专业班级：

指导教师：严宇工作单位：广州大学松田学院

题目：完全二叉树的判别。

初始条件：试写一个判别给定二叉树是否为完全二叉树的程序。

1）此二叉树以二叉链表作存储结构；

2）自行设计正、反测试用例；

要求完成的主要任务：

课程设计报告按学校规定格式用a4纸打印，并应包含如下内容：

1. 问题描述。

简述题目要解决的问题是什么。

2. 设计。

存储结构设计、主要算法设计（用c语言或用框图描述）、测试用例设计。

3. 调试报告。

调试过程中遇到的问题是如何解决的；对设计和编码的讨论和分析。

4. 程序运行结果（包括对算法改进的设想）

5. 经验与体会。

6. 参考文献。

说明：1. 设计报告、程序不得相互抄袭和拷贝；若有雷同，则所有雷同者成绩均为0分。

时间安排：1、第17周完成。

年6月28号提交打印版课程设计，源程序刻录光盘。

指导教师签名年月日。

目录。1.问题分析与任务定义。

2.数据类型和系统设计。

2.1储存结构设计。

2.2主要算法设计。

2.2.1二叉树构造的算法。

2.2.2判定是否为完全二叉树的算法。

2.2.3测试用例设计。

2.2.4程序各模块之间的关系图。

3.程序调试。

3.1.对设计和编码的讨论和分析。

3.2调试。

4.程序运行结果。

5.经验与体会。

6.参考文献。

完全二叉树的判别。

1、问题分析与任务定义

该课程设计的题目为：完全二叉树的判别。也就是对于输入的。

二叉树进行判定，看是否为完全二叉树。

为实现此次课程设计的完成，对程序设计作了相应的定义与限制。首先，为了输入的简洁，将树的结点树不大于20；其次，对于二叉树的输入就按照前序遍历的顺序进行输入；最后，对于程序的测试，应该从正反两面进行测试，即输入一个是完全二叉树和一个不是完全二叉树的。

由于输入二叉树时，对于不是完全二叉树的，有的结点会没有左子树或右子树，甚至两子树都没有，为跟好的表示没有子树的情况，在此次程序设计中用“@”来表示。

对于此次的正反测试，分别用一下的两个二叉树进行测试：

a) 完全二叉树b) 非完全二叉树。

所以输入的顺序分别为：

正面测试：a b d @ e @ c f @

反面测试：a b d @ c e @ f @

2、数据类型和系统设计。

2.1储存结构设计。

根据设计的要求，对于本程序的储存结构要用二叉链表。

以下是作为本次设计数据的存储结构的定义：

template class binarytree;

template

class treenode

friend class binarytree;

private:

type1 data;

treenode* leftchild;

treenode* rightchild;

public:

treenode():leftchild(null),rightchlid(null){}

treenode(type1 item,treenode*left=null,treenode*right=null):data(item),leftchild(left),rightchild(right){}

type1 getdata()const

treenode* getleft()const

treenode*getright()const

return rightchlid;}

void setdata(const type1& item)

voidsetleft(treenode*left)

voidsetright(treenode*right)

rightchild=right;}

2.2主要算法设计。

2.2.1二叉树构造的算法。

对于二叉树的构造，可以运用插入建立，还可以用递归建立。在此次设计中运用的是递归建立。运用队列的进队函数进行对二叉树的结点的输入。

对于进队的第一个数据为二叉树的根结点，如果为非空，则继续输入第二个进队元素，将其设置为该根结点的左子树，然后将该左子树作为新的根结点，依次进行到下一层的结点，直至到达叶节点（即既没有左子树也没有右子树），然后对于这以后进队的元素则作为右子树，用相同的方法建树。

2.2.2判定是否为完全二叉树的算法

判定完全二叉树，首先要知道什么是完全二叉树，对完全二叉树定义以前，要明白满二叉树的定义。一棵深度为k且有2k-1个结点的二叉树称为满二叉树。对满二叉树的你借点进行连续编号，约定编号从根结点起，自上而下，自左而右。

由此引出完全二叉树的定义。深度为k的，右n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树的编号从1至n的结点一一对应时，称之为完全二叉树。所以对于二叉树的判定，假如某一结点有右子树但没有左子树则该树不是完全二叉树。

如果某一结点没有右子树或没有左子树，但是其后的结点有左子树或右子树，则该树不是完全二叉树。根据这种判定方法，可以判定其是不是完全二叉树。

2.2.3测试用例设计。

按照课程设计报告要求，要分别从正面和反面两个方面进行测试。所以分别用是完全二叉树的树和不是完全二叉树的树用其的前序遍历顺序输入，就可以完成设计要求。

2.2.4程序各模块之间的关系图。

程序模块关系图。

3.程序调试。

3.1对设计和编码的讨论和分析。

编码建立上一步详细设计结果的基础上，对编码进行调试。

3.2调试。

调试一向是我感觉很头疼的一个环节，因为程序中会因为各种各样的原因出现很多错误。所以在调试前应该做好充分的准备，比如说准备一本高级语言程序设计的教材以及先建立好工程和文件。

在设计中，我使用的是visual c++ 6.0为平台对程序进行调试。调试之前就是要把源程序输入进去，我建立了一个。cpp文件。

输完源**后对**进行编译，出现了诸多问题。比如说，会在语句后面丢掉分号、输入的标点符号不是英语输入中的而是中文输入中的、语法错误、函数调用不匹配的问题等等。对于这些错误需要相当大的耐性，但是都不难解决，只要细心的检查程序就可以更正了。

可以在调试错误中找到出错的地方，根据错误信息提示进行改错。对于有的错误提示并不明白是什么错误，也是通过查资料书和在网络上搜索到底是什么错误，在寻求解决方法。

在编译没有错误之后开始组建。

在组建出现了内存泄露，这是在编程中经常出现的问题。产生这种问题的原因也有很多种。大多数情况下就是指针出现错误。

于是我就开始检查程序中使用到指针的地方，进行检测，最后查出来问题并更正了。

调试没有错误以后，就是进行程序执行。

4.程序运行结果。

首先是正面测试结果：

然后是反面测试结果：

5.经验与体会。

其实此次的程序设计你还有很多需要改进的地方。比如说此次测试是一次性的可以加入while循环来完成我那个多次验证。加入while循环后程序运行结果如下：

还有本程序中没有destroy函数析构函数，这是个不足点，容易引起错误。还可以引入二叉树的print函数，将二叉树打印出来，更加的直观。

数据结构课程设计

数据结构课程设计

数据结构课程设计

数据结构课程设计

其他用户还读了