二叉树抽象数据类型数据结构实验报告

-z.数据构造实验报告题目：二叉树抽象数据类型的实现学院***学院专业*********年级班别***********学号***********学生*************指导教师成绩____________________2012年6月报告：容： □详细 □完整 □不完整设计方案： □非常合理 □合理 □较差实现： □全部实现 □局部实现 □未实现文档格式： □规 □根本规 □不规辩论：□理解题目透彻，问题答复流利□理解题目较透彻，答复下列问题根本正确□局部理解题目，局部问题答复正确□未能完全理解题目，辩论情况较差总评成绩：□优□良□中□及格□不及格-z.一．实验概要二叉树抽象数据类型的实现二.实验目的了解二叉树的定义以及各项根本操作。实现二叉树存储、遍历及其他根本功能三.实验仪器设备和材料Visualstudio2010四．实验的容1.二叉树类型定义以及各根本操作的简要描述；ADTBinaryTree{数据对象D:D是具有一样特性的数据元素的集合.数据关系R:假设D=∅，则R=,称BinaryTree为空二叉树；假设D≠，则R={H}，H是如下二元关系：在D中存在惟一的称为根的数据元素root，它在关系H下无前驱；假设D-{root}≠∅，则存在D-{root}={D1,Dr}，且D1∩Dr=∅；假设D1≠∅，则D1中存在惟一的元素*1，<root，*1>∈H，且存在Dr上的关系Hr∈H；H={<root，*1>，<root，*r>，H1,Hr}；〔D1，{H1}〕是一棵符合本定义的二叉树，称为根的左子树，是一棵符合本定义的二叉树，称为根的右子树。根本操作P:InitBiTree(&T);操作结果：构造空二叉树T。DestroyBiTree(&T);初始条件：二叉树T存在。操作结果：销毁二叉树T。CreateBiTree(&T,definition);初始条件：definition给出二叉树T的定义。操作结果：按definition构造二叉树T。ClearBiTree(&T);初始条件：二叉树T存在。操作结果：将二叉树T清为空树。BiTreeEmpty(T);初始条件：二叉树T存在。操作结果：假设T为空二叉树，则返回TURE,否则FALSE。BiTreeDepth(T);初始条件：二叉树T存在。操作结果：返回T的深度。Root(T);初始条件：二叉树T存在。操作结果：返回T的根。Value(T,e);初始条件：二叉树T存在，e是T中的*个结点。操作结果：返回e的值。Assign(T,&e,value);初始条件：二叉树T存在，e是T中的*个结点。操作结果：结点e赋值为value。Parent(T,e);初始条件：二叉树T存在，e是T中的*个结点。操作结果：假设e是T的非跟结点，则返回它的双亲，否则返回“空〞。LeftChild(T,e);初始条件：二叉树T存在，e是T中的*个结点。操作结果：返回e的左孩子。假设e无左孩子，则返回“空〞。RightChild(T,e);初始条件：二叉树T存在，e是T中的*个结点。操作结果：返回e的右孩子。假设e无右孩子，则返回“空〞。LeftSibling(T,e);初始条件：二叉树T存在，e是T中的*个结点。操作结果：返回e的左兄弟。假设e无左孩子或无左兄弟，则返回“空〞。RightSibling(T,e);初始条件：二叉树T存在，e是T中的*个结点。操作结果：返回e的右兄弟。假设e无右孩子或无右兄弟，则返回“空〞。}ADTBinaryTree2.所选择的存储构造描述及在此存储构造上各根本操作的实现；3.源代码主文件:main.ccp:#include"base.h" //公用头文件、公共常量及公共函数等#include"bitree.h" //二叉树二叉链表根本操作void Menu(); //菜单函数void Produce(char*str); //随机产生二叉树先序序列函数int main() //主函数{ BiTree T,bt,insert_bt; char cmd,str[MA*SIZE],elem; int loc,temp; InitBiTree(T); //初始化二叉链表二叉树 Menu(); //显示菜单 while(1) { ClearLine(); //清空结果显示区 printf("请选择操作：(按‘Q'退出)"); cmd=getch(); ClearLine(); fflush(stdin); switch(cmd) { case'0'://随机创立一棵二叉树 while(cmd!='y'&&cmd!='Y') { Produce(str); //随机产生二叉树先序序列 CreateBiTree(T,str);//用此序列建树 ShowBiTree(T); //广义表形式显示 printf("使用创立的这个二叉树<Y/N>?"); cmd=getch(); ClearLine(); } break; case'2'://手动创立一棵二叉树 printf("请按二叉树先序序列输入二叉树：(空结点用空格''表示)\n"); CreateBiTree(T); ClearLine(); printf("二叉树创立成功!\n"); ShowBiTree(T); getch(); break; case'4'://销毁二叉树 DestroyBiTree(T); printf("二叉树已被销毁!"); getch(); break; case'6'://判空 if(BiTreeEmpty(T))printf("二叉树是空二叉树。"); else printf("二叉树非空"); getch(); break; case'8'://求深度 printf("深度是%d",BiTreeDepth(T)); getch(); break; case'a'://求左孩子 ShowBiTree(T); printf("你想求哪个字符的左孩子？"); do{ elem=getchar(); ClearLine(); bt=SearchBiTree(T,elem); //查找指定的结点值elem if(!bt)printf("你输入的结点不存在!请重新输入："); }while(!bt); ClearLine(); bt=LeftChild(T,bt); //求左孩子 if(bt)printf("%c的左孩子是%c",elem,bt->data); else printf("%c没有左孩子",elem); printf("\n参照二叉树:"); ShowBiTree(T); getch(); break; case'c'://求右孩子 ShowBiTree(T); printf("你想求哪个字符的右孩子？"); do{ elem=getchar(); ClearLine(); bt=SearchBiTree(T,elem); if(!bt)printf("你输入的结点不存在!请重新输入："); }while(!bt); ClearLine(); bt=RightChild(T,bt); if(bt)printf("%c的右孩子是%c",elem,bt->data); else printf("%c没有右孩子",elem); printf("\n参照二叉树:"); ShowBiTree(T); getch(); break; case'1'://先序遍历 if(!BiTreeEmpty(T)) { printf("先序遍历序列为："); PreOrderTraverse(T,Visit); } elseprintf("二叉树空，请先建树!"); getch(); break; case'3'://中序遍历 if(!BiTreeEmpty(T)) { printf("中序遍历序列为："); InOrderTraverse(T,Visit); } elseprintf("二叉树空，请先建树!"); getch(); break; case'5'://后序遍历 if(!BiTreeEmpty(T)) { printf("后序遍历序列为："); PostOrderTraverse(T,Visit); } elseprintf("二叉树空，请先建树!");getch(); break; case'7'://层次遍历 if(!BiTreeEmpty(T)) { printf("层次遍历序列为："); LevelOrderTraverse(T,Visit); } elseprintf("二叉树空，请先建树!"); getch(); break; case'9'://插入一棵二叉树为另一棵二叉树的子树 do{ //随机创立一棵右孩子为空 Produce(str); //且层数小于4的树 CreateBiTree(insert_bt,str); }while(insert_bt->rchild||BiTreeDepth(insert_bt)>3); printf("先随机创立一棵右子树空的二叉树如图\n"); ShowBiTree(insert_bt); //新创立的树 getch(); printf("你想插入这棵树为原树哪个结点的子树:\n"); ShowBiTree(T); bt=SearchBiTree(T,getchar()); ClearLine(); printf("你想插入为0.左孩子1.右孩子:"); fflush(stdin); scanf("%d",&loc); if(!InsertChild(T,bt,loc,insert_bt)) printf("插入出错!"); else{ ClearLine(); printf("插入成功!插入后T广义表形式为:\n"); ShowBiTree(T); } getch(); break; case'b'://删除指定结点的子树 ShowBiTree(T); printf("你想删除哪个结点的子树?"); fflush(stdin); bt=SearchBiTree(T,getchar()); printf("\n你想删除0.左子树1.右子树:"); fflush(stdin); scanf("%d",&loc); ClearLine(); if(!DeleteChild(T,bt,loc))printf("删除出错!"); elseprintf("删除成功，检查结果\n"); ShowBiTree(T); getch(); break; case'e'://返回先序序列第i个结点的值 printf("请输入一个结点的先序序列序号:"); scanf("%d",&loc); temp=loc; ClearLine(); elem=Value(T,temp); printf("参照二叉树:"); ShowBiTree(T); printf("\n"); if(elem=='') printf("该结点不存在。"); elseprintf("先序序列第%d个结点值为%c",loc,elem); getch();break; case'd'://结点赋值 ShowBiTree(T); printf("请输入要赋值的结点:"); do{ elem=getchar(); ClearLine(); bt=SearchBiTree(T,elem); if(!bt)printf("你输入的结点不存在!请重新输入："); }while(!bt);; ClearLine(); printf("请输入新值:"); fflush(stdin); elem=getchar(); Assign(T,bt,elem); printf("赋值成功，请查看二叉树状态.\n"); ShowBiTree(T); getch(); break; case'Q'://退出 case'q':e*it(0); } } return0;}void Menu()//显示菜单函数{ printf("0.随机创立CreateBiTree()1.先序遍历PreOrderTraverse()"); printf("\n\n2.手动创立CreateBiTree()3.中序遍历InOrderTraverse()"); printf("\n\n4.销毁DestoryBiTree()5.后序遍历PostOrderTraverse()"); printf("\n\n6.判空BiTreeEmpty()7.层次遍历LevelOrderTraverse()"); printf("\n\n8.求深度BiTreeDepth()9.插入子树InsertChild()"); printf("\n\na.求左孩子LeftChild()b.删除子树DeleteChild()"); printf("\n\nc.求右孩子RightChild()d.结点赋值Assign()"); printf("\n\ne.求结点值Value()"); printf("\n~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n");}void Produce(char*str)//用随机数产生二叉树层次字符序列//使所有节点的字符不一样，空节点用‘&’表示{ int e*ist[27],i,elem,ma*nodes=rand()%41; while(ma*nodes<15||ma*nodes>31)ma*nodes=rand()%41; /*随机产生一个大于15小于31的随机数作为结点个数*/ for(i=0;i<27;i++)e*ist[i]=0; //初始化存在数组，用于使所有结点值不同 i=1; while(i<ma*nodes) { elem=rand()%26; if(!e*ist[elem]&&str[i/2]!='&')//结点未生成且存在父节点 { str[i++]=elem+'A'; e*ist[elem]=1; } elsestr[i++]='&'; } str[i]='\0';}头文件:base.h:#include"stdio.h"#include"conio.h"#include"stdlib.h"#include"windows.h"#include"malloc.h"#include"math.h"#define OK 1#define TRUE 1#define ERROR 0#define FALSE 0#define MA*SIZE 100 typedef int Status;typedef char TElemType; short where*() //返回光标的*坐标{ CONSOLE_SCREEN_BUFFER_INFOcsbinfo; GetConsoleScreenBufferInfo(GetStdHandle(STD_OUTPUT_HANDLE),&csbinfo); returncsbinfo.dwCursorPosition.*;}short wherey() //返回光标的y坐标{ CONSOLE_SCREEN_BUFFER_INFOcsbinfo; GetConsoleScreenBufferInfo(GetStdHandle(STD_OUTPUT_HANDLE),&csbinfo); returncsbinfo.dwCursorPosition.Y;}voidgoto*y(short*,shorty) //移动光标到〔*，y〕坐标{ COORDpoint={*,y};SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE),point);}voidClearLine(unsignedy=17)//去除第y行与y+1行的字符，并使光标在行首，默认去除第17至19行{ for(inti=0;i<256;i++) { goto*y(i,y); putchar(''); } goto*y(0,wherey()-3);}voidClearAera(unsigned*=96,unsignedy=17)//去除(0,y)-(*,y+1)区域的字符，并使光标移动到y{ for(unsignedi=0;i<*;i++) { goto*y(i%(*/2),y+(i/48)); putchar(''); } goto*y(0,y);}Status Visit(TElemTypee)//二叉树结点visit函数，显示字符的值{ printf("%c",e); returnOK;}******************华美的分割线***********************bitree.h:typedefchar TElemType;typedef struct BiTNode{ TElemType data; struct BiTNode *lchild; struct BiTNode *rchild;//左右孩子指针}BiTNode,*BiTree; void InitBiTree(BiTree&T)//构造空二叉树T{ T=NULL;} Status DestroyBiTree(BiTree&T)//销毁二叉树T{ if(!T) returnERROR; DestroyBiTree(T->lchild); //删除左子树 DestroyBiTree(T->rchild); //删除右子树 free(T); T=NULL; returnOK;}Status CreateBiTree(BiTree&T)//先序建立二叉树T,空格表示空结点{ TElemTypech; fflush(stdin); ch=getche(); if(ch=='')T=NULL; else{ T=(BiTree)malloc(sizeof(BiTNode)); if(!T)e*it(OVERFLOW); T->data=ch; //生成头结点 CreateBiTree(T->lchild); //构造左子树 CreateBiTree(T->rchild); //构造右子树 } returnOK;}Status CreateBiTree(BiTree&T,char*str,unsignedi=1)//str储存着二叉树的层次序列，str[i]=='&'表示结点不存在//i为当前要创立结点对应的数组序号节点//由字符数组str先序建立一棵二叉树T{ if(str[i]=='&'||i>=strlen(str))T=NULL; //第i个结点不存在 else{ T=(BiTree)malloc(sizeof(BiTNode)); if(!T)e*it(OVERFLOW); T->data=str[i]; //生成根节点 CreateBiTree(T->lchild,str,i*2); //构造左子树 CreateBiTree(T->rchild,str,i*2+1); //构造右子树 } returnOK;}Status BiTreeEmpty(BiTreeT)//假设T为空二叉树，则返回TRUE，否则返回FALSE{ if(!T) returnTRUE; else returnFALSE;}int BiTreeDepth(BiTreeT) //返回T的深度//利用层次遍历求深度{ if(!T)return0; BiTree queue[200]; intdep=0; int rear=0,front=0; queue[rear++]=T; while(rear!=front) {T=queue[front++]; if(T->data) { dep++; if(T->lchild)queue[rear++]=T->lchild; if(T->rchild)queue[rear++]=T->rchild; } elsedep--; } returndep;}TElemType Value(BiTreeT,int &k)//返回二叉树先序遍历第k个节点的值，不存在则返回空格''{ if(!T||k<1) return''; if(--k==0&&T) returnT->data; BiTree stack[100],p=T; //定义数组栈 int top=0,i=-1; //初始化栈顶指针 while(p||top>0) //当结点不空或栈不空 { if(p) {i++; if(i==k) returnp->data; stack[top++]=p; //根指针入栈，遍历左子树 p=p->lchild; } else{ //根指针退栈，遍历右子树 p=stack[--top]; p=p->rchild; } }}void Assign(BiTreeT,BiTree&p,TElemTypevalue)//二叉树T存在，e是T中*个结点//结点p赋值为value{ if(p)p->data=value;}BiTree LeftChild(BiTreeT,BiTreep)//返回p的左孩子。假设p无左孩子，则返回“空〞{ returnp->lchild;}BiTree RightChild(BiTreeT,BiTreep)//返回p的右孩子。假设p无右孩子，则返回“空〞{ returnp->rchild;}Status InsertChild(BiTree&T,BiTree&p,intLR,BiTree&c)//二叉树T存在，p指向T中*个结点，LR为0或1，非空二叉树c与T不相交且右子树为空。//根据LR为0或1，插入c为T中p所指向结点的左或右子树。//p所指结点的原有左或右子树则成为c的右子树。{ if(!T||!c||!p||(LR!=0&&LR!=1)) returnERROR; //不符合条件 if(LR==0) //插入为左子树 { c->rchild=p->lchild; p->lchild=c; } if(LR==1) //插入为右子树 { c->rchild=p->rchild; p->rchild=c; } returnOK;}Status DeleteChild(BiTree&T,BiTree&p,int LR)//p指向T中*个结点，LR为0或1.//用队列，根据LR为0或1，删除T中P所指结点的左或右子树{ if(!T||!p||(LR!=1&&LR!=0)) returnERROR; BiTree queue[200]; //定义数组队列 int rear=0,front=0; //初始化队列的头指针和尾指针 if(LR==0&&p->lchild) //LR为0且所删除左孩子存在 { queue[rear++]=p->lchild; //则左孩子入队 p->lchild=NULL; } if(LR==1&&p->rchild) //LR为1且所删除右孩子存在 { queue[rear++]=p->rchild; //则右孩子入队 p->rchild=NULL; } while(rear!=front) //用队列层次遍历，删除所要求的子树 { p=queue[front++]; if(p->lchild)queue[rear++]=p->lchild; if(p->rchild)queue[rear++]=p->rchild; free(p); } returnOK;}Status PreOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)) //非递归先序遍历二叉树。对每个节点调用Visit函数{BiTree stack[100],p=T; //定义数组栈 int top=0; //初始化栈顶指针 while(p||top>0) //当结点不空或栈不空 { if(p) { if(!Visit(p->data)) //访问根节点 returnERROR; stack[top++]=p; //根指针入栈，遍历左子树 p=p->lchild; } else{ //根指针退栈，遍历右子树 p=stack[--top]; p=p->rchild; } } returnOK;}Status InOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee))//非递归中序遍历二叉树，对每个节点调用Visit。{ BiTree stack[100],p=T; //定义数组栈 int top=0; //初始化栈顶指针 while(p||top>0) { if(p) //根指针入栈，遍历左子树 { stack[top++]=p; p=p->lchild; } else{ //根指针退栈，遍历右子树 p=stack[--top]; if(!Visit(p->data)) returnERROR; p=p->rchild; } } returnOK;}Status PostOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee))//用栈非递归后序遍历二叉树T。//与非递归先序中序的区别在于，多定义一visited数组，用来记录访问次数//第二次访问时才退栈。{ BiTree stack[100],p=T; //定义数组栈 int top=0,visited[100]; //初始化栈顶指针与访问次数数组 while(p||top>0) { if(p) //遍历左子树，置访问数组为第一次访问 { stack[top++]=p; visited[top-1]=0; p=p->lchild; } else{ if(visited[top-1]==0)//假设栈顶结点只访问一次，遍历右子树 { p=stack[top-1]; visited[top-1]++; p=p->rchild; } elseif(visited[top-1]==1)//假设第二次访问，则根指针退栈，访问根节点。 if(!Visit(stack[--top]->data))returnERROR; } } returnOK;}Status LevelOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee))//用队列层次遍历二叉树T。//对每个结点调用函数Visit一次且