实验报告3-赵徐伟.doc

《实验报告3-赵徐伟.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、淮海工学院计算机科学系实验报告书课程名：《数据结构》题目：树形数据结构实验班级：网络132学号：2013122841姓名：赵徐伟评语：成绩：指导教师：戴红伟批阅时间：年月日《数据结构》实验报告-12-树形数据结构实验报告要求1目的与要求:1．熟练掌握二叉树的二叉链表存储结构；二叉树的常用遍历方法：按层遍历、先序递归遍历、中序递归和非递归遍历、后序递归遍历。2．掌握按先序遍历顺序输入数据，递归建立二叉树的方法。3.掌握建立哈夫曼树的方法，实现哈夫曼编码。4.按照实验题目要求独立正确地完成实验内容（提交程序清单及

2、相关实验数据与运行结果）；认真书写实验报告,并按时提交。2实验内容或题目实验内容:1.建立一棵用二叉链表方式存储的二叉树，并对其进行遍历（先序、中序和后序），打印输出遍历结果。[要求]从键盘接受输入先序序列，以二叉链表作为存储结构，建立二叉树（以先序来建立）并对其进行遍历（先序、中序、后序），然后将遍历结果打印输出。要求采用递归和非递归两种方法实现。[测试数据]ABCффDEфGффFффф（其中ф表示空格字符）输出结果为：先序：ABCDEGF中序：CBEGDFA后序：CGBFDBA2．如题1要求建立好二叉树

3、，按凹入表形式打印二叉树结构，如图1所示。(课后实习题三)3.参考课后习题6.9，以字符集（假设8个字符为A、B…H）中各个字符为叶结点、字符的使用频率为权重构造Huffman树，并求得各个字符的Huffman编码（参考教材P152教材算法6.16)。3实验步骤与源程序1)非递归方式#include#include《数据结构》实验报告-12-#includetypedefstructnode{chardata;//二叉树的元素类型structnode*

4、lchild;structnode*rchild;}BTNode;//自定义二叉树的结类型typedefBTNode*BTree;//定义二叉树的指针BTreeCreatBTree(void){BTreeT;charch;//定义输入的数据类型if((ch=getchar())=='#')//支持在键盘上输入先序二叉树return(NULL);//读入#，返回空指针else{T=(BTNode*)malloc(sizeof(BTNode));//分配空间，生成结点T->data=ch;T->lchild=Cr

5、eatBTree();//构造左子树T->rchild=CreatBTree();//构造右子树return(T);}}voidPreorder(BTreeT)//先序遍历{if(T){printf("%c",T->data);//访问结点Preorder(T->lchild);//先序遍历左子树Preorder(T->rchild);//先序遍历右子树}}voidInorder(BTreeT)//中序遍历{if(T){Inorder(T->lchild);//中序遍历左子树printf("%c",T->da

6、ta);//访问结点Inorder(T->rchild);//中序遍历右字树}}voidPostorder(BTreeT)//后序遍历{《数据结构》实验报告-12-if(T){Postorder(T->lchild);//后序遍历左子树Postorder(T->rchild);//后序遍历右子树printf("%c",T->data);//访问结点}}voidmain(){BTreeroot;//数的根结点inti;//可供选择的整型变量iprintf("");printf("请输入二叉树的先序序列，用#

7、代表虚结点:");root=CreatBTree();//返回根结点do{//循环语句printf("********************SELECT********************");printf("t1:先序遍历");printf("t2:中序遍历");printf("t3:后序遍历");printf("t0:Exit");printf("t*********************************************");scanf("%d",

8、&i);//输入菜单序号switch(i){case1:printf("先序遍历结果为:");Preorder(root);break;case2:printf("中序遍历结果为:");Inorder(root);break;case3:printf("后序遍历结果为:");Postorder(root);break;default:exit(1);}printf("");}while(i!=0