数据结构《实验3》实验报告

实验项目3：二叉树层次遍历

实验结果（运行结果界面及源程序，运行结果界面放在前面）：

数据结构实验报告

二〇一二年

数据结构实验报告

二〇一二年

#include <iostream.h>

#include <string.h>

#include <stdlib.h>

#include <math.h>

#define STUDENT EType

struct STUDENT

{

char number[8];

char name[8];

char sex[3];

int age;

char place[20];

};

struct BinaryTreeNode

{

EType data;

BinaryTreeNode *LChild;

BinaryTreeNode *RChild;

};

struct QType

{

BinaryTreeNode *ptr;

};

struct Queue

{

QType *element;

int front;

int rear;

int maxsize;

};

struct Node_Ptr

{

BinaryTreeNode *ptr;

} ;

void CreatQueue(Queue &Q,int MaxQueueSize)

{//创建队列

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)

{//取出队头元素

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.element[Q.rear];

return true;

}

bool EnQueue(Queue &Q,QType &x)

{//元素进队

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)

{//元素出队

if(IsEmpty(Q)) return false;

Q.front=(Q.front+1)%(Q.maxsize+1);

result=Q.element[Q.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->http://<<

" "<<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.element[i].ptr);

}

void LevelOrder_RtoL_DtoU(BinaryTreeNode *BT)

{//从右至左，从下至 …… 此处隐藏：7855字，全部文档内容请下载后查看。喜欢就下载吧 ……