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

数据结构实验报告实验五实验题目：排序算法 学号：201411130001日期：2015.12.11班级：计机14.1姓名：刘方铮Email：实验目的：二叉树操作 任务要求：一、实验目的 1、掌握二叉树的基本概念，链表描述方法；遍历方法。二、实验内容 创建二叉树类。二叉树的存储结构使用链表。提供操作:前序遍历、中序遍历、后序遍历、层次遍历、计算二叉树结点数目、计算二叉树高度。对建立好的二叉树，执行上述各操作。接收键盘录入的二叉树前序序列和中序序列(各元素各不相同)，输出该二叉树的后序序列。软件环境：Win7 操作系统开发工具：visual C+ 6.0实验代码：#include #include #include #include using namespace std;#define MaxSize 100#define MaxWidth 40#include #include #include #includetypedef char ElemType;typedef struct tnodeElemType data;struct tnode *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）。*/void CreateBtree(BTNode * &bt,char *str) /由str创建二叉链btBTNode *stMaxSize,*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;elseswitch(k)case 1:sttop-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;elselchilddep=BTHeight(bt-lchild);rchilddep=BTHeight(bt-rchild);return (lchilddeprchilddep)?(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;elsenum1=NodeCount(bt-lchild);num2=NodeCount(bt-rchild);return num1+num2+1;/*求二叉树叶子结点个数算法：递归模型如下if(bt=NULL) f(bt)=0;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&bt-rchild=NULL)return 1;elsenum1=LeafCount(bt-lchild);num2=LeafCount(bt-rchild);return num1+num2;/*以括号表示法输出二叉树运算算法*/void DispBtreel(BTNode *bt)if(bt!=NULL)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_PreOrder(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:树根节点指针* 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: 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;/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=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 #includetree.h#define SIZE 100 using namespace std; typedef struct BiTNode /定义二叉树节点结构 char data; /数据域 struct BiTNode *lchild,*rchild; /左右孩子指针域 BiTNode,*BiTree; int visit(BiTree t); void CreateBiTree(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; /取左右深度的最大值 /求结点数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; elsereturn(0); /主函数 void main() BiTree T; char ch; int flag=1; cout二叉树endl; cout请建立二叉树。endl; CreateBiTree(T); /初始化队列 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); 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;elsecout 二叉树为空!;break; case5:if (T) int depth=0,NodeNum=0; depth=TreeDepth(T); NodeNum=TreeNodeNUM( T); /求树的深度及叶子数 cout树的深度depth 节点个数NodeNumendl; elsecout 二叉树为空!;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); elsecout 二叉树为空!;break; default: flag=0; cout程序运行结束，按任意键退出!; coutch; /读入一个字符 if(ch=#) T=NULL; else T=(BiTNode *)malloc(sizeof(BiTNode); /生成一个新结点 T-data=ch; CreateBiTree(T-lchild); /生成左子树 CreateBiTree(T-rch