二叉树基本操作演示程序的设计与实现

数据结构课程设计报告

XXX大学 电子与信息工程学院 数据结构课程设计报告

( 2012——2013年度第一学期)

课程名称： 数据结构课程设计 题 目 ：6.2二叉树的基本操作演示程序 院 系： 计算机科学系 班 级： 10软件本二班 姓 名： X X 学 号： 100913005 指导教师： 孙凌宇老师 成 绩：

2012 年 月 日

1

数据结构课程设计报告

成 绩 评 定

一、 指导教师评语

二、 成绩

成绩 备注

指导教师： 日 期： 年 月 日

2

数据结构课程设计报告

设计题目<一>：6.2二叉树基本操作演示程序的设计与实现 一、设计要求 1．问题描述

设计一个与二叉树基本操作相关的演示程序。

2．需求分析

（1）创建二叉树。按照用户需要的二叉树，构建二叉树。 （2）将创建的二叉树，以树状形式输出。

（3）分别以先序、中序、后序三种遍历访问二叉树。 （4）输出二叉树的叶子结点及叶子结点的个数。 （5）输出二叉树的高度。

二、概要设计

为了实现以上功能，可以从3个方面着手设计。

1． 主界面设计

为了实现二叉树的相关操作功能的管理，设计一个含有多个菜单项的主控菜单子程序以链接系统的各项子功能，方便用户使用本程序。 本程序主控菜单运行界面如图1所示。

图1“二叉树基本操作程序”主菜单

3

数据结构课程设计报告

2．存储结构设计

本程序采用二叉链式存储类型（BiTNode）存储二叉树的结点信息。二叉树的链表中的结点至少包含3个域：数据域（data）、左孩子指针域（Lchild）、和右孩子指针域（Rchild）。

3．系统功能设计

本程序除了完成二叉树的创建功能外还设置了8个子功能菜单。由于这8个子功能都是建立在二叉树的构造上的，所以二叉树的创建由主函数main（）实现。8个子功能的设计描述如下：

(1) 树状输出二叉树。树状输出二叉树有函数TranslevePrint（）实现。当用户选择该功能时，系统即以树状的形式输出用户所创建的二叉树。

(2)先序遍历二叉树。由函数PreOrder（）实现。该功能按照先序遍历访问二叉树的方法输出先序遍历序列。

(3)中序遍历二叉树。由函数InOrder（）实现。该功能按照中序遍历访问二叉树的方法输出中序遍历序列。

(4)后序遍历二叉树。由函数PostOrder（）实现。该功能按照后序遍历访问二叉树的方法输出后序遍历序列。

(5)输出叶子结点。该功能采用先序遍历二叉树的方法，依次输出叶子结点。由函数PreOrderLeaf（）实现。

(6)输出叶子结点个数。该功能计算并输出二叉树中叶子结点的个数，由LeafCount（）函数实现。采用递归算法计算二叉树中叶子结点的个数，算法思想是：当二叉树为空树时，叶子结点总数为0；当二叉树只有一个结点时，叶子结点个数为1；否则，叶子结点个数等于左、右子树叶子结点数之和。

(7)输出二叉树的深度。该功能即输出二叉树结点所在层次的最大值。由函数PostTreeDepth（）实现，采用后序遍历的递归算法求二叉树的深度。

(8)退出。由exit（0）函数实现。

三、模块设计 1．模块设计

本程序包含三个模块：主程序模块、建立二叉树模块和工作区模块。其调用关系如图2所示。

4

数据结构课程设计报告

主程序模块 建立二叉树模块 工作区选择模块

图2 模块调用示意图

2．系统子程序及功能设计

本系统共设置11个子程序，各子程序的函数名及功能说明如下： (1) void CreateBiTree(BiTree *bt) //建立二叉树 (2) void TranslevelPrint(BiTree bt) //树状打印二叉树 (3) void Visit(char ch) //输出结点 (4) void PreOrder(BiTree root) //先序遍历二叉树 (5) void InOrder(BiTree root) //中序遍历二叉树 (6) void PostOrder(BiTree root) //后序遍历二叉树 (7) void PrePrderLeaf(BiTree root) //输出叶子结点 (8) int LeafCount(BiTree root) //输出叶子结点的个数 (9) int PostTreeDepth(BiTree root) //输出二叉树的深度

(10) void mainwork( ) //主要工作函数。操作区用户界面

(11) void main( ) //主函数。创建二叉树。调用工作区模块函数

3．函数主要调用关系图

本系统11个子程序之间的主要调用关系如图3所示。图中数字是各函数的编号。

5

数据结构课程设计报告

11 main() 10 mainwork() 1 2 4 5 6 7 3 图3 系统函数调用关系图

四、详细设计 1．数据类型定义

Typedef struct BiTNode //定义二叉树结点结构 ｛ char data; //数据域

struct BiTNode *LChild, *RChild; //左右孩子指针域 ｝

2．系统主要子程序详细设计

(1) 主函数模块设计

主函数，创建二叉树，调用工作区模块函数 void main() { printf(\首先请输入二叉树的结点序列：\ printf(\【提示：用@隔离】\\n\ CreateBiTree(&T);

printf(\【零式提醒】看下面的菜单哦：\\n\ mainwork ();

}

6

8 9 数据结构课程设计报告

(2) 建立二叉树模块

该模块是实现工作区模块的基础，工作区模块实现的8个子功能菜单都建立在此模块之上. void CreateBiTree(BiTree *bt) { }

(3) 用户工作区模块设计

主要工作函数，操作区用户界面设计。 void mainwork() {

int yourchoice;

printf(\printf(\ |\\n\printf(\欢迎使用二叉树基本操作程序------------------|\\n\printf(\printf(\︱ ----菜单选项---- ︱---|\\n\printf(\︱ 1.树状输出二叉树 2.先序遍历二叉树 ︱---|\\n\printf(\︱ 3.中序遍历二叉树 4.后序遍历二叉树 ︱---|\\n\printf(\︱ 5.输出叶子结点 6.输出叶子结点个数 ︱---|\\n\printf(\︱ 7.输出二叉树的深度 8.退出 ︱---|\\n\printf(\⊥＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿⊥---|\\n\printf(\【零 式】制 作—QQ:461595940-----------------|\\n\

7

//按照先序序列建立二叉树的二叉链表

char ch; scanf(\if(ch=='@') *bt=NULL; else { }

*bt=(BiTree)malloc(sizeof(BiTNode)); //生成一个新结点 (*bt)->data=ch;

CreateBiTree(&((*bt)->LChild)); //生成左子树 CreateBiTree(&((*bt)->RChild));

//生成右子树

数据结构课程设计报告

printf(\printf(\【零式提醒】您的输入只能在1至8之间哦！\\n\printf(\看数输数:\scanf(\

while(!(yourchoice==1||yourchoice==2||yourchoice==3||yourchoice==4||yourchoice==5||you

rchoice==6||yourchoice==7||yourchoice==8))

{ } while(1) {

switch(yourchoice) {

case 1:printf(\树的形状为:\\n\case 2:printf(\先序遍历序列为:\case 3:printf(\中序遍历序列为:\case 4:printf(\后序遍历序列为:\case 5:printf(\叶子结点为:\case 6:printf(\叶子结点为:%d\

case 7:printf(\二叉树的深度为:%d\\n\case 8: system(\default: break; }

printf(\【键入警告ERROR!】\\n\printf(\请重新输入：\scanf(\

printf(\printf(\ |\\n\printf(\欢迎使用二叉树基本操作程序------------------|\\n\printf(\printf(\︱ ----菜单选项---- ︱---|\\n\printf(\︱ 1.树状输出二叉树 2.先序遍历二叉树 ︱---|\\n\

8

数据结构课程设计报告

printf(\︱ 3.中序遍历二叉树 4.后序遍历二叉树 ︱---|\\n\printf(\︱ 5.输出叶子结点 6.输出叶子结点个数 ︱---|\\n\printf(\︱ 7.输出二叉树的深度 8.退出 ︱---|\\n\printf(\⊥＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿⊥---|\\n\printf(\【零 式】制 作—QQ:461595940-----------------|\\n\

printf(\printf(\【零式提醒】您的输入只能在1至8之间哦！\\n\printf(\看数输数:\scanf(\}//endwhile(1)

}//endmainwork (4) 树状输出二叉树 void TranslevelPrint(BiTree bt) { //本算法实现二叉树的按层打印

struct node {

BiTree vec[MAXLEN]; int layer[MAXLEN]; int locate[MAXLEN]; int front,rear;

//定义队列q

//存放树结点 //结点所在的层

//打印结点的位置

}q;

int i, j=1, k=0, nLocate; q.front = 0; q.rear = 0; printf(\

q.vec[q.rear]=bt; q.layer[q.rear]=1; q.locate[q.rear]=20; q.rear = q.rear+1; while(q.front < q.rear) {

bt = q.vec[q.front];

9

//初始化队列q队头，队尾

//将二叉树根结点如队列

数据结构课程设计报告

i = q.layer[q.front]; nLocate = q.locate[q.front]; if(j < i) { }

while (k<(nLocate-1)) //利用结点深度控制横向位置 { }

printf(\q.front=q.front+1;

if(bt->LChild !=NULL) //存放在左子树，将左子树根结点如队列 { }

if(bt->RChild !=NULL) //存放右子树，将右子树根结点入队列 { }

10

//进层打印时换行

printf(\j=j+1; k=0; while(k

printf(\

printf(\

q.vec[q.rear]=bt->LChild; q.layer[q.rear]=i+1;

q.locate[q.rear]=(int)(nLocate - pow(2, NLAYER-i-1)); q.rear = q.rear +1;

q.vec[q.rear]=bt->RChild; q.layer[q.rear]=i+1;

q.locate[q.rear]=(int)(nLocate+pow(2,NLAYER-i-1)); q.rear=q.rear+1;

数据结构课程设计报告

}

}

五、测试分析

请根据先根结点，按照从上到下、左至有的次序依次先根遍历根的每棵子树的方法，分别输入二叉树的结点序列（@号表示该结点为空）。例如“ABD@@E@@CH@@@”程序运行得到如图1所示的开始界面。

各子功能测试运行结果如下。

1. 树状输出二叉树

在主菜单下，用户输入1并回车，运行结果如图4所示。

图4 按树形输出创建二叉树

2. 先序遍历二叉树

在主菜单下，用户输入2并回车，运行结果如图5所示。

11

数据结构课程设计报告

图5 输出二叉树先序遍历序列

3. 中序遍历二叉树

在主菜单下，用户输入3并回车，运行结果如图6所示。

图6输出二叉树中序遍历序列

4. 后序遍历二叉树

在主菜单下，用户输入3并回车，运行结果如图7所示。

12

数据结构课程设计报告

图7 输出二叉树后序遍历序列

5. 输出叶子结点

在主菜单下，用户输入5并回车，运行结果如图8所示。

图8 输出二叉树的叶子结点

6. 输出叶子结点个数

在主菜单下，用户输入6并回车，运行结果如图9所示。

13

数据结构课程设计报告

图9输出二叉树的叶子结点个数

7. 输出二叉树的深度

在主菜单下，用户输入7并回车，运行结果如图10所示。

图10 输出二叉树的深度

8. 退出

在主菜单下，用户输入8并回车，即退出“二叉树基本操作程序”。

14

数据结构课程设计报告

六、用户手册

(1) 本程序执行文件为“二叉树的基本操作演示.exe”。

(2) 进入本程序之后，首先按照提示输入二叉树的结点，如按下列次序顺序读入字符ABD@@E@@CH@@@。

(3) 随即显示系统主菜单界面，用户可在该界面下输入各子菜单前对应的数字并回车，执行相应子菜单命令。

七、调试报告

(1) 调试过程中最常见的便是代码输入错误，如字母大小写、顺序颠倒、符号的半/全角使用等一些问题，都是在调试过程中逐一改正的。 (2)本程序是二叉树最基本的操作，没有深入。难免在执行程序时对输入的其他指令发生错误。所以只要根据本程序的说明操作即可。

(3)我想以后还可以给此程序添加其他一些功能，例如创建的二叉树是空树还是满二叉树；对创建的二叉树进行查找，删除，插入，匹配；如何解决程序顺利执行而不会陷入死循环一些问题等等。

(4)感想：程序员真的是太乏味了，不停的码代码，测代码，调代码，分析算法，考虑结构，然后不停的测试，不停的修改错误，直到没有问题为止。对我们年轻人的程序员，尤其是刚入门的学生来说，没有多大的兴趣和耐性去搞，所以当认真的去完成这个作业的时候，才发现八窍通了七窍——其结果是一窍不通。然而，当我就这一个小小的简单程序独立完成时，心中的喜悦和成就感却又充满心中，让我小乐了一下。我想IT业界的程序员们，埋头苦日，等的就是完成的那一刻的喜悦与成就吧。所以坚信自己是一大奇迹，我就能乘风万里。

八、程序清单

#include #include #include #include #define MAXLEN 100 #define NLAYER 4 typedef struct BiTNode {

char data; //数据域

15

//定义二叉树结点结构

本文来源：https://www.bwwdw.com/article/8y5v.html