数据结构实验3 二叉树层次遍历.docx
《数据结构实验3 二叉树层次遍历.docx》由会员分享，可在线阅读，更多相关《数据结构实验3 二叉树层次遍历.docx（30页珍藏版）》请在冰点文库上搜索。
数据结构实验3二叉树层次遍历
数据结构《实验3》实验报告
实验项目3：
二叉树层次遍历
学 号
姓 名
课程号
实验地点
指导教师
时间
评语：
按时完成实验；实验内容和过程记录完整；回答问题完整、正确；实验报告的撰写认真、格式符合要求；无抄袭的行为。
成绩
教师签字
二叉树从左至右，从上至下层次遍历
1、预习要求：
二叉树结构定义和层次遍历。
2、实验目的：
（1）了解二叉树结构层次遍历概念；
（2）理解二叉树二种不同层次遍历过程；
（3）掌握二叉树层次遍历算法程序。
3、实验内容及要求：
（1）建立包含10个结点的二叉树（树结构和数据元素的值由自己设定）；
（2）完成二叉树从左至右，从上至下层次遍历程序；
（3）给出程序和遍历程序的结果。
4、实验设备（环境）及要求
硬件：
支持IntelPentiumⅡ及其以上CPU，内存128MB以上、硬盘1GB以上容量的微机。
软件：
配有Windows98/2000/XP操作系统，安装VisualC++。
5、实验时间：
10学时
6、该文档的文件名不要修改，存入<学号><姓名>命名的文件夹中
7、该表中的数据只需填空，已有内容不要修改
实验结果（运行结果界面及源程序，运行结果界面放在前面）：
#include
#include
#include
#include
#defineSTUDENTEType
structSTUDENT
{
charnumber[8];
charname[8];
charsex[3];
intage;
charplace[20];
};
structBinaryTreeNode
{
ETypedata;
BinaryTreeNode*LChild;
BinaryTreeNode*RChild;
};
structQType
{
BinaryTreeNode*ptr;
};
structQueue
{
QType*element;
intfront;
intrear;
intmaxsize;
};
structNode_Ptr
{
BinaryTreeNode*ptr;
};
voidCreatQueue（Queue&Q,intMaxQueueSize）
{//创建队列
Q.maxsize=MaxQueueSize;
Q.element=newQType[Q.maxsize+1];
Q.front=0;
Q.rear=0;
}
boolIsEmpty（Queue&Q）
{//判断队列是否为空
if（Q.front==Q.rear）returntrue;
returnfalse;
}
boolIsFull（Queue&Q）
{//判断队列是否为满
if（Q.front==（Q.rear+1）%（Q.maxsize+1））returntrue;
returnfalse;
}
boolGetFront（Queue&Q,QType&result）
{//取出队头元素
if（IsEmpty（Q））returnfalse;
result=Q.element[（Q.front+1）%（Q.maxsize+1）];
returntrue;
}
boolGetRear（Queue&Q,QType&result）
{//取出队尾元素
if（IsEmpty（Q））returnfalse;
result=Q.element[Q.rear];
returntrue;
}
boolEnQueue（Queue&Q,QType&x）
{//元素进队
if（IsFull（Q））returnfalse;
Q.rear=（Q.rear+1）%（Q.maxsize+1）;
Q.element[Q.rear]=x;
returntrue;
}
boolDeQueue（Queue&Q,QType&result）
{//元素出队
if（IsEmpty（Q））returnfalse;
Q.front=（Q.front+1）%（Q.maxsize+1）;
result=Q.element[Q.front];
returntrue;
}
BinaryTreeNode*MakeNode（EType&x）
{//构造节点
BinaryTreeNode*ptr;
ptr=newBinaryTreeNode;
if（!
ptr）returnNULL;
ptr->data=x;
ptr->LChild=NULL;
ptr->RChild=NULL;
returnptr;
}
voidMakeBinaryTree（BinaryTreeNode*root,BinaryTreeNode*left,BinaryTreeNode*right）
{//构造二叉树之间的关系
root->LChild=left;
root->RChild=right;
}
voidOutputBinaryTreeNode（BinaryTreeNode*p）
{//输出节点
cout<<""<<
""<data.number<<
""<data.name<<
""<data.sex<<
""<data.age<<
""<data.place<cout<}
voidLevelOrder_LtoR_UtoD（BinaryTreeNode*BT）
{//从左至右，从上至下按层次遍历一棵二叉树
QueueQ;
QTypetemp;
BinaryTreeNode*p;
intmaxqueuesize=50;
CreatQueue（Q,maxqueuesize）;
p=BT;
temp.ptr=p;
EnQueue（Q,temp）;
cout<cout<<"学号姓名性别年龄住址"<cout<<"==============================="<while（p）
{
if（!
DeQueue（Q,temp））return;
p=temp.ptr;//出队成功
OutputBinaryTreeNode（p）;
if（p->LChild）
{
temp.ptr=p->LChild;
EnQueue（Q,temp）;
}
if（p->RChild）
{
temp.ptr=p->RChild;
EnQueue（Q,temp）;
}
}
}
voidLevelOrder_RtoL_UtoD（BinaryTreeNode*BT）
{//从右至左，从上至下按层次遍历一棵二叉树
QueueQ;
QTypetemp;
BinaryTreeNode*p;
intmaxqueuesize=50;
CreatQueue（Q,maxqueuesize）;
p=BT;
temp.ptr=p;
EnQueue（Q,temp）;
cout<cout<<"学号姓名性别年龄住址"<cout<<"==============================="<while（p）
{
if（!
DeQueue（Q,temp））return;
p=temp.ptr;//出队成功
OutputBinaryTreeNode（p）;
if（p->RChild）
{
temp.ptr=p->RChild;
EnQueue（Q,temp）;
}
if（p->LChild）
{
temp.ptr=p->LChild;
EnQueue（Q,temp）;
}
}
}
voidLevelOrder_LtoR_DtoU（BinaryTreeNode*BT）
{//从左至右，从下至上按层次遍历一棵二叉树
QueueQ;
QTypetemp;
BinaryTreeNode*p;
intmaxqueuesize=50;
CreatQueue（Q,maxqueuesize）;
intfrontkeep=Q.front;
p=BT;
temp.ptr=p;
EnQueue（Q,temp）;
cout<cout<<"学号姓名性别年龄住址"<cout<<"==============================="<while（p）
{
if（!
DeQueue（Q,temp））break;
p=temp.ptr;//出队成功
if（p->RChild）
{
temp.ptr=p->RChild;
EnQueue（Q,temp）;
}
if（p->LChild）
{
temp.ptr=p->LChild;
EnQueue（Q,temp）;
}
}
for（inti=Q.rear;i>frontkeep;i--）
OutputBinaryTreeNode（Q.element[i].ptr）;
}
voidLevelOrder_RtoL_DtoU（BinaryTreeNode*BT）
{//从右至左，从下至上按层次遍历一棵二叉树
QueueQ;
QTypetemp;
BinaryTreeNode*p;
intmaxqueuesize=50;
CreatQueue（Q,maxqueuesize）;
intfrontkeep=Q.front;
p=BT;
temp.ptr=p;
EnQueue（Q,temp）;
cout<cout<<"学号姓名性别年龄住址"<cout<<"==============================="<while（p）
{
if（!
DeQueue（Q,temp））break;
p=temp.ptr;//出队成功
if（p->LChild）
{
temp.ptr=p->LChild;
EnQueue（Q,temp）;
}
if（p->RChild）
{
temp.ptr=p->RChild;
EnQueue（Q,temp）;
}
}
for（inti=Q.rear;i>frontkeep;i--）
OutputBinaryTreeNode（Q.element[i].ptr）;
}
intBinaryHeight（BinaryTreeNode*BT）
{//返回二叉树的高度
if（!
BT）return0;
intHighL=BinaryHeight（BT->LChild）;
intHighR=BinaryHeight（BT->RChild）;
if（HighL>HighR）
return++HighL;
else
return++HighR;
}
voidBinaryDelete（BinaryTreeNode*BT）
{//二叉树删除算法
if（BT）
{
BinaryDelete（BT->LChild）;
BinaryDelete（BT->RChild）;
deleteBT;
}
}
intBinaryNodeSum（BinaryTreeNode*BT）
{//计算二叉树中的节点数
if（!
BT）return0;
QueueQ;
QTypetemp;
BinaryTreeNode*p;
intmaxqueuesize=50;
intindex=0;
CreatQueue（Q,maxqueuesize）;
p=BT;
temp.ptr=p;
EnQueue（Q,temp）;
while（p）
{
if（!
DeQueue（Q,temp））break;
p=temp.ptr;//出队成功
index++;
if（p->LChild）
{
temp.ptr=p->LChild;
EnQueue（Q,temp）;
}
if（p->RChild）
{
temp.ptr=p->RChild;
EnQueue（Q,temp）;
}
}
returnindex;
}
voidDigitalToString（charstr[],intn）
{
chartemp;
chark=1;
inti=0;
while（n&&i<80）
{
k=n%10+48;
n=n/10;
str[i]=k;
i++;
}
str[i]='\0';
intlen=strlen（str）;
for（i=0;i{
temp=str[i];
str[i]=str[len-i-1];
str[len-i-1]=temp;
}
}
char*GetOuputInformationString（intWidthOfData,char*OutputInformation,char*outputstring）
{//将一个元素的字符串OutputInformation转换为宽度为WidthOfData的等长字符串outputstring
//例如，姓名是由四个字符组成，而WidthOfData为8，则在姓名字符串的两边分别连接两个字符，形成8个长度的字符串
intleft_space,right_space;
inti;
charleft_space_string[16]={""};
charright_space_string[16]={""};
intadd_space;
intlen_OutputInformation=strlen（OutputInformation）;//计算OutputInformation的字符个数
add_space=WidthOfData-len_OutputInformation;//计算需要补充的字符个数
left_space=add_space/2;//计算OutputInformation左边需要补充的字符个数
right_space=add_space-left_space;//计算OutputInformation右边需要补充的字符个数
for（i=1;i<=left_space;i++）//形成OutputInformation左边需要补充的空格字符串
strcat（left_space_string,""）;
for（i=1;i<=right_space;i++）//形成OutputInformation右边需要补充的空格字符串
strcat（right_space_string,""）;
//在OutputInformation左边和右边连接需要补充的空格字符串
strcpy（outputstring,left_space_string）;
strcat（outputstring,OutputInformation）;
strcat（outputstring,right_space_string）;
returnoutputstring;//返回WidthOfData宽度的outputstring
}
char*GetOuputInformation（intitem,intk,char*outputInformation,Node_Ptr*element）
{
switch（item）
{
case1:
//线索树特有的处理与一般二叉树不同之处，在姓名的两边连接线索标志
{
strcat（outputInformation,element[k].ptr->data.name）;
break;
}
case2:
{
strcat（outputInformation,element[k].ptr->data.number）;
break;
}
case3:
{
strcat（outputInformation,element[k].ptr->data.place）;
break;
}
case4:
{
strcat（outputInformation,element[k].ptr->data.sex）;
break;
}
case5:
{
DigitalToString（outputInformation,element[k].ptr->data.age）;
break;
}
default:
break;
}
returnoutputInformation;
}
//输出二叉树
voidOutputBinaryTree（BinaryTreeNode*BT）
{
Node_Ptrtemp,*element;
BinaryTreeNode*p;
intMaxSize;
intBinaryTreeHigh;
inti,j,k;
BinaryTreeHigh=BinaryHeight（BT）;
MaxSize=（int）pow（2,BinaryTreeHigh）;
element=newNode_Ptr[MaxSize+1];//定义一个用于存放二叉树结点指针的数组
for（i=1;i<=MaxSize;i++）//对指针数组初始化，初值设为NULL
element[i].ptr=NULL;
p=BT;
temp.ptr=p;
if（p）element[1]=temp;
for（i=1;i<=MaxSize;i++）//将二叉树中的每个结点指针以顺序存储结构存放到数组中
{
p=element[i].ptr;
if（p）
{
if（p->LChild）//&&!
p->Lflag//线索树特有的处理与一般二叉树不同之处
{
temp.ptr=p->LChild;
element[2*i]=temp;
}
if（p->RChild）//&&!
p->Rflag//线索树特有的处理与一般二叉树不同之处
{
temp.ptr=p->RChild;
element[2*i+1]=temp;
}
}
}
intWidthOfData=5;
intIntervalOfData=3;
//cout<<"WidthOfData="<//cout<<"IntervalOfData="<//cout<<"BinaryTreeHigh="<intposition_of_central[6][17];//存放每一元素输出位置中心（距离屏幕左边界的字符数）
introw,col;//二维数组的行列下标变量
for（i=0;i<=BinaryTreeHigh;i++）//存放每一元素输出位置中心（距离屏幕左边界的字符数），初值为0
for（j=0;j<=pow（2,BinaryTreeHigh-1）;j++）
position_of_central[i][j]=0;
for（i=1;i<=pow（2,BinaryTreeHigh）-1;i++）//对深度为BinaryTreeHigh的满二叉树的所有结点计算每个结点输出的中心点位置
{
k=i*2;//k指向i的左子树根结点
while（k<=pow（2,BinaryTreeHigh）-1）//k不断推进到i编号的结点左子树中最右子孙结点
k=2*k+1;
k=k/2;//k的值就是i编号的结点左子树中最右子孙结点的编号
j=（int）（k-（pow（2,（BinaryTreeHigh-1））-1））;//由k编号的结点换算出该结点是底层中从左至右第j个结点右上方
//即编号为k的结点中心点垂直线左边最底层上有j个结点
row=（int）（log10（i）/log10
（2）+1）;//计算中心点值存放在position_of_central[row][col]中的row
col=（int）（i-（pow（2,（row-1））-1））;//计算中心点值存放在position_of_central[row][col]中的col
if（row==BinaryTreeHigh）
//计算底层i结点距离左边界的字符数，左边无间隙
position_of_central[row][col]=（j-1）*WidthOfData+（j-1）*IntervalOfData+（WidthOfData/2+1）;
else
//计算非底层i结点距离左边界的字符数，
position_of_central[row][col]=j*WidthOfData+（j-1）*IntervalOfData+（IntervalOfData/2+1）;
}
charprespace[100];
intm;
intkk;
intkkk;
intitem_max=5;
cout<for（i=1;i<=BinaryTreeHigh;i++）
{
kkk=（i
升级会员 