二叉树层次遍历
数据结构实验
报告
软件系统测试报告下载sgs报告如何下载关于路面塌陷情况报告535n,sgs报告怎么下载竣工报告下载
二〇一二年
数据结构《实验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、该表中的数据只需填空,已有内容不要修改
实验结果(运行结果界面及源程序,运行结果界面放在前面): 四种程序遍历的结果
数据结构实验报告 二〇一二年
数据结构实验报告 二〇一二年
#define STUDENT EType #include
#include #include
#include #include
//二叉树链式结构定义
数据结构实验报告 二〇一二年
struct STUDENT
{
char place[10];
char name[10];
char number[12];
char sex[3];
int age;
};
struct BinaryTreeNode {
EType data;
BinaryTreeNode *LChild;
BinaryTreeNode *RChild; };
typedef BinaryTreeNode BinaryTree; //队列结构定义
struct QType
{
BinaryTreeNode *ptr; };
struct Queue
{
QType *element;
int front;
int rear;
int maxsize;
};
void CreatQueue(Queue &Q,int MaxQueueSize)
{//构造一个最大容量为MaxQueueSize的队列Q
Q.maxsize=MaxQueueSize;
Q.element=new QType[Q.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) {//返回队列Q中队头元素
if(IsEmpty(Q))return false;
result=Q.element[(Q.front+1)%(Q.maxsize+1)];
return true;
}
bool EnQueue(Queue &Q,QType &x) {//x进Q队列,返回进入队列后的状态值
if(IsFull(Q))return false;
Q.rear=(Q.rear+1)%(Q.maxsize+1);
Q.element[Q.rear]=x;
return true;
}
bool DeQueue(Queue &Q,QType &result) {//将Q队列队头的值取至result中,并移动指针front,返回出队列后的状态值
if(IsEmpty(Q))return false;
Q.front=(Q.front+1)%(Q.maxsize+1);
result=Q.element[Q.front];
return true;
}
struct Node_Ptr
{
BinaryTreeNode *ptr;
} ;
void DigitalToString(char str[],int n)
{
char temp;
char k=1;
int i=0;
while (n && i<80)
{
k=n%10+48;
n=n/10;
str[i]=k;
i++;
}
str[i]='\0';
int len=strlen(str);
for (i=0;idata.number);
break;
}
case 2:
{
strcat(outputInformation,element[k].ptr->data.name);
break;
}
case 3:
{
strcat(outputInformation,element[k].ptr->data.sex);
break;
}
case 4:
{
strcat(outputInformation,element[k].ptr->data.place);
break;
}
case 5:
{
DigitalToString(outputInformation,element[k].ptr->data.age);
break;
}
default: break;
}
return outputInformation;
}
void OutputBinaryTree(BinaryTreeNode *BT) {
Node_Ptr temp,*element;
BinaryTreeNode *p;
int MaxSize;
int BinaryTreeHigh;
int i,j,k;
数据结构实验报告 二〇一二年
BinaryTreeHigh=5; //BinaryHeight(BT);
MaxSize=(int) pow(2,BinaryTreeHigh);
element = new Node_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)
{
temp.ptr = p->LChild;
element[2*i]=temp;
}
if (p->RChild)
{
temp.ptr = p->RChild;
element[2*i+1]=temp;
}
}
}
int WidthOfData=5;
int IntervalOfData=3;
// cout<<"WidthOfData="<=<两个输出数据中心点之差> - <前一个输出元素值长度一半> - <当前输出元素值长度的一半>
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<data=x;
ptr->LChild=NULL;
ptr->RChild=NULL;
return ptr;
}
数据结构实验报告 二〇一二年 void MakeBinaryTree(BinaryTree *root,BinaryTree *left,BinaryTree *right)
{//链接root,left,right所指的节点指针为二叉树
root->LChild=left;
root->RChild=right;
}
void BinaryDelete(BinaryTree *BT) {//二叉树的删除
if(BT)
{
BinaryDelete(BT->LChild);
BinaryDelete(BT->RChild);
delete BT;
}
}
int BinaryHeight(BinaryTreeNode *BT) {
if(!BT) return 0;
int HightL=BinaryHeight(BT->LChild);
int HightR=BinaryHeight(BT->RChild);
if(HightL>HightR)
return ++HightL;
else
return ++HightR;
}
//四种层次遍历方式
void LeverOrder_LtoR_UtoD(BinaryTree *BT) {//从左至右,从上至下遍历一棵二叉树
Queue Q;
QType temp;
BinaryTree *p=BT;
int MaxQueueSize=50;//其值是假设的一个足够大的数
CreatQueue(Q,MaxQueueSize);
temp.ptr=p;
EnQueue(Q,temp);
cout<<"************** "<data.name<<" "<data.number<<"
"<data.sex<<" "<data.age<<" "<data.place<LChild)
{
temp.ptr=p->LChild;
EnQueue(Q,temp);//左子树进栈
}
if(p->RChild)
{
temp.ptr=p->RChild;
EnQueue(Q,temp);//右子树进栈
}
}
}
void LeverOrder_RtoL_UtoD(BinaryTree *BT) {//从右至左,从上至下遍历一棵二叉树
Queue Q;
QType temp;
BinaryTree *p=BT;
int MaxQueueSize=50;//其值是假设的一个足够大的数
CreatQueue(Q,MaxQueueSize);
temp.ptr=p;
EnQueue(Q,temp);
cout<<"************** "<data.name<<" "<data.number<<"
"<data.sex<<" "<data.age<<" "<data.place<RChild)
{
temp.ptr=p->RChild;
EnQueue(Q,temp);//右子树进栈
}
if(p->LChild)
{
temp.ptr=p->LChild;
EnQueue(Q,temp);//左子树进栈
}
}
数据结构实验报告 二〇一二年 }
void LeverOrder_RtoL_DtoU(BinaryTree *BT)
{//从下至上,从右至左遍历一棵二叉树
Queue Q;
Q.rear=Q.front;
int frontkeep=0;
QType temp;
BinaryTree *q;
BinaryTree *p=BT;
int MaxQueueSize=50;//其值是假设的一个足够大的数
CreatQueue(Q,MaxQueueSize);
temp.ptr=p;
EnQueue(Q,temp);
cout<<"************** "<data.name<<" "<data.number<<"
"<data.sex<<" "<data.age<<" "<data.place<data.name<<" "<data.number<<" "<data.sex<<"
"<data.age<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--)
{
cout<<" "<data.name<<" "<data.number<<" "<data.sex<<" "<data.age<<" "<data.place<data.name<<" "<data.number<<"
"<data.sex<<" "<data.age<<" "<data.place<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--)
{
cout<<" "<data.name<<" "<data.number<<" "<data.sex<<" "<data.age<<" "<data.place<>choice;
cout<
本文档为【二叉树层次遍历】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑,
图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
该文档来自用户分享,如有侵权行为请发邮件ishare@vip.sina.com联系网站客服,我们会及时删除。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。