数据结构实验6说课讲解.docx
《数据结构实验6说课讲解.docx》由会员分享，可在线阅读，更多相关《数据结构实验6说课讲解.docx（17页珍藏版）》请在冰点文库上搜索。
数据结构实验6说课讲解
《数据结构》实验报告
实验序号：
6 实验项目名称：
树和二叉树的操作
学 号
姓 名
专业、班
实验地点
指导教师
实验时间
一、实验目的及要求
1、进一步掌握指针变量、动态变量的含义。
2、掌握二叉树的结构特征，以及各种存储结构的特点及适用范围。
3、掌握用指针类型描述、访问和处理二叉树的运算。
4、掌握用二叉树前序、中序、后序、层次遍历的方法。
二、实验设备（环境）及要求
微型计算机；
windows操作系统；
MicrosoftVisualStudio6.0集成开发环境。
三、实验内容与步骤
1.根据下图中的树回答问题①-⑨。
1列出所有的叶子结点；K,L,F,M,H,I,J
2列出G结点的双亲；B
3列出E结点的孩子；K.L
4列出I结点所有的堂兄弟；E,F,G,H
5列出B结点所有的子孙；E,F,G,K,L,M
6结点E的度是多少；2
7树的度是多少；3
8结点E的层次是多少；3
9树的深度是多少；4
2．根据P129的方法，将a*b-（（c+d*e/f）+g）转化为表达式二叉树（绘图），并写出表达式二叉树的前序、中序和后序遍历顺序。
先序：
-*ab++c/*defg
中序：
a*b-c+d*e/f+g
后序：
ab*cde*f/+g+-
3.画出和下列二叉树相应的森林：
4.链式表表示和实现二叉排序树如下：
#include
#include
typedefintTElemType;
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->rchild=NULL;
if（!
root）
{
root=s;
}
else
{
p=root;
while（p）/*如何接入二叉排序树的适当位置*/
{
q=p;
if（p->data==x）//相同结点不能重复插入
{
printf（"dataalreadyexist!
\n"）;
return;
}
elseif（xdata）
p=p->lchild;
else
p=p->rchild;
}
if（xdata）
q->lchild=s;
else
q->rchild=s;
}
}
voidmain（）/*先生成二叉排序树*/
{
inti=1,x;//i记录结点个数，x存放结点值
root=NULL;/*千万别忘了赋初值给root!
*/
printf（"请输入数据,-9999表示输入结束\n"）;
do
{
printf（"pleaseinputdata%d:
",i）;
i++;
scanf（"%d",&x）;/*从键盘采集数据，以-9999表示输入结束*/
if（x==-9999）{
printf（"\nNowoutputdatavalue:
\n"）;
}
else
insert_data（x）;/*调用插入数据元素的函数*/
}while（x!
=-9999）;
}
改写以上程序，实现功能如下（任选三题）：
1）.编写函数实现前序、中序和后序遍历。
2）.编写函数实现计算叶节点个数。
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’）;
else
printf（"%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’）;
else
printf（"%c",’d’）;
四、实验结果与数据处理
详细记录程序在调试过程中出现的问题及解决方法。
记录程序执行的结果（贴图）。
五、分析与讨论
对上机实践结果进行分析，上机的心得体会。
六、教师评语
签名：
日期：
成绩
附源程序清单：
1、#include
#include
typedefintTElemType;
typedefstructBiTNode
{
TElemTypedata;
structBiTNode*lchild,*rchild;
}BiNode,*Bitree;
DLR（Bitreeroot）
{if（root!
=NULL）{//非空二叉树
printf（"%d",root->data）;//访问D
DLR（root->lchild）;//递归遍历左子树
DLR（root->rchild）;//递归遍历右子树
}
return（0）;
}
LDR（Bitreeroot）
{if（root!
=NULL）
{
LDR（root->lchild）;
printf（"%d",root->data）;
LDR（root->rchild）;
}
return（0）;}
LRD（Bitreeroot）
{if（root!
=NULL）{
LRD（root->lchild）;
LRD（root->rchild）;
printf（"%d",root->data）;
}
return（0）;
}
Bitreeroot;//定义根结点
voidinsert_data（intx）/*生成/树*/
{
Bitreep,q,s;
s=（Bitree）malloc（sizeof（BiNode））;//创建结点
s->data=x;//结点赋值
s->lchild=NULL;
s->rchild=NULL;
if（!
root）
{
root=s;
}
else
{
p=root;
while（p）/*如何接入二叉排序树的适当位置*/
{
q=p;
if（p->data==x）//相同结点不能重复插入
{
printf（"dataalreadyexist!
\n"）;
return;
}
elseif（xdata）
p=p->lchild;
else
p=p->rchild;
}
if（xdata）
q->lchild=s;
else
q->rchild=s;
}
}
voidmain（）/*先生成二叉排序树*/
{
inti=1,x;//i记录结点个数，x存放结点值
root=NULL;/*千万别忘了赋初值给root!
*/
printf（"请输入数据,-9999表示输入结束\n"）;
do
{
printf（"pleaseinputdata%d:
",i）;
i++;
scanf（"%d",&x）;/*从键盘采集数据，以-9999表示输入结束*/
if（x==-9999）{
printf（"\nNowoutputdatavalue:
\n"）;
}
else
insert_data（x）;/*调用插入数据元素的函数*/
}while（x!
=-9999）;
printf（"\nDLR:
"）;
DLR（root）;
printf（"\nLDR:
"）;
LDR（root）;
printf（"\nLRD:
"）;
LRD（root）;
printf（"\n"）;
}
2、#include
#include
typedefintTElemType;
typedefstructBiTNode
{
TElemTypedata;
structBiTNode*lchild,*rchild;
}BiNode,*Bitree;
Bitreeroot;//定义根结点
intCountLeaf（Bitreeroot）
{//返回指针T所指二叉树中所有叶子结点个数
intm,n;
if（!
root）return0;
if（!
root->lchild&&!
root->rchild）return1;
else{
m=CountLeaf（root->lchild）;n=CountLeaf（root->rchild）;
return（m+n）;
}//else
}//CountLeaf
voidinsert_data（intx）/*生成/树*/
{
Bitreep,q,s;
s=（Bitree）malloc（sizeof（BiNode））;//创建结点
s->data=x;//结点赋值
s->lchild=NULL;
s->rchild=NULL;
if（!
root）
{
root=s;
}
else
{
p=root;
while（p）/*如何接入二叉排序树的适当位置*/
{
q=p;
if（p->data==x）//相同结点不能重复插入
{
printf（"dataalreadyexist!
\n"）;
return;
}
elseif（xdata）
p=p->lchild;
else
p=p->rchild;
}
if（xdata）
q->lchild=s;
else
q->rchild=s;
}
}
voidmain（）/*先生成二叉排序树*/
{
inti=1,x;//i记录结点个数，x存放结点值
intsum;
root=NULL;/*千万别忘了赋初值给root!
*/
printf（"请输入数据,-9999表示输入结束\n"）;
do
{
printf（"pleaseinputdata%d:
",i）;
i++;
scanf（"%d",&x）;/*从键盘采集数据，以-9999表示输入结束*/
if（x==-9999）{
printf（"\nNowoutputdatavalue:
\n"）;
}
else
insert_data（x）;/*调用插入数据元素的函数*/
}while（x!
=-9999）;
printf（"\n叶节点个数="）;
sum=CountLeaf（root）;
printf（"%d\n",sum）;
}
3、#include
#include
typedefintTElemType;
typedefstructBiTNode
{
TElemTypedata;
structBiTNode*lchild,*rchild;
}BiNode,*Bitree;
Bitreeroot;//定义根结点
intDepth（Bitreeroot）{//返回二叉树的深度
intdepthval,depthLeft,depthRight;
if（root==NULL）depthval=0;
else{
depthLeft=Depth（root->lchild）;
depthRight=Depth（root->rchild）;
depthval=1+（depthLeft>depthRight?
depthLeft:
depthRight）;
}
returndepthval;
}
voidinsert_data（intx）/*生成/树*/
{
Bitreep,q,s;
s=（Bitree）malloc（sizeof（BiNode））;//创建结点
s->data=x;//结点赋值
s->lchild=NULL;
s->rchild=NULL;
if（!
root）
{
root=s;
}
else
{
p=root;
while（p）/*如何接入二叉排序树的适当位置*/
{
q=p;
if（p->data==x）//相同结点不能重复插入
{
printf（"dataalreadyexist!
\n"）;
return;
}
elseif（xdata）
p=p->lchild;
else
p=p->rchild;
}
if（xdata）
q->lchild=s;
else
q->rchild=s;
}
}
voidmain（）/*先生成二叉排序树*/
{
inti=1,x;//i记录结点个数，x存放结点值
intd;
root=NULL;/*千万别忘了赋初值给root!
*/
printf（"请输入数据,-9999表示输入结束\n"）;
do
{
printf（"pleaseinputdata%d:
",i）;
i++;
scanf（"%d",&x）;/*从键盘采集数据，以-9999表示输入结束*/
if（x==-9999）{
printf（"\nNowoutputdatavalue:
\n"）;
}
else
insert_data（x）;/*调用插入数据元素的函数*/
}while（x!
=-9999）;
printf（"\n树的深度为="）;
d=Depth（root）;
printf（"%d\n",d）;
}
升级会员 