数据结构实验6.doc

数据结构实验报告实验序号：6 实验项目名称：树和二叉树的操作学号姓名专业、班实验地点指导教师实验时间一、实验目的及要求1、进一步掌握指针变量、动态变量的含义。2、掌握二叉树的结构特征，以及各种存储结构的特点及适用范围。3、掌握用指针类型描述、访问和处理二叉树的运算。4、掌握用二叉树前序、中序、后序、层次遍历的方法。二、实验设备（环境）及要求微型计算机；windows 操作系统；Microsoft Visual Studio 6.0集成开发环境。三、实验内容与步骤1.根据下图中的树回答问题-。 列出所有的叶子结点； K,L,F,M,H,I,J 列出G结点的双亲； B 列出E结点的孩子； K.L 列出I结点所有的堂兄弟； E,F,G,H 列出B结点所有的子孙； E,F,G,K,L,M 结点E的度是多少； 2 树的度是多少； 3 结点E的层次是多少； 3 树的深度是多少； 42根据P129的方法，将a*b-(c+d*e/f)+g)转化为表达式二叉树（绘图），并写出表达式二叉树的前序、中序和后序遍历顺序。-*+ab+gc/f*de先序：-*ab+c/*defg中序：a*b-c+d*e/f+g后序：ab*cde*f/+g+-3. 画出和下列二叉树相应的森林：4. 链式表表示和实现二叉排序树如下：#include #include typedef int TElemType;typedef struct BiTNodeTElemType data;struct BiTNode *lchild,*rchild;BiNode, *Bitree;Bitree root;/定义根结点 void insert_data(int x) /*生成二叉排序树*/ Bitree p,q,s;s=(Bitree)malloc(sizeof(BiNode); /创建结点s-data=x; /结点赋值s-lchild=NULL;s-rchild=NULL;if(!root)root=s; elsep=root; while(p) /*如何接入二叉排序树的适当位置*/q=p;if(p-data=x) /相同结点不能重复插入printf(data already exist! n);return;else if(xdata)p=p-lchild; else p=p-rchild;if(xdata)q-lchild=s;else q-rchild=s;void main() /*先生成二叉排序树*/int i=1,x; /i记录结点个数，x存放结点值root=NULL; /*千万别忘了赋初值给root!*/printf(请输入数据,-9999表示输入结束n);doprintf(please input data %d:,i);i+;scanf(%d,&x); /*从键盘采集数据，以-9999表示输入结束*/if(x=-9999) printf(nNow output data value:n); else insert_data(x); /*调用插入数据元素的函数*/while(x!=-9999); 改写以上程序，实现功能如下(任选三题)：1). 编写函数实现前序、中序和后序遍历。2). 编写函数实现计算叶节点个数。3). 编写函数实现层序遍历。4). 编写函数实现查询二叉树中的某个结点(分查到和查不到两种情况)。5)编写函数实现求二叉树的深度6). 编写函数实现中序非递归遍历(利用栈)以下题目为选做题：5. 如果通讯字符a，b，c，d出现频度分别为7，5，2，4某同学设计了如下程序，请根据程序画出对应的二叉树，计算所画出的二叉树的带权路径长度；if(input=c) printf(%c,c); else if(input=d) printf(%c,d); else if(input=a) printf(%c,a); elseprintf(%c,b); WPL=7*3+5*3+4*2+2*1=46请画出对应的赫夫曼（哈弗曼）树；计算赫夫曼树的带权路径长度；WPL=2*3+4*3+5*2+7*1=35根据赫夫曼树，用if-else语句修改中的程序，写出最佳判定算法。if(input=a) printf(%c,a); else if(input=b) printf(%c,b); else if(input=c) printf(%c,c); elseprintf(%c,d);四、实验结果与数据处理详细记录程序在调试过程中出现的问题及解决方法。记录程序执行的结果（贴图）。五、分析与讨论对上机实践结果进行分析，上机的心得体会。六、教师评语签名：日期：成绩附源程序清单：1、#include #include typedef int TElemType;typedef struct BiTNodeTElemType data;struct BiTNode *lchild,*rchild;BiNode, *Bitree;DLR( Bitree root ) if (root !=NULL) /非空二叉树 printf(%d,root-data); /访问D DLR(root-lchild); /递归遍历左子树 DLR(root-rchild); /递归遍历右子树 return(0); LDR(Bitree root) if(root !=NULL) LDR(root-lchild); printf(%d,root-data); LDR(root-rchild); return(0);LRD (Bitree root) if(root !=NULL) LRD(root-lchild); LRD(root-rchild); printf(%d,root-data); return(0);Bitree root;/定义根结点 void insert_data(int x) /*生成/树*/ Bitree p,q,s;s=(Bitree)malloc(sizeof(BiNode); /创建结点s-data=x; /结点赋值s-lchild=NULL;s-rchild=NULL;if(!root)root=s; elsep=root; while(p) /*如何接入二叉排序树的适当位置*/q=p;if(p-data=x) /相同结点不能重复插入printf(data already exist! n);return;else if(xdata)p=p-lchild; else p=p-rchild;if(xdata)q-lchild=s;else q-rchild=s;void main() /*先生成二叉排序树*/int i=1,x; /i记录结点个数，x存放结点值root=NULL; /*千万别忘了赋初值给root!*/printf(请输入数据,-9999表示输入结束n);doprintf(please input data %d:,i);i+;scanf(%d,&x); /*从键盘采集数据，以-9999表示输入结束*/if(x=-9999) printf(nNow output data value:n); else insert_data(x); /*调用插入数据元素的函数*/while(x!=-9999); printf(nDLR:); DLR(root); printf(nLDR:); LDR(root); printf(nLRD:); LRD(root);printf(n);2、#include #include typedef int TElemType;typedef struct BiTNodeTElemType data;struct BiTNode *lchild,*rchild;BiNode, *Bitree;Bitree root;/定义根结点 int CountLeaf (Bitree root) /返回指针T所指二叉树中所有叶子结点个数int m,n; if (!root ) return 0; if (!root-lchild & !root-rchild) return 1; else m = CountLeaf( root-lchild); n = CountLeaf( root-rchild); return (m+n); /else / CountLeafvoid insert_data(int x) /*生成/树*/ Bitree p,q,s;s=(Bitree)malloc(sizeof(BiNode); /创建结点s-data=x; /结点赋值s-lchild=NULL;s-rchild=NULL;if(!root)root=s; elsep=root; while(p) /*如何接入二叉排序树的适当位置*/q=p;if(p-data=x) /相同结点不能重复插入printf(data already exist! n);return;else if(xdata)p=p-lchild; else p=p-rchild;if(xdata)q-lchild=s;else q-rchild=s;void main() /*先生成二叉排序树*/int i=1,x; /i记录结点个数，x存放结点值int sum;root=NULL; /*千万别忘了赋初值给root!*/printf(请输入数据,-9999表示输入结束n);doprintf(please input data %d:,i);i+;scanf(%d,&x); /*从键盘采集数据，以-9999表示输入结束*/if(x=-9999) printf(nNow output data value:n); else insert_data(x); /*调用插入数据元素的函数*/while(x!=-9999);printf( n叶节点个数=);sum=CountLeaf (root);printf(%dn,sum);3、#include #include typedef int TElemType;typedef struct BiTNodeTElemType data;struct BiTNode *lchild,*rchild;BiNode, *Bitree;Bitree root;/定义根结点 int Depth (Bitree root ) / 返回二叉树的深度 int depthval,depthLeft,depthRight;if (root=NULL) depthval = 0; else depthLeft = Depth( root-lchild ); depthRight= Depth( root-rchild ); depthval = 1+(depthLeftdepthRight?depthLeft:depthRight); return depthval;void insert_data(int x) /*生成/树*/ Bitree p,q,s;s=(Bitree)malloc(sizeof(BiNode); /创建结点s-data=x; /结点赋值s-lchild=NULL;s-rchild=NULL;if(!root)root=s; elsep=root; while(p) /*如何接入二叉排序树的适当位置*/q=p;if(p-data=x) /相同结点不能重复插入printf(data already exist! n);return;else if(xdata)p=p-lchild; else p=p-rchild;if(xdata)q-lchild=s;else q-rchild=s;void main() /*先生成二叉排序树*/int i=1,x; /i记录结点个数，x存放结点值int d;root=NULL; /*千万别忘了赋初值给root!*/printf(请输入数据,-9999表示输入结束n);doprintf(please input data %d:,i);i+;scanf(%d,&x); /*从键盘采集数据，以-9999表示输入结束*/if(x=-9999) printf(nNow output data value:n); else insert_data(x); /*调用插入数据元素的函数*/while(x!=-9999);printf( n树的深度为=);d=Depth (root);printf(%dn,d);