实验2 树型数据结构及其应用

淮海工学院计算机工程学院

实验报告书

课程名： 《 数 据 结 构B》 题 目： 树形数据结构实验

班 级： 学 号： 姓 名：

评语： 成绩： 指导教师： 批阅时间： 年 月 日

《 数据结构B》实验报告 - 1 -

实验2 树形数据结构

实验目的和要求

1. 熟练掌握树的基本概念、二叉树的基本操作及在链式存储结构上的实现； 2. 重点掌握二叉树的生成、遍历及求深度等算法； 3. 掌握哈夫曼树的含义及其应用；

4. 掌握运用递归方式描述算法及编写递归C程序的方法，提高算法分析和程序设计能力。 实验环境

Turbo C 或VC++ 实验学时

2学时，必做实验 实验题目

1建立一棵用二叉链表方式存储的二叉树，并对其进行遍历（先序、中序和后序），打印输出遍历结果，求二叉树的深度//叶结点数目。

[基本要求] 从键盘接受输入先序序列，以二叉链表作为存储结构，建立二叉

树（以先序来建立）并对其进行遍历（先序、中序、后序），然后将遍历结果打印输出。要求采用递归和非递归两种方法实现。

[测试数据] ABCффDEфGффFффф（其中ф表示空格字符） 输出结果为： 先序：ABCDEGF 中序：CBEGDFA 后序：CGBFDBA

2已知二叉树按照二叉链表方式存储，编写算法，要求实现二叉树的竖向显示（竖向显示就是二叉树的按层显示）。

主要数据结构

主要算法

运行结果

实验体会

《 数据结构B》实验报告 - 2 -

附源代码