资源描述：
《数据结构实验6.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、《数据结构》实验报告实验序号：6 实验项目名称：树和二叉树的操作学 号姓 名专业、班实验地点指导教师实验时间一、实验目的及要求1、进一步掌握指针变量、动态变量的含义。2、掌握二叉树的结构特征，以及各种存储结构的特点及适用范围。3、掌握用指针类型描述、访问和处理二叉树的运算。4、掌握用二叉树前序、中序、后序、层次遍历的方法。二、实验设备（环境）及要求微型计算机；windows操作系统；MicrosoftVisualStudio6.0集成开发环境。三、实验内容与步骤1.根据下图中的树回答问题①-⑨。①列出所有的叶子结点；K,L,F
2、,M,H,I,J②列出G结点的双亲；B③列出E结点的孩子；K.L④列出I结点所有的堂兄弟；E,F,G,H⑤列出B结点所有的子孙；E,F,G,K,L,M⑥结点E的度是多少；2⑦树的度是多少；3⑧结点E的层次是多少；3⑨树的深度是多少；42．根据P129的方法，将a*b-((c+d*e/f)+g)转化为表达式二叉树（绘图），并写出表达式二叉树的前序、中序和后序遍历顺序。-*+ab+gc/f*de先序：-*ab++c/*defg中序：a*b-c+d*e/f+g后序：ab*cde*f/+g+-3.画出和下列二叉树相应的森林：4.链式表表示和实现二叉排序树如
3、下：#include#includetypedefintTElemType;typedefstructBiTNode{TElemTypedata;structBiTNode*lchild,*rchild;}BiNode,*Bitree;Bitreeroot;//定义根结点voidinsert_data(intx)/*生成二叉排序树*/{Bitreep,q,s;s=(Bitree)malloc(sizeof(BiNode));//创建结点s->data=x;//结点赋值s->lchild=NULL;s->rchi
4、ld=NULL;if(!root){root=s;}else{p=root;while(p)/*如何接入二叉排序树的适当位置*/{q=p;if(p->data==x)//相同结点不能重复插入{printf("dataalreadyexist!");return;}elseif(xdata)p=p->lchild;elsep=p->rchild;}if(xdata)q->lchild=s;elseq->rchild=s;}}voidmain()/*先生成二叉排序树*/{inti=1,x;//i记录结点个数，x存放结点值root=N
5、ULL;/*千万别忘了赋初值给root!*/printf("请输入数据,-9999表示输入结束");do{printf("pleaseinputdata%d:",i);i++;scanf("%d",&x);/*从键盘采集数据，以-9999表示输入结束*/if(x==-9999){printf("Nowoutputdatavalue:");}elseinsert_data(x);/*调用插入数据元素的函数*/}while(x!=-9999);}改写以上程序，实现功能如下(任选三题)：1).编写函数实现前序、中序和后序遍历。2).编写函数实
6、现计算叶节点个数。3).编写函数实现层序遍历。4).编写函数实现查询二叉树中的某个结点(分查到和查不到两种情况)。5)．编写函数实现求二叉树的深度6).编写函数实现中序非递归遍历(利用栈)以下题目为选做题：5.如果通讯字符a，b，c，d出现频度分别为7，5，2，4①某同学设计了如下程序，请根据程序画出对应的二叉树，计算所画出的二叉树的带权路径长度；if(input==’c’)printf("%c",’c’);elseif(input==’d’)printf("%c",’d’);elseif(input==’a’)printf("%c",’a’);e
7、lseprintf("%c",’b’);WPL=7*3+5*3+4*2+2*1=46②请画出对应的赫夫曼（哈弗曼）树；③计算赫夫曼树的带权路径长度；WPL=2*3+4*3+5*2+7*1=35④根据赫夫曼树，用if-else语句修改①中的程序，写出最佳判定算法。if(input==’a’)printf("%c",’a’);elseif(input==’b’)printf("%c",’b’);elseif(input==’c’)printf("%c",’c’);elseprintf("%c",’d’);四、实验结果与数据处理详细记录程序在调试过程中出
8、现的问题及解决方法。记录程序执行的结果（贴图）。五、分析与讨论对上机实践结果进行分析，上机的心得体会。六、教师评语签名：日
