《山东大学数据结构实验报告五》由会员分享，可在线阅读，更多相关《山东大学数据结构实验报告五（16页珍藏版）》请在金锄头文库上搜索。
1、数据结构实验报告实验五实验题目：排序算法 学号：201411130001 日期：2015.12.11班级：计机 14.1姓名：刘方铮 Email： 实验目的：二叉树操作 任务要求：一、实验目的 1、掌握二叉树的基本概念，链表描述方法；遍历方法。 二、实验内容 创建二叉树类。二叉树的存储结构使用链表。提供操作:前序遍历、中序遍历、后序遍历、层次遍历、计算二叉树结点数目、计 算二叉树高度。对建立好的二叉树，执行上述各操作。接收键盘录入的二叉树前序序列和中序序列(各元素各不相同)，输出该二叉树的后 序序列。软件环境： Win7 操作系统 开发工具：visual C+ 6.0实验代码：#include
2、 #include #include #include using namespace std; #define MaxSize 100 #define MaxWidth 40 #include #include #include #includetypedef char ElemType;typedef struct tnode ElemType data; struct tnode *lchild,*rchild; BTNode;/*建立二叉树算法描述： 用 ch 扫描采用括号表示法表示二叉树的字符串 Str。分以下几种情况： 1、若 ch=(则将前面刚创建的结点作为双亲结点进栈，并置 k
3、=1,表示其后创建 的结点将做为这个结点的左孩子 结点。 2、若 ch=)表示栈中结点的左右孩子结点处理完毕，退栈。 3、若 ch=,表示其后创建的结点为右孩子结点 4、其他情况表示要创建一个结点，并根据 k 值建立它与栈中结点之间的关系， 当 k=1 时，表示这个结点作为栈中 结点的左孩子结点，当 k=2 时，表示这个结点作为栈中结点的右孩子结点。如 此循环直到 str 处理完毕。算法中 使用一个栈 st 保存双亲结点，top 为其栈指针，k 指定其后处理的结点是双亲结 点（保存在栈中）的左孩子结点 （k=1）还是右孩子结点（k=2） 。 */ void CreateBtree(BTNode
4、 * int top=-1,k,j=0; char ch; bt=NULL; /建立的二叉树初始为空 ch=strj; while(ch!=0) /str 未扫描完时循环 switch(ch) case (:top+;sttop=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) case 1:sttop-lchil
5、d=p;break; case 2:sttop-rchild=p;break; j+; ch=strj; /*求二叉树高度算法： 递归模型如下 if(b=NULL) f(b)=0; else f(b)=maxf(b)-lchild,f(b)-rchild+1; */ int BTHeight(BTNode *bt) int lchilddep,rchilddep; if(bt=NULL) return 0; else lchilddep=BTHeight(bt-lchild); rchilddep=BTHeight(bt-rchild); return (lchilddeprchilddep)
6、?(lchilddep+1):(rchilddep+1); /*求二叉树结点个数算法： 递归模型如下 if(bt=NULL) f(b)=1; else f(bt)=f(bt-lchild)+f(bt-rchild)+1; */ int NodeCount(BTNode *bt) int num1,num2; if(bt=NULL) return 0; else num1=NodeCount(bt-lchild); num2=NodeCount(bt-rchild); return num1+num2+1; /*求二叉树叶子结点个数算法： 递归模型如下 if(bt=NULL) f(bt)=0;
7、if(bt 为叶子结点) f(bt)=1; else f(bt)=f(bt-lchild)+f(bt-rchild); */ int LeafCount(BTNode *bt) int num1,num2; if(bt=NULL) return 0; else if(bt-lchild=NULL else num1=LeafCount(bt-lchild); num2=LeafCount(bt-rchild); return num1+num2; /*以括号表示法输出二叉树运算算法*/ void DispBtreel(BTNode *bt) if(bt!=NULL) coutdata; if(
8、bt-lchild!=NULL|bt-rchild!=NULL) coutlchild); if(bt-rchild!=NULL) coutrchild); coutdata;/visit(bt);BT_PreOrder(bt-lchild);BT_PreOrder(bt-rchild); /*= = * Function name: BT_InOrder * Parameter: root:树根节点指针 * Precondition: None * Description: 中序遍历 * Return value: void = =*/ void BT_InOrder(BTNode *bt)
9、 if (NULL != bt)BT_InOrder(bt-lchild);coutdata;/visit(bt);BT_InOrder(bt-rchild); /*= = * Function name: BT_PostOrder * Parameter: root:树根节点指针 * Precondition: None * Description: 后序遍历 * Return value: void =*/ void BT_PostOrder(BTNode *bt) if (NULL != bt)BT_PostOrder(bt-lchild);BT_PostOrder(bt-rchild)
10、;coutdata;/visit(bt); /*= = * Function name: BT_LevelOrder * Parameter: root:树根节点指针 * Precondition: NULL != root * Description: 层序遍历 * Return value: void = =*/ void BT_LevelOrder(BTNode *bt) queue q;tnode *treePtr;assert( NULL != bt ); q.push(bt);while (!q.empty()treePtr = q.front();q.pop();coutdata
11、;/visit(bt); treePtr;if (NULL != treePtr-lchild)q.push(treePtr-lchild); if (NULL != treePtr-rchild)q.push(treePtr-rchild); /先序中序求后序 int find(char c,char A,int s,int e) /* 找出中序中根的位置。 */ int i; for(i=s;iin_e) return ; /* 非法子树，完成。 */ if(in_s=in_e)printf(“%c“,inin_s); /* 子树子仅为一个节点时直接输出并完成。 */return ; c=
12、prepre_s; /* c 储存根节点。 */ k=find(c,in,in_s,in_e); /* 在中序中找出根节点的位置。 */ pronum(pre,pre_s+1,pre_s+k-in_s,in,in_s,k-1); /* 递归求解分割的左子树。 */ pronum(pre,pre_s+k-in_s+1,pre_e,in,k+1,in_e); /* 递归求解分割的右子树。 */ printf(“%c“,c); /* 根节点输出。 */ #include #include #include #include #include #include“tree.h“ #define SIZE
13、 100 using namespace std; typedef struct BiTNode /定义二叉树节点结构 char data; /数据域 struct BiTNode *lchild,*rchild; /左右孩子指针域 BiTNode,*BiTree; int visit(BiTree t); void CreateBiTree(BiTree /生成一个二叉树 void PreOrder(BiTree); /递归先序遍历二叉树 void InOrder(BiTree); /递归中序遍历二叉树 void PostOrder(BiTree); /递归后序遍历二叉树 void LeverTraverse(BiTree T);/非递归层次遍历 int TreeDepth(BiTree T) int hl,hr,max; if(T) hl=TreeDepth(T-lchild); /求左深度 hr=TreeDepth(T-rchild); /求右深度max=hlhr?hl:hr; /取左右深度的最大值/求结
