课程设计说明书

《完全二叉树的判断》

课程设计**。

学生姓名。学号。

所属学院信息工程学院

专业计算机科学与技术

班级计算机

指导教师。教师职称讲师。

目录。前言 1

正文 22.1课程设计任务及要求 2

2.2课程设计思想 2

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

2.4功能模块说明 3

2.5编码设计 4

2.6调试 5

2.7程序运行结果 6

课程设计总结 9

参考文献 10

附录 11在计算机科学中，二叉树是每个结点最多有两个子树的有序树。通常子树的根被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用作二叉查找树和二叉堆或是二叉排序树。

二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2的 i -1次方个结点；深度为k的二叉树至多有2^(k) -1个结点；对任何一棵二叉树t，如果其终端结点数(即叶子结点数)为n0，度为2的结点数为n2，则n0 = n2 + 1。

二叉树也是递归定义的，其结点有左右子树之分，逻辑上二叉树有五种基本形态：

1)空二叉树——(a)；

2)只有一个根结点的二叉树——(b)；

3)只有左子树——(c)；

4)只有右子树——(d)；

5)完全二叉树——(e)

完全二叉树：

若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层有叶子结点，并且叶子结点都是从左到右依次排布，这就是完全二叉树。

满二叉树。除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。

深度：二叉树的层数，就是高度。

先序遍历：

先序遍历也叫做先根遍历、前序遍历，可记做根左右（二叉树父结点向下先左后右）。首先访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树，如果二叉树为空则返回。

例如，下图所示二叉树的遍历结果是：abdecf

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

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

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

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

在计算机科学中，二叉树是每个结点最多有两个子树的有序树。通常子树的根被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用作二叉查找树和二叉堆或是二叉排序树。

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

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

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

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

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

完全二叉树定义：

若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。完全二叉树是由满二叉树而引出来的。对于深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。

若一棵二叉树至多只有最下面的两层上的结点的度数可以小于2，并且最下层上的结点都集中在该层最左边的若干位置上，则此二叉树成为完全二叉树。

用c语言的方法实现完全二叉树的判断算法：

/完全二叉树判断函数。

/先利用队列找出二叉树中第一个没有包含两个孩子的节点（即第一个非正常节点）

/从第一个非正常节点后面开始出队的所有节点均不含子节点则该二叉树为完全二叉树。

int completebinarytree(bitree root)

int flag;

linkqueue binode;//创建队列。

initqueue(&binode);/初始化队列。

enterqueue(&binode,root);/将根节点入队。

while(当队列不为空时进行广度优先扫描二叉树。

/当发现非正常节点时跳出循环。

if(>next->data->lchild!=null&&>next->data->rchild!=null)

//当左右孩子均有。

elsebreak;

程序各模块之间的关系图：

图1程序模块关系图。

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

在计算机硬件中，编码（coding）是指用**来表示各组数据资料，使其成为可利用计算机进行处理和分析的信息。**是用来表示事物的记号，它可以用数字、字母、特殊的符号或它们之间的组合来表示将数据转换为**或编码字符，并能译为原数据形式。是计算机书写指令的过程，程序设计中的一部分。

在地图自动制图中，按一定规则用数字与字母表示地图内容的过程，通过编码，使计算机能识别地图的各地理要素。 n位二进制数可以组合成2的n次方个不同的信息，给每个信息规定一个具体码组，这种过程也叫编码。数字系统中常用的编码有两类，一类是二进制编码，另一类是二—十进制编码。

下面分三种情况讨论：

/左孩子没有右孩子没有，继续扫描。

if(>next->data->lchild==null&&>next->data->rchild==null)

deletequeue(&binode);

while(

return true;

/左孩子有右孩子没有，继续扫描。

else if(>next->data->lchild!=null&&>next->data->rchild==null)

enterqueue(&binode,>next->data->lchild);

deletequeue(&binode);

while(

return true;

/左孩子没有右孩子有，非完全二叉树。

else if(>next->data->lchild==null&&>next->data->rchild!=null)

return false;

/队列的初始化函数。

int initqueue(linkqueue *q)

/将q初始化为一个空的链队列。

q->front=(linkqueuenode *)malloc(sizeof(linkqueuenode));

if(q->front!=null)

q->rear=q->front;

课程设计说明书

课程设计说明书

课程设计说明书

课程设计说明书

其他用户还读了