二叉树--数据结构课程设计报告

武汉纺织大学

数学与计算机学院

数据结构课程设计报告

二叉树的编码

学生姓名： 学号： 班级： 指导老师： 报告日期：年月日

1 题目与要求

1.1 问题提出

其中，x，y是两个整数坐标，采用由上至下和从左到右的方法对这些坐标进行赋值；size表示结点所有子孙结点的个数；depth表示结点的层次。如下图所示：

A（1，22，10，1）括号内数值含义（x，y，size，depth）B（2，11，4，2）C（12，21，4，2）D（3，10，3，3）E（13，14，0，3）F（15，20，2，3）G（4，5，0，4）H（6，9，1，4）I（16，19，1，4）J（7，8，0，5）

K（17，18，0，5）要求利用所学的知识编写代码创建二叉树，求x,y,size,depth的值，并完成相应的操作，掌握二叉树的基本知识！

1.2 本系统涉及的知识点

涉及的相关知识点： 1.二叉树的先序建立 2.递归算法 3.队列

4.逆中序输出结点 5.二叉树的遍历 6.凹入法

1.3 功能要求

实现的主要功能：

⑴根据课本“算法6.4”建立上图所示的二叉树，并且对每个结点的（x，y，size，depth）都赋零值，即（0，0，0，0）。 ⑵编写算法求每个结点的（x，y）。 ⑶编写算法求每个结点的size。

⑷编写算法求每个结点的depth。

⑸求二叉树中分支结点和叶子结点的数目。

⑹二叉树的繁茂度定义为各层结点数的最大值与树的深度的乘积，求二叉树的繁茂度。

⑺编写算法判别给定二叉树是否为完全二叉树。 ⑻按中序凹入法显示二叉树。 ⑼对二叉树进行层序遍历。 ⑽销毁二叉树中的所有结点，要求在销毁每一个结点前，输出该结点的数据域。

2 功能设计

2.1 数据结构定义

二叉树的二叉链表存储表示如下： typedefstructBiNode {

char data;

int x, y, size, depth;

structBiNode *lchild, *rchild; }BiNode, *BiTree;

2.2 模块图

1.建立二叉树并赋零值 2.求每个结点的（x，y） 3.求每个结点的size 4.求每个结点的depth 5.分支结点和叶子结点的数目 6.求二叉树的繁茂度 7.判别是否为完全二叉树 8.中序凹入法显示二叉树 9.对二叉树进行层序遍历 10.销毁二叉树的结点 二叉树的操作

3 程序代码设计

#include \#include \typedefstructBiNode {

char data;

intx,y,size,depth;

structBiNode *lchild,*rchild; }BiNode,*BiTree; int max,max1,max2; BiTreecreat(BiTree T) {

char c;

scanf(\ if(c=='#') T=NULL;

else { T=(BiTree)malloc(sizeof(BiNode)); T->data=c; T->x=0; T->y=0; T->size=0; T->depth=0; printf(\请输入%c结点的左子结点:\ fflush(stdin); T->lchild=creat(T->lchild); printf(\请输入%c结点的右子结点:\ fflush(stdin); T->rchild=creat(T->rchild); } return T; }

void degree(BiTree T)//求二叉树的各层结点树的最大值 {

BiTreeTree[30]; int n=1,i=0,flag; if(T->y==0) {

Tree[i]=T; Tree[i]->x=n;

Tree[i]->depth=i+1; max=Tree[i]->depth; i++;n++; while(i>=1) { flag=0; while(Tree[i-1]->lchild!=NULL) { Tree[i]=Tree[i-1]->lchild; if(Tree[i]->y==0) { Tree[i]->x=n; Tree[i]->depth=i+1; max=max>Tree[i]->depth?max:Tree[i]->depth;

本文来源：https://www.bwwdw.com/article/6lid.html