淮海工学院计算机科学系
实验报告书
课程名： 《数据结构》
题 目： 树形数据结构实验 班 级： 网络132 学 号： 2013122832 姓 名： 徐峰
评语： 成绩： 指导教师： 戴红伟 批阅时间： 年 月 日 《数据结构》实验报告 - 1 -
树形数据结构实验报告要求
1目的与要求:
1．熟练掌握二叉树的二叉链表存储结构；二叉树的常用遍历方法：按层遍历、先序递归遍历、中序递归和非递归遍历、后序递归遍历。
2．掌握按先序遍历顺序输入数据，递归建立二叉树的方法。 3. 掌握建立哈夫曼树的方法，实现哈夫曼编码。
4. 按照实验题目要求独立正确地完成实验内容（提交程序清单及相关实验数据与运行结果）；认真书写实验报告,并按时提交。
2 实验内容或题目
实验内容:
1. 建立一棵用二叉链表方式存储的二叉树，并对其进行遍历（先序、中序和后序），打印输出遍历结果。
[要求] 从键盘接受输入先序序列，以二叉链表作为存储结构，建立二叉树（以先序来建立）并对其进行遍历（先序、中序、后序），然后将遍历结果打印输出。要求采用递归和非递归两种方法实现。
[测试数据] ABCффDEфGффFффф（其中ф表示空格字符） 输出结果为： 先序：ABCDEGF 中序：CBEGDFA 后序：CGBFDBA
2．如题1要求建立好二叉树，按凹入表形式打印二叉树结构，如图1所示。(课后实习题三)
3. 参考课后习题6.9，以字符集（假设8个字符为A、B…H）中各个字符为叶结点、字符的使用频率为权重构造Huffman树，并求得各个字符的Huffman编码（参考教材P152教材算法6.16)。
3 实验步骤与源程序 1)非递归方式
#include
《数据结构》实验报告 - 2 -
#include
char data; //二叉树的元素类型 struct node *lchild; struct node *rchild;
}BTNode; //自定义二叉树的结类型
typedef BTNode *BTree; //定义二叉树的指针
BTree CreatBTree(void) {
BTree T;
char ch; //定义输入的数据类型
if((ch=getchar())=='#') //支持在键盘上输入先序二叉树 return(NULL); //读入#，返回空指针 else {
T=(BTNode *)malloc(sizeof(BTNode)); //分配空间，生成结点 T->data=ch;
T->lchild=CreatBTree(); //构造左子树 T->rchild=CreatBTree(); //构造右子树 return(T); } }
void Preorder(BTree T) //先序遍历 { if(T) {
printf(\访问结点
Preorder(T->lchild); //先序遍历左子树 Preorder(T->rchild); //先序遍历右子树 } }
void Inorder(BTree T) //中序遍历 { if(T) {
Inorder(T->lchild); //中序遍历左子树 printf(\访问结点
Inorder(T->rchild); //中序遍历右字树 } }
void Postorder(BTree T) //后序遍历 {
《数据结构》实验报告 - 3 -
if(T) {
Postorder(T->lchild); //后序遍历左子树 Postorder(T->rchild); //后序遍历右子树 printf(\访问结点 } }
void main() {
BTree root; //数的根结点
int i; //可供选择的整型变量i printf(\
printf(\请输入二叉树的先序序列，用#代表虚结点:\root=CreatBTree(); //返回根结点 do{ //循环语句
printf(\ printf(\先序遍历\\n\ printf(\中序遍历\\n\ printf(\后序遍历\\n\ printf(\
printf(\ scanf(\输入菜单序号 switch(i) {
case 1:printf(\先序遍历结果为:\ Preorder(root); break;
case 2:printf(\中序遍历结果为:\ Inorder(root); break;
case 3:printf(\后序遍历结果为:\ Postorder(root); break;
default:exit(1); }
printf(\}
while(i!=0); } 递归方式
#include
typedef char DataType;
《数据结构》实验报告 - 4 -
typedef struct Node {
DataType data;
struct Node *LChild; struct Node *RChild; }BiTNode, *BiTree;
void CreateBiTree(BiTree *bt) {
char ch;
ch=getchar();
if(ch=='.') *bt=NULL; else {
*bt=(BiTree)malloc(sizeof(BiTNode));//生成一个新结点 (*bt)->data=ch;
CreateBiTree(&(*bt)->LChild);//生成左子树 CreateBiTree(&(*bt)->RChild);//生成右子树 } }
void Visit(char ch) {
printf(\ }
void PreOrder(BiTree root)//先序遍历二叉树，root为指向二叉树（或某一子树）根结点的指针 {
if(root!=NULL) {
Visit(root->data);//访问根结点
PreOrder(root->LChild);//先序遍历左子树 PreOrder(root->RChild);//先序遍历右子树 } }
void InOrder(BiTree root)//中序遍历二叉树 {
if(root!=NULL) {
InOrder(root->LChild);//中序遍历左子树 Visit(root->data);//访问根结点
InOrder(root->RChild);//中序遍历右子树