二叉树其他典型算法 数据结构实验报告

南昌航空大学实验报告课程名称:数据结构班级：080611指导教师评定：课程名称:数据结构班级：080611指导教师评定：签实验名称：.实验七二叉树的其他典型算法学生姓名：学号：08名：题目：假设二叉树采用二叉链表结构。设计并实现如下算法：输入某棵二叉树的广义表形式，建立该二叉树，并按层次遍历该二叉树。一、需求分析用户可以根据自己的需求分别输入任意的一个以广义表表示的二叉树，并且以此创建一个二叉树。通过已有的二叉树用层次遍历该树，并输出。并且以广义表的形式输出该二叉树程序执行的命令包括：输入广义表(2)构造二叉树T(2)层次遍历二叉树(3)二叉树以广义表的形式输出(4)求二叉树的结点数(辅助功能，为了输出二叉树)二、概要设计为实现上述算法，需要链表的抽象数据类型：ADTBinarytree{数据对象：D是具有相同特性的数据元素的集合数据关系R：若D为空集，则R为空集，称binarytree为空二叉树；若D不为空集，则R为{H},H是如下二元关系；在D中存在唯一的称为根的数据元素root,它在关系H下无前驱；若D—{root}不为空，则存在D—{root}={D1,Dr}，且DlHDr为空集；若D1不为空，则D1中存在唯一的元素xl,<root,xl〉WH，且存在D1上的关系H1是H的子集；若Dr不为空集，则Dr中存在唯一的元素Xr,<root,Xr〉WH,且存在Dr上的关系Hr为H的子集；H={〈root,xl〉，〈root,Xr〉,Hl,Hr};(D1,{H1})是一颗符合本定义的二叉树，称为根的左子树，(Dr,{Hr})是一颗符合本定义的二叉树，称为根的右子树。基本操作：Creatbitree(&S,definition)初始条件：definition给出二叉树S的定义操作结果：按definition构造二叉树Scounter(T)初始条件：二叉树T已经存在操作结果：返回二叉树的总的结点数Printbitree(T)初始条件：二叉树T已存在操作结果：以广义表的形式输出TClearbintree(S)初始条件：二叉树S已经存在操作结果：将二叉树S清为空树Bitreeempty(S)初始条件：二叉树S已经存在操作结果：若S为空二叉树，则返回TRUE，否则返回FALSEBitreedepth(S，&e)初始条件：二叉树S已经存在操作结果：返回S的深度Parent(S)初始条件：二叉树S已经存在，e是S中的某个结点操作结果：若e是T的非根结点，则返回它的双亲，否则返回空Preordertraverse(S)初始条件：二叉树S已经存在，Visit是对结点操作的应用函数。操作结果：先序遍历S,对每个结点调用函数visit一次且仅一次。一旦visit失败，则操作失败。Inordertraverse(S,&e)初始条件：二叉树S已经存在，Visit是对结点操作的应用函数。操作结果：中序遍历S,对每个结点调用函数visit一次且仅一次。一旦visit失败，则操作失败。Postordertraverse(&S,e)初始条件：二叉树S已经存在，Visit是对结点操作的应用函数。操作结果：后序遍历S,对每个结点调用函数visit一次且仅一次。一旦visit失败，则操作失败。}ADTBinarytree本程序有三个模块：⑴主程序模块main(){初始化；{接受命令；显示结果；}}⑵广义表形式建树的模块：主要建立一棵二叉树；⑶层次遍历模块：输出中序遍历的结果；(4)输出二叉树模块：广义表输出二叉树。三、详细设计

1•元素类型，结点类型/*定义二叉树*/typedefstructbitree{charnode;structbitree*lchild,*rchild;}bitree;/*定义队列元素类型*/typedefstructqnode{bitree*q;}qnode;/*定义队列*/typedefstructqueue{qnode*base;intfront;intrear;intsize;}queue;/*全局变量*/bitree*T;queue*Q;inti=0,a;chars[100];/*存放广义表数组*/对抽象数据类型中的部分基本操作的伪码算法如下:/*广义表创建二叉树*/structbitree*creatbitree2(bitree*T){structbitree*r;structbitree*a[100];/*定义数组栈，存放根节点*/charch;inttop=-1;intk;/*用k作为处理结点的左子树和右子树，k=1处理左子树，k=2处理右子树*/intj=0;T=NULL;while(s[j]!='\0'){ch=s[j];switch(ch){case'#':break;/*#表示没有左孩子或右孩子*/caseif(top==99){printf("stacksizefull！\n");exit(l);}top++;a[top]=r;3k=1;break;caseif(top==-1)exit(1);}{printf("btreebiaoerror!\n");top—;break;exit(1);}casek=2;break;default:r二(bitree*)malloc(sizeof(bitree))r—〉node=ch;r-〉lchild=r-〉rchild=NULL;f(T==NULL){T=r;}else{if(k==1){a[top]->lchild=r;}

else{a[top]->rchild=r;}}}j++;}returnT;}/*求二叉树的结点总数*/intcounter(structbitree*T){intnum1,num2,num;if(T==NULL)return0;else{num1=counter(T->lchild);num2=counter(T->rchild);num=num1+num2+1;returnnum;}}/*创建空队列*/queue*initqueue(){Q-〉base=(qnode*)malloc(MAX*sizeof(qnode));Q—〉front二Q->rear=0;Q->size=MAX;returnQ;}/*判断队列是否为空*/intemptyqueue(queue*q){if(q-〉front==q-〉rear)return1;elsereturn0;}/*入队列*/queue*enqueue(queue*q,bitree*p){q-〉base[q-〉rear].q二p;q—〉rear++;returnq;}/*出队列*/bitree*dequeue(queue*q){intn;if(q-〉front==q-〉rear){printf("thequeueisNULL!\n");return0;}n二q—〉front;q—〉front++;return(q-〉base[n].q);}/*层次遍历*/voidlevelorder(bitree*t){bitree*p;Q=initqueue();if(t!=NULL){enqueue(Q,t);while(!emptyqueue(Q)){p=dequeue(Q);visit(p-〉node);if(p-〉lchild!=NULL)enqueue(Q,p-〉lchild);if(p-〉rchild!二NULL)enqueue(Q,p-〉rchild);}}}/*广义表形式输出二叉树*/voidprintBTree(bitree*T){if(T!=NULL)/*树为空时结束递归，否则执行如下操作*/{printf("%c",T-〉node);/*输出根结点的值*/辻(T-〉lchild!=NULL||T-〉rchild!=NULL){printf("(");printBTree(T-〉lchild);辻(T-〉rchild!=NULL){printf(〃,〃)；}printBTree(T-〉rchild);printf(〃)〃)；}}}主函数和其他函数的伪码算法intmain(void){intsum;printf("\n\ninputguangyibiao:\n");gets(s);/*输入广义表*/T=creatbitree2(T);/*广义表创建树*/printf("\n\nthebitreedezongjiedianshu:\n");a=counter(T);printf("a=%d\n",a);/*输出树的总结点数*/printf("\n\nouputthebtreebiao\n");printBTree(T);/*二叉树以广义表输出*/printf("\n\ncengcibianliresult:\n");levelorder(T);/*层次遍历的结果*/getch();return0;}/*访问元素*/voidvisit(charch){if(i!=(a-1)){printf("%c-〉",ch);i++；}else{printf("%c",ch);printf(〃\n〃)；}}4函数调用关系#}/*求二叉树的结点总数*/intcounter(structbitree*T){intnuml,num2,num;if(T==NULL)return0;else{num1=counter(T-〉lchild);num2=counter(T-〉rchild);num二numl+num2+l;returnnum;}}/*创建空队列*/queue*initqueue(){Q-〉base=(qnode*)malloc(MAX*sizeof(qnode));Q—〉front二Q—〉rear=0;Q->size=MAX;returnQ;}/*判断队列是否为空*/intemptyqueue(queue*q){if(q-〉front==q-〉rear)return1;elsereturn0;}/*入队列*/queue*enqueue(queue*q,bitree*p){q-〉base[q-〉rear].q二p;q—〉rear++;returnq;}/*出队列*/bitree*dequeue(queue*q){intn;if(q-〉front==q-〉rear){printf("thequeueisNULL!\n");return0;}n二q—〉front;q—〉front++;return(q-〉base[n].q);}/*层次遍历*/voidlevelorder(bitree*t){bitree*p;Q=initqueue();if(t!=NULL){enqueue(Q,t);while(!emptyqueue(Q)){p=dequeue(Q);visit(p-〉node);if(p-〉lchild!=NULL)enqueue(Q,p-〉lchild);if(p-〉rchild!二NULL)enqueue(Q,p-〉rchild);}}}/*广义表形式输出二叉树*/voidprintBTree(bitree*T){if(T!=NULL)/*树为空时结束递归，否则执行如下操作*/

{printf("%c",T-〉node);/*输出根结点的值*/辻(T-〉lchild!=NULL||T-〉rchild!=NULL){printf("(");printBTree(T-〉lchild);辻(T-〉rchild!=NULL){printf(〃,〃)；}printBTree(T-〉rchild);printf(〃)〃)；}}}/*主函数*/intmain(void){intsum;printf("\n\ninputguangyibiao:\n");gets(s);/*输入广义表