数据结构实验2.docx
- 文档编号:9678304
- 上传时间:2023-05-20
- 格式:DOCX
- 页数:30
- 大小:217.04KB
数据结构实验2.docx
《数据结构实验2.docx》由会员分享,可在线阅读,更多相关《数据结构实验2.docx(30页珍藏版)》请在冰点文库上搜索。
数据结构实验2
数据结构《实验2》实验报告
实验项目2:
二叉树前序、中序非递归遍历
学 号
姓 名
课程号
实验地点
指导教师
时间
评语:
按时完成实验;实验内容和过程记录完整;回答问题完整、正确;实验报告的撰写认真、格式符合要求;无抄袭的行为。
成绩
教师签字
二叉树中序、后序非递归遍历
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;
};
typedefBinaryTreeNodeBinaryTree;
structSType
{
BinaryTreeNode*ptr;
boolstatus;
};
structStack
{
SType*element;
inttop;
intmaxsize;
};
boolIsEmpty(Stack&S)
{//判断是否为空
if(S.top==-1)returntrue;
returnfalse;
}
boolIsFull(Stack&S)
{//判断是否为满
if(S.top>=S.maxsize-1)returntrue;
returnfalse;
}
voidCreatStack(Stack&S,intmaxstacksize)
{//创建堆栈
S.maxsize=maxstacksize;
S.element=newSType[S.maxsize];
S.top=-1;
}
boolPush(Stack&S,SType&x)
{//进栈
if(IsFull(S))returnfalse;
S.top++;
S.element[S.top]=x;
returntrue;
}
boolPop(Stack&S,SType&result)
{//出栈
if(IsEmpty(S))returnfalse;
result=S.element[S.top];
S.top--;
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(EType&x)
{//输出节点
cout<<""<<
""< ""< ""< ""< ""< cout< } structNode_Ptr { BinaryTreeNode*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; StackS; STypetemp; intindex=0; BinaryTreeNode*p=BT; intmaxstacksize=50; CreatStack(S,maxstacksize); while(p||! IsEmpty(S)) { if(p) { index++; temp.ptr=p; Push(S,temp); p=p->LChild; } else if(! IsEmpty(S)) { Pop(S,temp); p=temp.ptr; p=p->RChild; } } 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=(int)pow(2,i-1);//kkk是满二叉树中每一层第1个结点的编号 for(intitem=1;item<=item_max;item++)//输出每个数据元素多个item成员的值 { inthalf_len_pre_value=0;//同一行前一个输出的元素值长度的一半,同一行第一个输出的元素值前没有值输出,初值为0 inthalf_len_now_value=WidthOfData/2;//同一行当前输出的元素值长度的一半,其值始终为WidthOfData的一半 kk=kkk;//kk是满二叉树中每一层结点的编号变化,从某层的最左边第一个结点编号kkk开始 for(j=1;j<=pow(2,i-1);j++)//输出满二叉树中同一层次上的每个数据元素的同一个成员的值 { charoutputInformation[20]={""}; char*OutputInformation; if(element[kk].ptr)//获取每个数据元素的一个成员的值OutputInformation,如姓名、年龄等 OutputInformation=GetOuputInformation(item,kk,outputInformation,element); if(position_of_central[i][j])//输出数据中点值存在时,position_of_central[i][j]非0 { charoutputstring[80]={""}; char*OutputString; //下面语句将每个数据元素的一个成员的值OutputInformation,如姓名、年龄等,转换为等长WidthOfData的字符串OutputString OutputString=GetOuputInformationString(WidthOfData,OutputInformation,outputstring); //生成两个孩子之前的空格串prespace //构成: <前导空格串>=<两个输出数据中心点之差>-<前一个输出元素值长度一半>-<当前输出元素值长度的一半> strcpy(prespace,""); m=(position_of_central[i][j]-position_of_central[i][j-1]-1-half_len_pre_value-half_len_now_value); for(k=1;k<=m;k++) strcat(prespace,""); cout< cout< half_len_pre_value=WidthOfData/2;//调整同一行前一个输出的元素值长度为WidthOfData的一半 kk++; }//if(position_of_central[i][j]) }//for(j=1;j<=pow(2,i-1);j++) cout< }//for(intitem=1;item<=5;item++) charline[3]="─"; charOutputLine[80]; charmidspace[80]; intnodenumber; if(i==1)//对深度为BinaryTreeHigh的满二叉树从上至下,从左至右的编号,计算第i层上起始结点的编号nodenumber nodenumber=1; else nodenumber=(int)((pow(2,i)-1)-(pow(2,i-1)-1));//第i(i! =1)层上的第1个结点编号nodenumber for(j=1;j<=pow(2,i-1);j++)//输出同一层次上的线条 { if(i==BinaryTreeHigh)break;//最底层下面没有线条,所以break //生成两个数据元素之前的前导空格串prespace strcpy(prespace,""); m=(position_of_central[i+1][j]-position_of_central[i+1][j-1]-1); for(k=1;k<=m;k++) strcat(prespace,""); //计算左右两个孩子之间一半的连线OutLine,由若干个line"─"构成 //注意line是汉字字符,一个占两个字符位,m是左右两个孩子之间的line"─"数,所以m要除4 strcpy(OutputLine,""); m=(position_of_central[i+1][j+1]-position_of_central[i+1][j]-1)/4; for(k=1;k<=m;k++) strcat(OutputLine,line); //计算左右两个孩子之间一半的空格字符的个数m,,所以要除2。 由m形成左右两个孩子之间的空格串midspace strcpy(midspace,""); m=(position_of_central[i+1][j+1]-position_of_central[i+1][j]-1)/2; for(k=1;k<=m;k++) strcat(midspace,""); if((element[2*nodenumber].ptr)&&(element[2*nodenumber+1].ptr))//左右子树都存在时,左右两个孩子上的连接线┌─┴─┐ cout< <<"┌"< if((element[2*nodenumber].ptr)&&(! element[2*nodenumber+1].ptr))//左子树存在,右子树不存在时,左右两个孩子上的连接线┌─┘ cout< <<"┌"<
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 实验