数据结构实验3 二叉树层次遍历.doc
《数据结构实验3 二叉树层次遍历.doc》由会员分享,可在线阅读,更多相关《数据结构实验3 二叉树层次遍历.doc(21页珍藏版)》请在三一办公上搜索。
1、数据结构实验3实验报告实验项目3:二叉树层次遍历学号姓名课程号实验地点指导教师时间评语: 按时完成实验;实验内容和过程记录完整;回答问题完整、正确;实验报告的撰写认真、格式符合要求;无抄袭的行为。成绩教师签字二叉树从左至右,从上至下层次遍历1、预习要求:二叉树结构定义和层次遍历。2、实验目的: (1)了解二叉树结构层次遍历概念;(2)理解二叉树二种不同层次遍历过程;(3)掌握二叉树层次遍历算法程序。3、实验内容及要求:(1)建立包含10个结点的二叉树(树结构和数据元素的值由自己设定);(2)完成二叉树从左至右,从上至下层次遍历程序;(3)给出程序和遍历程序的结果。4、实验设备(环境)及要求硬件
2、:支持 Intel Pentium 及其以上 CPU ,内存 128MB 以上、硬盘 1GB 以上容量的微机。软件:配有 Windows98/2000/XP 操作系统,安装 Visual C+ 。5、实验时间:10学时6、该文档的文件名不要修改,存入 命名的文件夹中7、该表中的数据只需填空,已有内容不要修改实验结果(运行结果界面及源程序,运行结果界面放在前面):#include #include #include #include #define STUDENT ETypestruct STUDENTcharnumber8;charname8;charsex3;int age;charplac
3、e20;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.m
4、axsize+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.maxs
5、ize+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(
6、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
7、*left,BinaryTreeNode *right)/构造二叉树之间的关系root-LChild=left;root-RChild=right;void OutputBinaryTreeNode(BinaryTreeNode *p)/输出节点cout data.number data.name data.sex data.age data.placeendl;coutendl;void LevelOrder_LtoR_UtoD(BinaryTreeNode *BT)/从左至右,从上至下按层次遍历一棵二叉树Queue Q;QType temp;BinaryTreeNode *p;int ma
8、xqueuesize=50;CreatQueue(Q,maxqueuesize);p=BT;temp.ptr=p;EnQueue(Q,temp);coutendl;cout 学号 姓名 性别 年龄 住址 endl;cout =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 *
9、p;int maxqueuesize=50;CreatQueue(Q,maxqueuesize);p=BT;temp.ptr=p;EnQueue(Q,temp);coutendl;cout 学号 姓名 性别 年龄 住址 endl;cout =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;BinaryTr
10、eeNode *p;int maxqueuesize=50;CreatQueue(Q,maxqueuesize);int frontkeep=Q.front;p=BT;temp.ptr=p;EnQueue(Q,temp);coutendl;cout 学号 姓名 性别 年龄 住址 endl;cout =RChild)temp.ptr=p-RChild;EnQueue(Q,temp);if(p-LChild)temp.ptr=p-LChild;EnQueue(Q,temp);for(int i=Q.rear;ifrontkeep;i-)OutputBinaryTreeNode(Q.elementi
11、.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);coutendl;cout 学号 姓名 性别 年龄 住址 endl;cout =LChild)temp.ptr=p-LChild;EnQueue(Q,temp);if(p-RChil
12、d)temp.ptr=p-RChild;EnQueue(Q,temp);for(int i=Q.rear;ifrontkeep;i-)OutputBinaryTreeNode(Q.elementi.ptr);int BinaryHeight(BinaryTreeNode *BT)/返回二叉树的高度if(!BT) return 0;int HighL=BinaryHeight(BT-LChild);int HighR=BinaryHeight(BT-RChild);if(HighLHighR)return +HighL;elsereturn +HighR;void BinaryDelete(Bi
13、naryTreeNode *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(!DeQue
14、ue(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 & i80)k=n%10+48;n=n/10;stri=k;i+;stri=0;int len=strlen(str);for (i=0;ilen/2;i+)temp=s
15、tri;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_string
16、16=;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
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构实验3 二叉树层次遍历 数据结构 实验 二叉 层次 遍历
链接地址:https://www.31ppt.com/p-2396678.html