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

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

2、ude #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=1,表示其后创建的结点将做为这

3、个结点的左孩子结点。2、若ch=)表示栈中结点的左右孩子结点处理完毕，退栈。3、若ch=,表示其后创建的结点为右孩子结点4、其他情况表示要创建一个结点，并根据k值建立它与栈中结点之间的关系，当k=1时，表示这个结点作为栈中结点的左孩子结点，当k=2时，表示这个结点作为栈中结点的右孩子结点。如此循环直到str处理完毕。算法中使用一个栈st保存双亲结点，top为其栈指针，k指定其后处理的结点是双亲结点（保存在栈中）的左孩子结点（k=1）还是右孩子结点（k=2）。*/void CreateBtree(BTNode * &bt,char *str) /由str创建二叉链bt BTNode *stMax

4、Size,*p=NULL; 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:s

5、ttop-lchild=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 (lchilddeprchil

6、ddep)?(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;if(

7、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&bt-rchild=NULL) return 1; else num1=LeafCount(bt-lchild); num2=LeafCount(bt-rchild); return num1+num2; /*以括号表示法输出二叉树运算算法*/void DispBtreel(BTNode *bt) if(bt!=N

8、ULL) coutdata; if(bt-lchild!=NULL|bt-rchild!=NULL) coutlchild); if(bt-rchild!=NULL) coutrchild); cout); /*=* Function name: BT_PreOrder* Parameter: root:树根节点指针* Precondition: None* Description: 前序遍历=*/void BT_PreOrder(BTNode *bt) if (NULL != bt) coutdata;/visit(bt); BT_PreOrder(bt-lchild); BT_PreOrd

9、er(bt-rchild); /*=* Function name: BT_InOrder* Parameter: root:树根节点指针* Precondition: None* Description: 中序遍历* Return value: void=*/void BT_InOrder(BTNode *bt) if (NULL != bt) BT_InOrder(bt-lchild); coutdata;/visit(bt); BT_InOrder(bt-rchild); /*=* Function name: BT_PostOrder* Parameter: root:树根节点指针*

10、Precondition: None* Description: 后序遍历* Return value: void=*/void BT_PostOrder(BTNode *bt) if (NULL != bt) BT_PostOrder(bt-lchild); BT_PostOrder(bt-rchild); coutdata;/visit(bt); /*=* Function name: BT_LevelOrder* Parameter: root:树根节点指针* Precondition: NULL != root* Description: 层序遍历* Return value: voi

11、d=*/void BT_LevelOrder(BTNode *bt) queue q; tnode *treePtr; assert( NULL != bt ); q.push(bt); while (!q.empty() treePtr = q.front(); q.pop(); coutdata;/visit(bt); treePtr; if (NULL != treePtr-lchild) q.push(treePtr-lchild); if (NULL != treePtr-rchild) q.push(treePtr-rchild); /先序中序求后序int find(char c,

12、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=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_

13、s+1,pre_e,in,k+1,in_e); /* 递归求解分割的右子树。 */printf(%c,c); /* 根节点输出。 */#include #include #include #include #include #includetree.h#define SIZE 100 using namespace std; typedef struct BiTNode /定义二叉树节点结构 char data; /数据域 struct BiTNode *lchild,*rchild; /左右孩子指针域 BiTNode,*BiTree; int visit(BiTree t); void Cr

14、eateBiTree(BiTree &T); /生成一个二叉树 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; /取左右深度的

15、最大值 /求结点数return(max+1); else return(0); int TreeNodeNUM(BiTree T) int N=0; int hl,hr,max; if(T) if(T) coutdata; N=N+1;/访问结点 PreOrder(T-lchild); /遍历左子树 PreOrder(T-rchild); /遍历右子树 return N; else return(0); /主函数 void main() BiTree T; char ch; int flag=1; cout二叉树endl; cout请建立二叉树。endl; CreateBiTree(T); /

16、初始化队列 getchar(); while(flag) cout请选择: endl; cout1.先序遍历endl; cout2.中序遍历endl; cout3.后序遍历endl; cout4.层次遍历endl; cout5.树的深度和节点个数endl; cout6.根据前序和中序确定后序endl; cout0.退出程序ch; switch(ch) case 1: if(T) cout递归先序遍历二叉树:; PreOrder(T); coutendl; else cout二叉树为空!endl; break; case 2: if(T) cout递归中序遍历二叉树:; InOrder(T);

17、coutendl; else cout二叉树为空!endl; break; case 3: if(T) cout递归后序遍历二叉树:; PostOrder(T); coutendl; else cout二叉树为空!endl; break; case 4: if (T) cout 层序遍历二叉树:; LeverTraverse(T); cout endl; else cout 二叉树为空!; break; case5:if (T) int depth=0,NodeNum=0; depth=TreeDepth(T); NodeNum=TreeNodeNUM( T); /求树的深度及叶子数 cout

18、树的深度depth 节点个数NodeNumendl; else cout 二叉树为空!; break; case6:if (T) couts0; const char *p0=s0.c_str(); char *pre = new charstrlen(p0)+1; strcpy(pre, p0); couts1; const char *p1=s1.c_str(); char *in = new charstrlen(p1)+1; strcpy(in, p1); cout树的后序为： ; pronum(pre,0,strlen(in)-1,in,0,strlen(pre)-1); else

19、cout 二叉树为空!; break; default: flag=0; cout程序运行结束，按任意键退出!; coutch; /读入一个字符 if(ch=#) T=NULL; else T=(BiTNode *)malloc(sizeof(BiTNode); /生成一个新结点 T-data=ch; CreateBiTree(T-lchild); /生成左子树 CreateBiTree(T-rchild); /生成右子树 /先序遍历的递归 void PreOrder(BiTree T) if(T) coutdata; /访问结点 PreOrder(T-lchild); /遍历左子树 PreO

20、rder(T-rchild); /遍历右子树 /中序遍历的递归 void InOrder(BiTree T) if(T) InOrder(T-lchild); /遍历左子树 coutdata; /访问结点 InOrder(T-rchild); /遍历右子树 /后序遍历的递归 void PostOrder(BiTree T) if(T) PostOrder(T-lchild); /遍历左子树 PostOrder(T-rchild); /访问结点 coutdata; /遍历右子树 void LeverTraverse(BiTree T)/非递归层次遍历 queue Q; BiTree p; p = T; if (visit(p) = 1) Q.push(p); while (!Q.empty() p = Q.front(); Q.pop(); if (visit(p-lchild) = 1) Q.push(p-lchild); if (visit(p-rchild) = 1) Q.push(p-rchild); int visit(BiTree T) if(T) coutdata; return 1; else return 0; 实验结果：