山东大学数据结构实验报告五

《山东大学数据结构实验报告五》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构实验报告——实验五 实验题目：排序算法学号：201411130001日期：2015.12.11班级：计机14.1姓名：刘方铮Email：liu191150932@163.com实验目的：二叉树操作任务要求： 一、实验目的1、掌握二叉树的基本概念，链表描述方法；遍历方法。二、实验内容创建二叉树类。二叉树的存储结构使用链表。提供操作:前序遍历、中序遍历、后序遍历、层次遍历、计算二叉树结点数目、计算二叉树高度。对建立好的二叉树，执行上述各操作。接收键盘录入的二叉树前序序列和中序序列(各元素各不相同)，输出该二叉树的后序序列。软件环境：Win7操作系统开发工具：visualC++

2、6.0实验代码：#include#include#include#includeusingnamespacestd;#defineMaxSize100#defineMaxWidth40#include#include#include#includetypedefcharElemType;typedefstructtnode{ElemTypedata;structtnode*lchild,*rchild;}BTNode;/*建立二叉树算法描述：

3、用ch扫描采用括号表示法表示二叉树的字符串Str。分以下几种情况：1、若ch='('则将前面刚创建的结点作为双亲结点进栈，并置k=1,表示其后创建的结点将做为这个结点的左孩子结点。2、若ch=')'表示栈中结点的左右孩子结点处理完毕，退栈。3、若ch=','表示其后创建的结点为右孩子结点4、其他情况表示要创建一个结点，并根据k值建立它与栈中结点之间的关系，当k=1时，表示这个结点作为栈中结点的左孩子结点，当k=2时，表示这个结点作为栈中结点的右孩子结点。如此循环直到str处理完毕。算法中使用一个栈st保存双亲结点，top为其栈指针，k指定其后处理的结点是双亲结点（保存在栈中）的左

4、孩子结点（k=1）还是右孩子结点（k=2）。*/voidCreateBtree(BTNode*&bt,char*str)//由str创建二叉链bt{BTNode*st[MaxSize],*p=NULL;inttop=-1,k,j=0;charch;bt=NULL;//建立的二叉树初始为空ch=str[j];while(ch!='')//str未扫描完时循环{switch(ch){case'(':top++;st[top]=p;k=1;break;//为左孩子结点case')':top--;break;case',':k=2;break;default:p=(BTNode*)m

5、alloc(sizeof(BTNode));p->data=ch;p->lchild=p->rchild=NULL;if(bt==NULL)bt=p;else{switch(k){case1:st[top]->lchild=p;break;case2:st[top]->rchild=p;break;}}}j++;ch=str[j];}}/*求二叉树高度算法：递归模型如下if(b==NULL)f(b)=0;elsef(b)=max{f(b)->lchild,f(b)->rchild}+1;*/intBTHeight(BTNode*bt){intlchilddep,rchilddep

6、;if(bt==NULL)return0;else{lchilddep=BTHeight(bt->lchild);rchilddep=BTHeight(bt->rchild);return(lchilddep>rchilddep)?(lchilddep+1):(rchilddep+1);}}/*求二叉树结点个数算法：递归模型如下if(bt==NULL)f(b)=1;elsef(bt)=f(bt->lchild)+f(bt->rchild)+1;*/intNodeCount(BTNode*bt){intnum1,num2;if(bt==NULL)return0;else{num1=

7、NodeCount(bt->lchild);num2=NodeCount(bt->rchild);returnnum1+num2+1;}}/*求二叉树叶子结点个数算法：递归模型如下if(bt==NULL)f(bt)=0;if(bt为叶子结点)f(bt)=1;elsef(bt)=f(bt->lchild)+f(bt->rchild);*/intLeafCount(BTNode*bt){intnum1,num2;if(bt==NULL)return0;elseif(bt->lchil