《数据结构》

课程设计报告

专 业 计算机科学与技术

班 级 3班

姓 名

学 号

指导教师

起止时间 20XX.12~20XX.1

课程设计：二叉树

一、任务描述

二叉树的中序、前序、后序的递归、非递归遍历算法，应包含建树的实现。

任务：设计一个程序，实现二叉树的前序、中序、后序的递归遍历运算。

要求：

（1）创建二叉树；

（2）二叉树的前序、中序、后序的递归遍历运算实现。

二、问题分析

1、功能分析

分析设计课题的要求，要求编程实现以下功能：

（1）二叉树的建立—即创建二叉树；

（2）二叉树的遍历—二叉树的前序、中序、后序操作；

2、数据对象分析

二叉树的遍历：包括前序、中序、后序

将二叉树补充到完全二叉树在输入，才能正确创建二叉树

三、数据结构设计

二叉树的建立和遍历的实现。有关的定义如下：

typedef int Status;

typedef char TElemType; //定义二叉树结点值的类型为字符型

struct BiTNode {//定义二叉树结点类型栈结点的类型

TElemType data; //数据域

BiTNode *lchild,*rchild;//指针域

};BiTNode *BiTree;

四、功能设计

（一）主控菜单设计

程序运行后，输入提示，如下：“创建二叉树，请按前序序列输入各节点值：”

正确输入二叉树后，提示“已成功创建二叉树”

（二）程序模块结构

由课题要求可将程序划分为以下几个模块（即实现程序功能所需的函数）：

● 创建二叉树的函数void CreateBiTree(BiTree &T);

● 二叉树的前序遍历函数 Status PreOrderTraverse(BiTree T,Status(*Visit)(TElemType));

● 二叉树的中序遍历函数Status InOrderTraverse(BiTree T,Status(*Visit)(TElemType));

● 二叉树的后序遍历函数Status PostOrderTraverse(BiTree T,Status(*Visit)(TElemType))；

● 最简单的visit函数Status Visit(TElemType e);

（三）函数调用关系

程序的主要结构（函数调用关系）如下图所示。

其中main()是主函数，它进行菜单驱动。

BiTree T;

int n=0;

printf("创建二叉树，请按前序序列输入各节点值：\n");

CreateBiTree(T);

printf("\n");

printf("已成功创建二叉树\n");

PreOrderTraverse( T,Visit);

printf("\n");

InOrderTraverse(T,Visit);

printf("\n");

PostOrderTraverse(T,Visit);

printf("\n");

（四）文件结构

1、tree.h：二叉树相关的定义与声明

2、tree.cpp：二叉树运算的实现

5、mn.cpp：主函数

（五）各函数的算法设计

1、CreateBiTree()

算法原理：按先序次序输入二叉树中结点的值（一个字符），空格字符表示空树，构造二叉链表

流程图：

代码描述：void CreateBiTree(BiTree &T)

{char ch;

ch=getchar(); //读入一个字符

printf("%c",ch);

if (ch==' ') T=NULL;

else {if (!(T=(BiTNode *)malloc(sizeof(BiTNode)))) exit(OVERFLOW);

//内存分配成功

T-＞data = ch; //生成根结点

CreateBiTree(T-＞lchild);

CreateBiTree(T-＞rchild);

}

}

算法的时间复杂度分析：O(1)

2、PreOrderTraverse ()

算法原理：若二叉树为空，则空操作；否则（1）访问根结点；（2）先序遍历左子树（3）先序遍历右子树

流程图：

代码描述：Status PreOrderTraverse (BiTree T,Status (*visit)(TElemType e))

{ /*功能:先序遍历二叉树;参数:T为二叉树的根,visit为对结点的处理方法*/

if (T) { //若根结点不空

if(visit(T-＞data)) //访问根结点

if (PreOrderTraverse(T-＞lchild,visit)) //先序遍历根的左子树

if(PreOrderTraverse(T-＞rchild,visit)) //先序遍历根的右子树

return OK;

}

}

算法的时间复杂度分析：O(n)

3、InOrderTraverse ()

算法原理：若二叉树为空，则空操作；否则（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树；

流程图：

代码描述：Status InOrderTraverse (BiTree T,Status (*visit)(TElemType e)) {/*功能:中序遍历二叉树;参数:T为二叉树的根,visit为对结点的处理方法*/

if (T) { //若根结点不空

if (InOrderTraverse(T-＞lchild,visit)) //中序遍历根结点的左子树

if(visit(T-＞data)) //访问根结点

if(InOrderTraverse(T-＞rchild,visit)) //中序遍历根结点的右子树

return OK;

}

}

算法的时间复杂度分析：O(n)

4、PostOrderTraverse()

算法原理：若二叉树为空，则空操作；否则（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点

流程图：

代码描述：Status PostOrderTraverse (BiTree T,Status (*visit)(TElemType e))

{/*功能:后序遍历二叉树;参数:T为二叉树的根,visit为对结点的处理方法*/

if (T) { //若根结点不空

if (PostOrderTraverse(T-＞lchild,visit)) //后序遍历根结点的左子树

if(PostOrderTraverse(T-＞rchild,visit)) //后序遍历根结点的右子树

if(visit(T-＞data)) //访问根结点

return OK;

}

}

算法的时间复杂度分析：O(n)

五、测试数据和结果

1、测试数据

Abc de g f

2、测试结果

本程序在VC++环境下实现，下面是对以上测试数据的运行结果。

(1) 主菜单显示如下：

(2) 建立二叉树及各种遍历：

六、结束语

本设计完成了课题要求的任务，较熟练地建立了二叉树，实现了各种遍历算法设计了较便捷的操作界面。

 

第二篇：二叉树的基本操作及哈夫曼编码译码系统的实现

实 验 报 告

二叉树的基本操作及哈夫曼编码译码系统的实现

（20## / 20## 学年 第 二 学期）

实 验 报 告

实 验 报 告