数据结构实验3 二叉树层次遍历Word文档下载推荐.docx

1、5、实验时间：10学时6、该文档的文件名不要修改，存入 命名的文件夹中7、该表中的数据只需填空，已有内容不要修改实验结果（运行结果界面及源程序，运行结果界面放在前面）：#include string.hstdlib.hmath.h#define STUDENT ETypestruct STUDENT char number8; char name8; char sex3; int age; char place20;struct BinaryTreeNode EType data; BinaryTreeNode *LChild; BinaryTreeNode *RChild;struct QT

2、ype BinaryTreeNode *ptr;struct Queue QType *element; int front; int rear; int maxsize;struct Node_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 fa

3、lse;bool IsFull（Queue &/判断队列是否为满 if（Q.front=（Q.rear+1）%（Q.maxsize+1） return true;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 &/取出队尾元素 result=Q.elementQ.rear;bool EnQueue（Queue &x）/元素进队 if（IsFull（Q）

4、 return false; Q.rear=（Q.rear+1）%（Q.maxsize+1）; Q.elementQ.rear=x;bool DeQueue（Queue &/元素出队 Q.front=（Q.front+1）%（Q.maxsize+1）; result=Q.elementQ.front;BinaryTreeNode *MakeNode（EType &/构造节点 ptr=new BinaryTreeNode; if（!ptr） return NULL; ptr-data=x;LChild=NULL;RChild=NULL; return ptr;void MakeBinaryTre

5、e（BinaryTreeNode *root, BinaryTreeNode *left,BinaryTreeNode *right）/构造二叉树之间的关系 root-LChild=left;RChild=right;void OutputBinaryTreeNode（BinaryTreeNode *p）/输出节点 coutdata.numberdata.namedata.sexdata.agedata.placeLChild） temp.ptr=p-LChild; EnQueue（Q,temp）; RChild）RChild; void LevelOrder_RtoL_UtoD（Binary

6、TreeNode *BT）/从右至左，从上至下按层次遍历一棵二叉树void LevelOrder_LtoR_DtoU（BinaryTreeNode *BT）/从左至右，从下至上按层次遍历一棵二叉树 int frontkeep=Q.front;DeQueue（Q,temp） break; for（int i=Q.rear;ifrontkeep;i-） OutputBinaryTreeNode（Q.elementi.ptr）;void LevelOrder_RtoL_DtoU（BinaryTreeNode *BT）/从右至左，从下至上按层次遍历一棵二叉树int BinaryHeight（Binar

7、yTreeNode *BT）/返回二叉树的高度BT） return 0; int HighL=BinaryHeight（BT-LChild）; int HighR=BinaryHeight（BT-RChild）; if（HighLHighR） return +HighL; else return +HighR;void BinaryDelete（BinaryTreeNode *BT）/二叉树删除算法 if（BT） BinaryDelete（BT- delete BT;int BinaryNodeSum（BinaryTreeNode *BT）/计算二叉树中的节点数 int index=0; in

8、dex+; return index;void DigitalToString（char str,int n） char temp; char k=1; int i=0; while （n & i80） k=n%10+48; n=n/10; stri=k; i+; stri=0; int len=strlen（str）; for （i=0;idata.name）; break; case 2:data.number）; case 3:data.place）; case 4:data.sex）; case 5: DigitalToString（outputInformation,elementk

9、.ptr-data.age）; default: break; return outputInformation;/输出二叉树void OutputBinaryTree（BinaryTreeNode *BT） Node_Ptr temp,*element; BinaryTreeNode *p; int MaxSize; int BinaryTreeHigh; int i,j,k; BinaryTreeHigh=BinaryHeight（BT）; MaxSize=（int） pow（2,BinaryTreeHigh）; element = new Node_Ptr MaxSize+1; /定义一

10、个用于存放二叉树结点指针的数组 for （i=1;=MaxSize;i+） /对指针数组初始化，初值设为NULL elementi.ptr=NULL; p = BT; temp.ptr = p; if （p） element1=temp; i+） /将二叉树中的每个结点指针以顺序存储结构存放到数组中 p=elementi.ptr; if （p） if （p-LChild ） /&!Lflag/线索树特有的处理与一般二叉树不同之处 temp.ptr = p- element2*i=temp; RChild ） /&Rflag/线索树特有的处理与一般二叉树不同之处 element2*i+1=tem

11、p; int WidthOfData=5; int IntervalOfData=3;/ coutWidthOfData=WidthOfDataIntervalOfData=IntervalOfDataBinaryTreeHigh=BinaryTreeHigh int position_of_central617; /存放每一元素输出位置中心（距离屏幕左边界的字符数） int row,col; /二维数组的行列下标变量 for（i=0;=BinaryTreeHigh;i+） /存放每一元素输出位置中心（距离屏幕左边界的字符数），初值为0 for（j=0;j=pow（2,BinaryTreeHi

12、gh-1）;j+） position_of_centralij=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个结点右上方 /即

13、编号为k的结点中心点垂直线左边最底层上有j个结点 row=（int）（log10（i）/log10（2）+1）; /计算中心点值存放在position_of_centralrowcol中的row col=（int）（i-（pow（2,（row-1）-1）; /计算中心点值存放在position_of_centralrowcol中的col if（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）; char prespace100; int m; int kk; int kkk; int item_max=5; kkk=（i