数据结构实验指导(3)

3.编译运行。运行结果如下图所示：

25

实验4 树和二叉树的存储结构的实现

实验目的

1． 熟悉二叉树结点的结构和对二叉树的基本操作。 2． 掌握对二叉树每一种操作的具体实现。

3． 学会利用递归方法编写对二叉树这种递归数据结构进行处理的算法。

4． 在二叉树基本操作的基础上掌握对二叉树的一些其它操作的具体实现方法。

实验要求

1． 独立完成；

2． 程序调试正确，有执行结果。

实验内容（基础题必做，应用题任选）

1. 基础题：

按照教材中抽象数据类型二叉树的定义，采用二叉链表存储结构，编写主函数演示二叉树的基本操作，如： 说明：二叉树的基本操作可包括：

(1) void InitBT( BTreeNode *&BT ) //初始化二叉树BT (2) void CreateBT( BTreeNode *&BT, char *a )

//根据字符串a所给出二叉树的描述，建立二叉链表存储结构 (3) int EmptyBT( BTreeNode *BT)

//检查二叉树BT是否为空，空返回1，否则返回0

(4) int DepthBT( BTreeNode *BT) //求二叉树BT的深度并返回该值 (5) int FindBT( BTreeNode *BT, ElemType x)

//查找二叉树BT中值为x的结点，若查找成功返回1，否则返回0 (6) void PreOrder( BTreeNode *BT) //先序遍历二叉树BT (7) void InOrder( BTreeNode *BT) //中序遍历二叉树BT (8) void PostOrder( BTreeNode *BT) //后序遍历二叉树BT (9) void LevelOrder( BTreeNode *BT ) //按层次遍历二叉树BT

(10) void LeafCount(BTreeNode *BT , int & count) //求二叉树b的叶子结点个数

(11) int NodeCount(BTreeNode *BT) //求二叉树BT的总结点个数 (12) void ClearBTree( BTreeNode *&BT ) //清除二叉树BT 2．应用题

(1)输入n个叶子结点的权值，根据Huffman算法，构造一棵哈夫曼树。

(2)家谱管理：本题目对家谱管理进行简单的模拟，以实现查看祖先和子孙个人信息、插入家族成员、删除家族成员等功能。

26

实验步骤参考：

1.打开FileView双击tree.h，完成头文件的编写。tree.h主要含结构体的定义和函数的实现。

27

28