数据结构实验3 二叉树层次遍历Word文档下载推荐.docx
《数据结构实验3 二叉树层次遍历Word文档下载推荐.docx》由会员分享,可在线阅读,更多相关《数据结构实验3 二叉树层次遍历Word文档下载推荐.docx(30页珍藏版)》请在冰点文库上搜索。
5、实验时间:
10学时
6、该文档的文件名不要修改,存入<
学号>
<
姓名>
命名的文件夹中
7、该表中的数据只需填空,已有内容不要修改
实验结果(运行结果界面及源程序,运行结果界面放在前面):
#include<
iostream.h>
string.h>
stdlib.h>
math.h>
#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
};
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&
{//判断队列是否为满
if(Q.front==(Q.rear+1)%(Q.maxsize+1))returntrue;
boolGetFront(Queue&
Q,QType&
result)
{//取出队头元素
if(IsEmpty(Q))returnfalse;
result=Q.element[(Q.front+1)%(Q.maxsize+1)];
returntrue;
boolGetRear(Queue&
{//取出队尾元素
result=Q.element[Q.rear];
boolEnQueue(Queue&
x)
{//元素进队
if(IsFull(Q))returnfalse;
Q.rear=(Q.rear+1)%(Q.maxsize+1);
Q.element[Q.rear]=x;
boolDeQueue(Queue&
{//元素出队
Q.front=(Q.front+1)%(Q.maxsize+1);
result=Q.element[Q.front];
BinaryTreeNode*MakeNode(EType&
{//构造节点
ptr=newBinaryTreeNode;
if(!
ptr)returnNULL;
ptr->
data=x;
LChild=NULL;
RChild=NULL;
returnptr;
voidMakeBinaryTree(BinaryTreeNode*root,BinaryTreeNode*left,BinaryTreeNode*right)
{//构造二叉树之间的关系
root->
LChild=left;
RChild=right;
voidOutputBinaryTreeNode(BinaryTreeNode*p)
{//输出节点
cout<
<
"
"
"
p->
data.number<
data.name<
data.sex<
data.age<
data.place<
endl;
voidLevelOrder_LtoR_UtoD(BinaryTreeNode*BT)
{//从左至右,从上至下按层次遍历一棵二叉树
QueueQ;
QTypetemp;
BinaryTreeNode*p;
intmaxqueuesize=50;
CreatQueue(Q,maxqueuesize);
p=BT;
temp.ptr=p;
EnQueue(Q,temp);
学号姓名性别年龄住址"
==============================="
while(p)
{
if(!
DeQueue(Q,temp))return;
p=temp.ptr;
//出队成功
OutputBinaryTreeNode(p);
if(p->
LChild)
{
temp.ptr=p->
LChild;
EnQueue(Q,temp);
}
RChild)
RChild;
}
voidLevelOrder_RtoL_UtoD(BinaryTreeNode*BT)
{//从右至左,从上至下按层次遍历一棵二叉树
voidLevelOrder_LtoR_DtoU(BinaryTreeNode*BT)
{//从左至右,从下至上按层次遍历一棵二叉树
intfrontkeep=Q.front;
DeQueue(Q,temp))break;
for(inti=Q.rear;
i>
frontkeep;
i--)
OutputBinaryTreeNode(Q.element[i].ptr);
voidLevelOrder_RtoL_DtoU(BinaryTreeNode*BT)
{//从右至左,从下至上按层次遍历一棵二叉树
intBinaryHeight(BinaryTreeNode*BT)
{//返回二叉树的高度
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->
deleteBT;
intBinaryNodeSum(BinaryTreeNode*BT)
{//计算二叉树中的节点数
intindex=0;
index++;
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<
len/2;
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;
=left_space;
i++)//形成OutputInformation左边需要补充的空格字符串
strcat(left_space_string,"
);
=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:
data.number);
case3:
data.place);
case4:
data.sex);
case5:
DigitalToString(outputInformation,element[k].ptr->
data.age);
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;
=MaxSize;
i++)//对指针数组初始化,初值设为NULL
element[i].ptr=NULL;
p=BT;
temp.ptr=p;
if(p)element[1]=temp;
i++)//将二叉树中的每个结点指针以顺序存储结构存放到数组中
p=element[i].ptr;
if(p)
if(p->
LChild)//&
!
Lflag//线索树特有的处理与一般二叉树不同之处
{
temp.ptr=p->
element[2*i]=temp;
}
RChild)//&
Rflag//线索树特有的处理与一般二叉树不同之处
element[2*i+1]=temp;
intWidthOfData=5;
intIntervalOfData=3;
//cout<
WidthOfData="
WidthOfData<
IntervalOfData="
IntervalOfData<
BinaryTreeHigh="
BinaryTreeHigh<
intposition_of_central[6][17];
//存放每一元素输出位置中心(距离屏幕左边界的字符数)
introw,col;
//二维数组的行列下标变量
for(i=0;
=BinaryTreeHigh;
i++)//存放每一元素输出位置中心(距离屏幕左边界的字符数),初值为0
for(j=0;
j<
=pow(2,BinaryTreeHigh-1);
j++)
position_of_central[i][j]=0;
=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;
kkk=(i