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

数据结构《实验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)

{//从右至左，从下至上按层次遍历一棵二叉树

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

}

int BinaryHeight(BinaryTreeNode *BT)

{//返回二叉树的高度

if(!BT) return 0;

int HighL=BinaryHeight(BT->LChild);

int HighR=BinaryHeight(BT->RChild);

if(HighL>HighR)

return ++HighL;

else

return ++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)

{

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;i<len/2;i++)

{

temp=str[i];

str[i]=str[len-i-1];

str[len-i-1]=temp;

}

}

char *GetOuputInformationString(int WidthOfData, char *OutputInformation, char *outputstring)

{//将一个元素的字符串OutputInformation转换为宽度为WidthOfData的等长字符串outputstring

//例如，姓名是由四个字符组成，而WidthOfData为8，则在姓名字符串的两边分别连接两个字符，形成8个长度的字符串

int left_space,right_space;

int i;

char left_space_string[16]={""};

char right_space_string[16]={""};

int add_space;

int len_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);

return outputstring; //返回WidthOfData宽度的outputstring

}

char *GetOuputInformation(int item, int k, char *outputInformation, Node_Ptr *element)

{

switch(item)

{

case 1: //线索树特有的处理与一般二叉树不同之处，在姓名的两边连接线索标志 {

strcat(outputInformation,element[k].ptr->http://);

break;

}

case 2:

{

strcat(outputInformation,element[k].ptr->data.number);

break;

}

case 3:

{

strcat(outputInformation,element[k].ptr->data.place);

break;

}

case 4:

{

strcat(outputInformation,element[k].ptr->data.sex);

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=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 ) //&&!p->Lflag//线索树特有的处理与一般二叉树不同之处 {

temp.ptr = p->LChild;

element[2*i]=temp;

}

if (p->RChild ) //&&!p->Rflag//线索树特有的处理与一般二叉树不同之处 {

temp.ptr = p->RChild;

element[2*i+1]=temp;

}

}

}

int WidthOfData=5;

int IntervalOfData=3;

// cout<<"WidthOfData="<<WidthOfData<<endl;

// cout<<"IntervalOfData="<<IntervalOfData<<endl;

// cout<<"BinaryTreeHigh="<<BinaryTreeHigh<<endl;

int position_of_central[6][17]; //存放每一元素输出位置中心（距离屏幕左边界的字符数）

int row,col; //二维数组的行列下标变量

for(i=0;i<=BinaryTreeHigh;i++) //存放每一元素输出位置中心（距离屏幕左边界的字符数），初值为0

for(j=0;j<=pow(2,BinaryTreeHigh-1);j++)

position_of_central[i][j]=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_central[row][col]中的row

col=(int)(i-(pow(2,(row-1))-1)); //计算中心点值存放在position_of_central[row][col]中的col

if(row==BinaryTreeHigh)

//计算底层i结点距离左边界的字符数，左边无间隙

position_of_central[row][col]= (j-1)*WidthOfData + (j-1)*IntervalOfData + (WidthOfData/2 +1);

else

//计算非底层i结点距离左边界的字符数，

position_of_central[row][col]=j*WidthOfData + (j-1)*IntervalOfData + (IntervalOfData/2 +1);

char prespace[100];

int m;

int kk;

int kkk;

int item_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成员的值

{

int half_len_pre_value=0; //同一行前一个输出的元素值长度的一半,同一行第一个输出的元素值前没有值输出，初值为0

int half_len_now_value=WidthOfData/2;//同一行当前输出的元素值长度的一半，其值始终为WidthOfData的一半

kk=kkk; //kk是满二叉树中每一层结点的编号变化，从某层的最左边第一个结点编号kkk开始

for(j=1;j<=pow(2,i-1);j++) //输出满二叉树中同一层次上的每个数据元素的同一个成员的值

{

char outputInformation[20]={""};

char *OutputInformation;

if (element[kk].ptr) //获取每个数据元素的一个成员的值OutputInformation，如姓名、年龄等

OutputInformation=GetOuputInformation(item,kk,outputInformation,element);

if (position_of_central[i][j]) //输出数据中点值存在时，position_of_central[i][j]非0

{

char outputstring[80]={""};

char *OutputString;

//下面语句将每个数据元素的一个成员的值OutputInformation，如姓名、年龄等，转换为等长WidthOfData的字符串OutputString

OutputString=GetOuputInformationString(WidthOfData,OutputInformation,outputstring);

//生成两个孩子之前的空格串prespace

//构成：<前导空格串>=<两个输出数据中心点之差> - <前一个输出元素值长度一半> - <当前输出元素值长度的一半>

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<<prespace;

cout<<OutputString;

half_len_pre_value=WidthOfData/2; //调整同一行前一个输出的元素值长度为WidthOfData的一半

kk++;

}// if (position_of_central[i][j])

}//for(j=1;j<=pow(2,i-1);j++)

cout<<endl;

}//for(int item=1;item<=5;item++)

char line[3]="─";

char OutputLine[80];

char midspace[80];

int nodenumber;

if(i==1) //对深度为BinaryTreeHigh的满二叉树从上至下，从左至右的编号，计算第i层上起始结点的编号nodenumber

nodenumber=1;

else

nodenumber=(int)((pow(2,i)-1)-(pow(2,i-1)-1)); //第i(i!=1)层上的第1个结点编号nodenumber

for(j=1;j<=pow(2,i-1);j++) //输出同一层次上的线条 {

if(i==BinaryTreeHigh) break; //最底层下面没有线条，所以break

//生成两个数据元素之前的前导空格串prespace

strcpy(prespace,"");

m=(position_of_central[i+1][j]-position_of_central[i+1][j-1]-1);