数据结构用c语言描述实验五

《数据结构用c语言描述实验五》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、实验五实验名称二叉树及其砬用实验性质设计性实验学时数6学一、实验目的1.掌握二义树链表的结构和构造过程。2.掌握用递归方法实现二叉树的遍历。3.加强对二叉树的理解，培养解决实际问题的能力。二、实验内容1.用递归方法实现对二叉树的遍历等操作。2.二义树的其他操作算法。一一一实验过程1、实验题目［问题描述］以下题FI根据自己兴趣和能力可选作二道作为实验题R:（1）创建一颗二叉树，用递归方法实现对其进行先序、屮序和后序遍历的操作；（2）根据题目1，修改其中一个算法，用来计算统计二叉树屮叶子节点的个数和度为1、度为2的节点个数；（3）设计并实现一个哈夫曼树并对其进

2、行编码。（4）修理牧场。农夫要修理牧场的一段栅栏，发现需要N块木头，每块木头长度为整数Li个长度单位，于是他购买了一条很长的、能鋸成N块的木头，即该木头的长度是Li的总和。但是农夫自己没有锯子，请人锯木的酬金跟这段木头的长度成正比。简单起见，设酬金等于所鋸木头的长度。例如，将长度为20的木头锯成长度为8、7和5的三段，第一次锯木头将木头锯成12和8,花费20;第二次将木头长度为12的木头鋸成7和5花费12,总花费为32.如果第一次将木头锯成15和5，则第二次鋸木头花费15,总花费35（大于32）。请编写程序帮助农夫计算将木头锯成N块的最少花费。输入数据N表

3、示要将木头锅成N块，然后输入N个整数，表示每段木块的长度。输出将木头鋸成N块的最少花费。（可采用哈夫曼算法和最小堆实现）［基本要求］（1）按实验内容编写完整的程序，并上机验证。（2）实验完成后，提交电子档教师验收程序，并提交填写好的实验报告。［测试数据］由学生依据软件工程的测试技术自己确定。注意测试边界数据。2、源程序#include#include#defineDataTypechar#defineVisitchartypedefstructNode//定义二叉链表节点结构{DataTypedata;structNo

4、de*LChild;structNode*RChild;}BiTNodc,*BiTrcc;voidinist(BiTrcc*root)//初始化二叉链表{(*root)=(BiTrcc)malloc(sizcof(BiTNodc));(*root)->LChild=NULL;(*root)->RChild=NULL;}voidCrcatcBiTrcc(BiTrcc*bt)//创建二叉链表{charch;ch=gctchar();if(ch==)*bt=NULL;else{*bt=(BiTrcc)malloc(sizcof(BiTNodc));(*bt)->

5、data=ch;CreatcBiTree(&((*bt)->LChild));CrcatcBiTrcc(&((*bt)->RChiId));}}voidPrcOrdcr(BiTrccroot)/*先序遍历二叉树，root为指向二叉树根节点的指针*/{if(root!=NULL){Visit(root->data);printfC’％cr/’，root->data);PreOrder(root->LChiId);PreOrder(root->RChiId);}}voidInOrdcr(BiTrccroot)/*中序遍历二叉树，root为指向二叉树根节点的指

6、针*/{if(root!=NULL){InOrdcr(root~>LChiId);Visit(root~>data);printfC’％c'root~>data);InOrdcr(root~>RChiId);}}voidPostOrdcr(BiTrccroot)/*后序遍历二叉树，root为指向二叉树根节点的指针*/{if(root!=NULL){PostOrdcr(root~>LChiId);PostOrdcr(root~>RChiId);Visit(root-〉data);printf("%crT，root~>data);}}intmain()/

7、/主函数{intchoice;BiTreebt;inist(&bt);bt=(BiTrcc)malloc(sizcof(BiTNodc));printf("请输入字符以‘；’结束<);CreateBiTree(&bt);do{printf("请输入选择项：1.先序遍历2.中序遍历3.后序遍历0.退出");scanf(〃%d〃,&choice);switch(choice){case01:PrcOrdcr(bt);printfC’。；break;ease02:InOrdcr(bt);printfC’。；break;ease03:PostOrder

8、(bt);printf(z/z，);break;default