数据结构试验6

1、数据结构实验报告实验序号：6实验项目名称：树和二叉树的操作学号姓名专业、班实验地点指导教师实验时间一、实验目的及要求1进一步掌握指针变量、动态变量的含义。2、掌握二叉树的结构特征，以及各种存储结构的特点及适用范围3、掌握用指针类型描述、访问和处理二叉树的运算。4、掌握用二叉树前序、中序、后序、层次遍历的方法。二、实验设备(环境)及要求微型计算机；wi ndows操作系统；Microsoft Visual Studio 6.0 集成开发环境。三、实验内容与步骤1.根据下图中的树回答问题 -。 列出所有的叶子结点； K,L,F,M,H,I,J 列出G结点的双亲；B 列出E结点的孩子；K丄 列出I结

2、点所有的堂兄弟；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+c/*defg中序：a*b-c+d*e/f+g后序：ab*cde*f/+g+-生成二叉排序树*/创建结点如何接入二叉排序树的适当位置*/4.链式表表示和实现二叉排序树如下:#i nclude <stdlib.h>#in elude <stdio.h> typedef

3、int TEIemType;typedef struct BiTNodeTElemType data; struct BiTNode *lchild,*rchild;BiNode, *Bitree;Bitree root;/定义根结点void in sert_data(i nt 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->da

4、ta=x) II相同结点不能重复插入prin tf("data already exist! n");return;else if(x<p->data)p=p->lchild;elsep=p->rchild;if(x<q->data)q->lchild=s;elseq->rchild=s;void main ()/*int i=1, x; /i root=NULL;先生成二叉排序树*/root!*/记录结点个数，x存放结点值/*千万别忘了赋初值给printf(”请输入数据，-9999表示输入结束n");doprin

5、tf("please in put data %d:",i);i+;scanf("%d",&x);/*从键盘采集数据，以-9999表示输入结束*/if(x=-9999)prin tf("nNow output data value:n");elsein sert_data(x);/*调用插入数据元素的函数*/while(x!=-9999);改写以上程序，实现功能如下(任选三题)：1) .编写函数实现前序、中序和后序遍历。'C:Use rssu 20Deskto总聊建立彳牛夹【H青输A数据叨丹杏三输人结童l)lease

6、input please input piease input please input please inut please input pieace Inputj)lease please ZLn.iitplease injiutdata 1 ：5 dta 2 ：1data 3：3 data 4：4data 5:? (>: Sdata exist!data 8 :&9data lC：-9999INoip output data Value *l)LR；5137t8L»R：134Sfc?8L«D：431fce*?GPress any key 七u cant;

7、inuc2) .编写函数实现计算叶节点个数'C:Use rssu 20D eskto pl 制雀刘牛夹'晴输入数据表示输入结束plfiftSRinputdata.1；5pleaseinjiutdataZ；6pie astiniiutdata3:2p le as ein putdata4：8pleaseinuutdata.gpleaseinputdata.&：7p 1h dl£ bini)utd.At a7：?in putdata8：1pleaseinputda.ta?：5Idata alvedyexist!Ele acir)i)utdAt a10:4p丄 ea

8、seinputdAtan：-?y9Naw output data, value：叶节点个数詁Press anj/ kmy to continue3) .编写函数实现层序遍历4) .编写函数实现查询二叉树中的某个结点(分查到和查不到两种情况)5) 编写函数实现求二叉树的深度J 'C：U&ers5*j20Deskto”冃ple-aseplease pleaseple*5e please p le-Eise please p& dot戏 alrcaiy ple-ae inputinput input input in put input input input npiut l

9、n|)u.t inputdfit 锐 data data data data datadec七熬 dLat stZ 鼻 11 = 99?79：110：5lou output datfi value:耐的探度为吨Pjess anv kesF to cantlnue.6).编写函数实现中序非递归遍历(利用栈)以下题目为选做题：5. 如果通讯字符a, b, c, d出现频度分别为7, 5, 2, 4某同学设计了如下程序，请根据程序画出对应的二叉树，计算所画出的二叉树 的带权路径长度；if(input=' c')printf("%c",' c');e

10、lse if(input=' d')printf("%c",' d');else if(input=' a')printf("%c",' a');elseWPL=7*3+5*3+4*2+2* 仁46WPL=2*3+4*3+5*2+7*1=35根据赫夫曼树，用if-else语句修改中的程序，写出最佳判定算法if(in put=' a')printf("%c "， a');else if(input=' b')printf("

11、%c"， b');else if(input=' c')printf("%c"， c');elseprintf("%c "， d');四、实验结果与数据处理详细记录程序在调试过程中出现的问题及解决方法。记录程序执行的结果(贴图)。五、分析与讨论对上机实践结果进行分析，上机的心得体会。六、教师评语签名：日期：成绩附源程序清单：1、#inelude <stdlib.h>#in elude <stdio.h> typedef int TEIemType;typedef struct Bi

12、TNodeTElemType 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(O);LDR(Bitree root) if(root !=NULL)LDR(root->lchild); printf("%d&quo

13、t;,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-

14、>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(x<p->data) p=p->lchild;elsep=p->rchild; if(x<q->data) q->lchild=s;else q->rchild=s;void main() /*

15、先生成二叉排序树 */int i=1,x; /i 记录结点个数， x 存放结点值 root=NULL;/* 千万别忘了赋初值给 root!*/printf(" 请输入数据 ,-9999 表示输入结束 n");doprintf("please input data %d:",i);i+;-9999 表示输入结束 */*/scanf("%d",&x); /* 从键盘采集数据，以 if(x=-9999)printf("nNow output data value:n");else insert_data(x);

16、/* 调用插入数据元素的函数 while(x!=-9999); printf("nDLR:");DLR(root); printf("nLDR:");LDR(root); printf("nLRD:");LRD(root); printf("n");2、#include <stdlib.h>#include <stdio.h>typedef int TElemType;typedef struct BiTNodeTElemType data; struct BiTNode *lchild,*

17、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(

18、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(x<p->data) p=p->lchild;

19、elsep=p->rchild; if(x<q->data) q->lchild=s;elseq->rchild=s;void main() /* 先生成二叉排序树 */int i=1,x; /i 记录结点个数， x 存放结点值 int sum;root=NULL;/* 千万别忘了赋初值给 root!*/printf(" 请输入数据 ,-9999 表示输入结束 n");do printf("please input data %d:",i); i+;-9999 表示输入结束 */*/scanf("%d",

20、&x); /* 从键盘采集数据，以 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 <stdlib.h>#include <stdio.h>typedef int TElemType;typedef struc

21、t 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+(depthLeft>depthRight?depthLeft:depthRight); return depthval;void insert_data(int x)/*生成 /树 */Bitree p,q,s; s=(Bitree)malloc(sizeof(BiNode); / 创建结点 s->data=x;/