山东大学数据结构实验报告五样本.doc

文档介绍：数据结构试验汇报——试验五 试验题目:排序算法学号:日期:.::刘方铮Email:试验目标:二叉树操作任务要求: 一、试验目标1、掌握二叉树基础概念,链表描述方法;遍历方法。二、试验内容创建二叉树类。二叉树存放结构使用链表。提供操作:前序遍历、中序遍历、后序遍历、层次遍历、计算二叉树结点数目、计算二叉树高度。对建立好二叉树,实施上述各操作。接收键盘录入二叉树前序序列和中序序列(各元素各不相同),输出该二叉树后序序列。软件环境:Win7操作系统开发工具:visualC++:#include<iostream>#include<>#include<>#include<>usingnamespacestd;#defineMaxSize100#defineMaxWidth40#include<stack>#include<queue>#include<>#include<string>typedefcharElemType;typedefstructtnode{ ElemTypedata; structtnode*lchild,*rchild;}BTNode;/*建立二叉树算法描述:用ch扫描采取括号表示法表示二叉树字符串Str。分以下多个情况:1、若ch='('则将前面刚创建结点作为双亲结点进栈,并置k=1,表示其后创建结点将做为这个结点左孩子结点。2、若ch=')'表示栈中结点左右孩子结点处理完成,退栈。3、若ch=','表示其后创建结点为右孩子结点4、其它情况表示要创建一个结点,并依据k值建立它和栈中结点之间关系,当k=1时,表示这个结点作为栈中结点左孩子结点,当k=2时,表示这个结点作为栈中结点右孩子结点。如此循环直到str处理完成。算法中使用一个栈st保留双亲结点,top为其栈指针,k指定其后处理结点是双亲结点(保留在栈中)左孩子结点(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!='\0')//str未扫描完时循环 { switch(ch) { case'(':top++;st[top]=p;k=1;break;//为左孩子结点 case')':top--;break; case',':k=2;break; default:p=(BTNode*)malloc(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; 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=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; else if(bt->lchil