数据结构实验3 二叉树层次遍历.doc

数据结构实验3实验报告实验项目3：二叉树层次遍历学号姓名课程号实验地点指导教师时间评语： 按时完成实验；实验内容和过程记录完整；回答问题完整、正确；实验报告的撰写认真、格式符合要求；无抄袭的行为。成绩教师签字二叉树从左至右，从上至下层次遍历1、预习要求：二叉树结构定义和层次遍历。2、实验目的： （1）了解二叉树结构层次遍历概念；（2）理解二叉树二种不同层次遍历过程；（3）掌握二叉树层次遍历算法程序。3、实验内容及要求：（1）建立包含10个结点的二叉树（树结构和数据元素的值由自己设定）；（2）完成二叉树从左至右，从上至下层次遍历程序；（3）给出程序和遍历程序的结果。4、实验设备（环境）及要求硬件：支持 Intel Pentium 及其以上 CPU ，内存 128MB 以上、硬盘 1GB 以上容量的微机。软件：配有 Windows98/2000/XP 操作系统，安装 Visual C+ 。5、实验时间：10学时6、该文档的文件名不要修改，存入<学号> <姓名> 命名的文件夹中7、该表中的数据只需填空，已有内容不要修改实验结果（运行结果界面及源程序，运行结果界面放在前面）：#include <iostream.h>#include <string.h>#include <stdlib.h>#include <math.h>#define STUDENT ETypestruct STUDENTcharnumber8;charname8;charsex3;int age;charplace20;struct BinaryTreeNodeEType data;BinaryTreeNode *LChild;BinaryTreeNode *RChild;struct QTypeBinaryTreeNode *ptr;struct QueueQType *element;int front;int rear;int maxsize;struct Node_PtrBinaryTreeNode*ptr; ;void CreatQueue(Queue &Q,int MaxQueueSize)/创建队列Q.maxsize=MaxQueueSize;Q.element=new QTypeQ.maxsize+1;Q.front=0;Q.rear=0;bool IsEmpty(Queue &Q)/判断队列是否为空if(Q.front=Q.rear) return true;return false;bool IsFull(Queue &Q)/判断队列是否为满if(Q.front=(Q.rear+1)%(Q.maxsize+1) return true;return false;bool GetFront(Queue &Q,QType &result)/取出队头元素if(IsEmpty(Q) return false;result=Q.element(Q.front+1)%(Q.maxsize+1);return true;bool GetRear(Queue &Q,QType &result)/取出队尾元素if(IsEmpty(Q) return false;result=Q.elementQ.rear;return true;bool EnQueue(Queue &Q,QType &x)/元素进队if(IsFull(Q) return false;Q.rear=(Q.rear+1)%(Q.maxsize+1);Q.elementQ.rear=x;return true;bool DeQueue(Queue &Q,QType &result)/元素出队if(IsEmpty(Q) return false;Q.front=(Q.front+1)%(Q.maxsize+1);result=Q.elementQ.front;return true;BinaryTreeNode *MakeNode(EType &x)/构造节点BinaryTreeNode *ptr;ptr=new BinaryTreeNode;if(!ptr) return NULL;ptr->data=x;ptr->LChild=NULL;ptr->RChild=NULL;return ptr;void MakeBinaryTree(BinaryTreeNode *root, BinaryTreeNode *left,BinaryTreeNode *right)/构造二叉树之间的关系root->LChild=left;root->RChild=right;void OutputBinaryTreeNode(BinaryTreeNode *p)/输出节点cout<<" "<<" "<<p->data.number<< " "<<p->data.name<< " "<<p->data.sex<< " "<<p->data.age<< " "<<p->data.place<<endl;cout<<endl;void LevelOrder_LtoR_UtoD(BinaryTreeNode *BT)/从左至右，从上至下按层次遍历一棵二叉树Queue Q;QType temp;BinaryTreeNode *p;int maxqueuesize=50;CreatQueue(Q,maxqueuesize);p=BT;temp.ptr=p;EnQueue(Q,temp);cout<<endl;cout<<" 学号 姓名 性别 年龄 住址 "<<endl;cout<<" ="<<endl;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);void LevelOrder_RtoL_UtoD(BinaryTreeNode *BT)/从右至左，从上至下按层次遍历一棵二叉树Queue Q;QType temp;BinaryTreeNode *p;int maxqueuesize=50;CreatQueue(Q,maxqueuesize);p=BT;temp.ptr=p;EnQueue(Q,temp);cout<<endl;cout<<" 学号 姓名 性别 年龄 住址 "<<endl;cout<<" ="<<endl;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);void LevelOrder_LtoR_DtoU(BinaryTreeNode *BT)/从左至右，从下至上按层次遍历一棵二叉树Queue Q;QType temp;BinaryTreeNode *p;int maxqueuesize=50;CreatQueue(Q,maxqueuesize);int frontkeep=Q.front;p=BT;temp.ptr=p;EnQueue(Q,temp);cout<<endl;cout<<" 学号 姓名 性别 年龄 住址 "<<endl;cout<<" ="<<endl;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(int i=Q.rear;i>frontkeep;i-)OutputBinaryTreeNode(Q.elementi.ptr);void LevelOrder_RtoL_DtoU(BinaryTreeNode *BT)/从右至左，从下至上按层次遍历一棵二叉树Queue Q;QType temp;BinaryTreeNode *p;int maxqueuesize=50;CreatQueue(Q,maxqueuesize);int frontkeep=Q.front;p=BT;temp.ptr=p;EnQueue(Q,temp);cout<<endl;cout<<" 学号 姓名 性别 年龄 住址 "<<endl;cout<<" ="<<endl;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(int i=Q.rear;i>frontkeep;i-)OutputBinaryTreeNode(Q.elementi.ptr);int BinaryHeight(BinaryTreeNode *BT)/返回二叉树的高度if(!BT) return 0;int HighL=BinaryHeight(BT->LChild);int HighR=BinaryHeight(BT->RChild);if(HighL>HighR)return +HighL;elsereturn +HighR;void BinaryDelete(BinaryTreeNode *BT)/二叉树删除算法if(BT)BinaryDelete(BT->LChild);BinaryDelete(BT->RChild);delete BT;int BinaryNodeSum(BinaryTreeNode *BT)/计算二叉树中的节点数if(!BT) return 0; Queue Q;QType temp;BinaryTreeNode *p;int maxqueuesize=50;int index=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);return index;void DigitalToString(char str,int n)chartemp;chark=1;inti=0;while (n && i<80)k=n%10+48;n=n/10;stri=k;i+;stri='0'int len=strlen(str);for (i=0;i<len/2;i+)temp=stri;stri=strlen-i-1;strlen-i-1=temp;char*GetOuputInformationString(int WidthOfData,char *OutputInformation,char *outputstring)/将一个元素的字符串OutputInformation转换为宽度为WidthOfData的等长字符串outputstring /例如，姓名是由四个字符组成，而WidthOfData为8，则在姓名字符串的两边分别连接两个字符，形成8个长度的字符串intleft_space,right_space;inti;charleft_space_string16=""charright_space_string16=""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宽度的outputstringchar*GetOuputInformation(int item,int k,char *outputInformation,Node_Ptr *element)switch(item)case 1:/线索树特有的处理与一般二叉树不同之处，在姓名的两边连接线索标志strcat(outputInformation,elementk.ptr->data.name);break;case 2:strcat(outputInformation,elementk.ptr->data.number);break;case 3:strcat(outputInformation,elementk.ptr->data.place);break;case 4:strcat(outputInformation,elementk.ptr->data.sex);break;case 5:DigitalToString(outputInformation,elementk.ptr->data.age);break;default:break;returnoutputInformation;/输出二叉树void OutputBinaryTree(BinaryTreeNode *BT)Node_Ptrtemp,*element;BinaryTreeNode *p;intMaxSize; intBinaryTreeHigh;inti,j,k;BinaryTreeHigh=BinaryHeight(BT);MaxSize=(int) pow(2,BinaryTreeHigh);element = new Node_Ptr MaxSize+1;/定义一个用于存放二叉树结点指针的数组for (i=1;i<=MaxSize;i+)/对指针数组初始化，初值设为NULLelementi.ptr=NULL;p = BT;temp.ptr = p;if (p) element1=temp;for (i=1;i<=MaxSize;i+)/将二叉树中的每个结点指针以顺序存储结构存放到数组中p=elementi.ptr;if (p)if (p->LChild ) /&&!p->Lflag/线索树特有的处理与一般二叉树不同之处temp.ptr = p->LChild;element2*i=temp;if (p->RChild ) /&&!p->Rflag/线索树特有的处理与一般二叉树不同之处temp.ptr = p->RChild;element2*i+1=temp;intWidthOfData=5;intIntervalOfData=3;/cout<<"WidthOfData="<<WidthOfData<<endl;/cout<<"IntervalOfData="<<IntervalOfData<<endl;/cout<<"BinaryTreeHigh="<<BinaryTreeHigh<<endl;intposition_of_central617;/存放每一元素输出位置中心（距离屏幕左边界的字符数）introw,col;/二维数组的行列下标变量for(i=0;i<=BinaryTreeHigh;i+)/存放每一元素输出位置中心（距离屏幕左边界的字符数），初值为0for(j=0;j<=pow(2,BinaryTreeHigh-1);j+)position_of_centralij=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_centralrowcol中的rowcol=(int)(i-(pow(2,(row-1)-1);/计算中心点值存放在position_of_centralrowcol中的colif(row=BinaryTreeHigh) /计算底层i结点距离左边界的字符数，左边无间隙position_of_centralrowcol= (j-1)*WidthOfData + (j-1)*IntervalOfData + (WidthOfData/2 +1);else/计算非底层i结点距离左边界的字符数，position_of_centralrowcol=j*WidthOfData + (j-1)*IntervalOfData + (IntervalOfData/2 +1);charprespace100;intm;intkk;intkkk;intitem_max=5;cout<<endl;for(i=1;i<=BinaryTreeHigh;i+)kkk=(int)pow(2,i-1);/kkk是满二叉树中每一层第1个结点的编号for(int item=1;item<=item_max;item+)/输出每个数据元素多个item成员的值inthalf_len_pre_value=0;/同一行前一个输出的元素值长度的一半,同一行第一个输出的元素值前没有值输出，初值为0inthalf_len_now_value=WidthOfData/2;/同一行当前输出的元素值长度的一半，其值始终为WidthOfData的一半kk=kkk;/kk是满二叉树中每一层结点的编号变化，从某层的最左边第一个结点编号kkk开始for(j=1;j<=pow(2,i-1);j+)/输出满二叉树中同一层次上的每个数据元素的同一个成员的值charoutputInformation20=""char*OutputInformation;if (elementkk.ptr)/获取每个数据元素的一个成员的值OutputInformation，如姓名、年龄等OutputInformation=GetOuputInformation(item,kk,outputInformation,element);if (position_of_centralij)/输出数据中点值存在时，position_of_centralij非0charoutputstring80=""char*OutputString;/下面语句将每个数据元素的一个成员的值OutputInformation，如姓名、年龄等，转换为等长WidthOfData的字符串OutputStringOutputString=GetOuputInformationString(WidthOfData,OutputInformation,outputstring);/生成两个孩子之前的空格串prespace/构成：<前导空格串>=<两个输出数据中心点之差> - <前一个输出元素值长度一半> - <当前输出元素值长度的一半>strcpy(prespace,"");m=(position_of_centralij-position_of_centralij-1-1-half_len_pre_value-half_len_now_value);for(k=1;k<=m;k+)strcat(prespace," ");cout<<prespace;cout<<OutputString;half_len_pre_value=WidthOfData/2;/调整同一行前一个输出的元素值长度为WidthOfData的一半kk+;/if (position_of_centralij)/for(j=1;j<=pow(2,i-1);j+)cout<<endl;/for(int item=1;item<=5;item+)charline3=""charOutputLine80;charmidspace80;intnodenumber;if(i=1)/对深度为BinaryTreeHigh的满二叉树从上至下，从左至右的编号，计算第i层上起始结点的编号nodenumbernodenumber=1;elsenodenumber=(int)(pow(2,i)-1)-(pow(2,i-1)-1);/第i(i!=1)层上的第1个结点编号nodenumberfor(j=1;j<=pow(2,i-1);j+)/输出同一层次上的线条if(i=BinaryTreeHigh)break;/最底层下面没有线条，所以break/生成两个数据元素之前的前导空格串prespacestrcpy(prespace,"");m=(position_of_centrali+1j-position_of_centrali+1j-1-1);for(k=1;k<=m;k+)strcat(prespace," ");/计算左右两个孩子之间一半的连线OutLine，由若干个line""构成/注意line是汉字字符，一个占两个字符位，m是左右两个孩子之间的line""数，所以m要除4strcpy(OutputLine,"");m=(position_of_centrali+1j+1-position_of_centrali+1j-1)/4;for(k=1;k<=m;k+)strcat(OutputLine,line);/计算左右两个孩子之间一半的空格字符的个数m,，所以要除2。由m形成左右两个孩子之间的空格串midspacestrcpy(midspace,"");m=(position_of_centrali+1j+1-position_of_centrali+1j-1)/2;for(k=1;k<=m;k+)strcat(midspace," ");if (element2*nodenumber.ptr) && (element2*nodenumber+1.ptr)/左右子树都存在时，左右两个孩子上的连接线cout<<prespace<<""<<OutputLine<<""<<OutputLine<<""if (element2*nodenumber.ptr) && (!element2*nodenumber+1.ptr)/左子树存在，右子树不存在时，左右两个孩子上的连接线cout<<prespace<<""<<OutputLine<<""<<midspace;if (!element2*nodenumber.ptr) && (element2*nodenumber+1.ptr)/左子树不存在，右子树存在时左右两个孩子上的连接线cout<<prespace<<midspace<<""<<OutputLine<<""if (!element2*nodenumber.ptr) && (!element2*nodenumber+1.ptr)/左子树不存在，右子树不存在时，没有连接线，是空格串cout<<prespace<<midspace<<" "<<midspace<<" "nodenumber=nodenumber+1;/结点编号加1cout<<endl;/for(i=1;i<=BinaryTreeHigh;i+)delete element;/释放工作空间int main()BinaryTreeNode*BT,*P11;EType x;int choice;char number8=" ","001","002","003","004","005","006","007","008","009","010"char name8=" ","百里","东郭","太史","闻人","公孙","赫连","钟离","鲜鱼","轩辕","南门"char sex3=" ","女","男","女","男","女","女","男","男","女","男"char place20=" ","重庆","长安","东莞","安庆","承德","四平","安稳","香港","金门","龙门"for(int i=1;i<=10;i+)strcpy(x.number , numberi);strcpy(x.name , namei);strcpy(x.sex , sexi);x.age=20+i;strcpy(x.place , placei);Pi=MakeNode(x);MakeBinaryTree(P1,P2,P3);MakeBinaryTree(P2,P4,P5);MakeBinaryTree(P3,NULL,P6);MakeBinaryTree(P4,P7,NULL);MakeBinaryTree(P5,NULL,P8);MakeBinaryTree(P6,P9,P10);MakeBinaryTree(P7,NULL,NULL);MakeBinaryTree(P8,NULL,NULL);MakeBinaryTree(P9,NULL,NULL); MakeBinaryTree(P10,NULL,NULL);BT=P1; while (true)cout<<endl;cout<<"*二叉树的简单运算*"<<endl;cout<<"* 1-