数据结构 二叉树.doc_第1页
数据结构 二叉树.doc_第2页
数据结构 二叉树.doc_第3页
数据结构 二叉树.doc_第4页
数据结构 二叉树.doc_第5页
已阅读5页,还剩15页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

数据结构与算法实验指导V2017常熟理工学院数据结构与算法实验指导与报告书_2017-2018_学年 第_1_ 学期专 业: 物联网工程 实验名称: 二叉树 实验地点: N6-210 指导教师: 聂盼红 计算机科学与工程学院2017实验六 二叉树【实验目的】1、掌握二叉树的基本存储表示。2、掌握二叉树的遍历操作实现方法(递归和非递归方法)。3、理解并实现二叉树的其他基本操作。4、掌握二叉树的重要应用-哈夫曼编码的实现。【实验学时】4-6学时【实验预习】回答以下问题:1、二叉树的二叉链表存储表示。/*-二叉树的二叉链表存储表示-*/typedef struct BTNode char data ; /*结点数据*/ struct BTNode *lchild; /*左孩子指针*/ struct BTNode *rchild ; /*右孩子指针*/*BiTree;2、二叉树的三种基本遍历方式。/*先序遍历二叉树,补充递归算法*/void PreOrder(BiTree p) if(p!=NULL); printf(%c,p-data); /访问根节点 PreOrder(p-lchild); /先序遍历左子数 PreOrder(p-rchild); /先序遍历右子数 /*PreOrder*/*中序遍历二叉树,补充递归算法*/void InOrder(BiTree p) if(p!=NULL); InOrder(p-lchild); /中序遍历左子数 printf(%c,p-data); /访问根节点 InOrder(p-rchild); /中序遍历右子数 /*InOrder*/*后序遍历二叉树,补充递归算法*/void PostOrder(BiTree p) if(p!=NULL); PostOrder(p-lchild); /后序遍历左子数 PostOrder(p-rchild); /后序遍历右子数 printf(%c,p-data); /访问根节点 /*PostOrder*/3、解释哈夫曼树和带权路径长度WPL。哈夫曼树,是指权值为W1、W2、.Wn的n个叶节点所构成的二叉树中带权路径长度最小的二叉树。从树根结点到到该结点之间的路径长度与该结点上权的乘积称为结点的带权路径长度,通常记作:WPL=(n,i=1)WiLi【实验内容和要求】1、 编写程序exp6_1.c,实现二叉树的链式存储及基本操作。以下图所示的二叉树实现二叉树的二叉链表存储及基本操作,回答下列问题,补充完整程序,并调试运行验证结果。(1)按照先序序列建立该二叉树。读入的字符序列应为:A,B,C,*,*,D,E,*,G,*,*,F,*,*,* (*表示空指针)。(2)该二叉树的三种遍历序列:先序序列:A,B,C,D,E,G,F;中序序列:C,B,E,G,D,F,A;后序序列:C,G,E,F,D,B,A;(3)按层次遍历该二叉树,得到的序列为:A,B,C,D,E,F,G(4)该二叉树的深度为 5 。(5)该二叉树的叶子结点数为:_3_。A(6)交换该二叉树所有结点的左右次序得到的新二叉树为:(画出新二叉树的图)BCDEFG(7)新二叉树的三种遍历序列分别为:先序序列:A,B,D,C,F,G,E;中序序列:D,B,F,G,C,E,A;后序序列:D,G,F,E,C,B,A;exp6_1.c参考程序如下:#include#include#define MAX 20/*-二叉树的二叉链表存储表示-*/typedef struct BTNode char data; /*结点数据*/ struct BTNode *lchild; /*左孩子指针*/ struct BTNode *rchild ; /*右孩子指针*/ * BiTree;/*-非递归遍历辅助队列-*/typedef struct SqQueue BiTree dataMAX; int front,rear; SqQueue;void createBiTree(BiTree *t); /*先序遍历创建二叉树*/void PreOrder(BiTree p); /*先序遍历二叉树*/void InOrder(BiTree p); /*中序遍历二叉树*/void PostOrder(BiTree p);/*后序遍历二叉树*/void RPreorder(BiTree p); /*先序遍历的非递归算法*/void RInorder(BiTree p); /*中序遍历的非递归算法*/void RPostorder(BiTree p); /*后序遍历的非递归算法*/int depth(BiTree t); /*求二叉树的深度算法*/BiTree gettreenode(char x,BiTree lptr,BiTree rptr);/*后序复制二叉树-建立结点*/BiTree copytree(BiTree t);/*以后序遍历的方式复制二叉树*/BiTree swap(BiTree b); /*交换二叉树的结点的左右孩子*/void ccOrder(BiTree t); /*利用循环队列实现层次遍历*/int Leaves(BiTree t); /*统计二叉树叶子结点(递归)*/void release(BiTree t); /*释放二叉树*/*先序遍历创建二叉树*/void createBiTree(BiTree * t) char s; BiTree q; printf(nplease input data:); s=getchar(); getchar(); /*扔掉存在键盘缓冲区的输入结束回车符*/ if(s=#) /*子树为空则返回*/ * t =NULL; return; else q=(BiTree)malloc(sizeof(struct BTNode); if(q=NULL) printf(Memory alloc failure!); exit(0); q-data=s; *t=q; createBiTree(&q-lchild);/*递归建立左子树*/ createBiTree(&q-rchild);/*递归建立右子树*/ /*createBiTree*/*先序遍历二叉树,补充递归算法*/void PreOrder(BiTree p) if(p!=NULL) printf(%c,p-data); /访问根节点 PreOrder(p-lchild); /先序遍历左子数 PreOrder(p-rchild); /先序遍历右子数 /*PreOrder*/*中序遍历二叉树,补充递归算法*/void InOrder(BiTree p) if(p!=NULL) InOrder(p-lchild); /中序遍历左子数 printf(%c,p-data); /访问根节点 InOrder(p-rchild); /中序遍历右子数 /*InOrder*/*后序遍历二叉树,补充递归算法*/void PostOrder(BiTree p) if(p!=NULL) PostOrder(p-lchild); /后序遍历左子数 PostOrder(p-rchild); /后序遍历右子数 printf(%c,p-data); /访问根节点 /*PostOrder*/*先序遍历的非递归算法*/void RPreorder(BiTree p) BiTree stackMAX,q; int top=0,i; for(i=0; idata); if(q-rchild!=NULL) stacktop+=q-rchild; /*右指针进栈*/ if(q-lchild!=NULL) q=q-lchild;/*顺着左指针继续向下*/ else if(top0) q=stack-top; /*左子树访问完,出栈继续访问右子树结点*/ else q=NULL; /*RPreorder*/*中序遍历的非递归算法*/void RInorder(BiTree p) BiTree stackMAX,q; /定义节点栈和搜索指针 int top=0; q=p; do while(q)/左链所有节点入栈 stacktop+=q; q=q-lchild; if(top0) q=stack-top; printf(%c,q-data); /访问根 q=q-rchild; while(q|top!=0);/*RInorder*/*后序遍历的非递归算法*/void RPostorder(BiTree p) BiTree stackMAX,q; int i,top=0,flagMAX; for(i=0; ilchild; else while(top) if(flagtop-1=0) /*遍历结点的右子树*/ q=stacktop-1; q=q-rchild; flagtop-1=1; break; else q=stack-top; printf(%c,q-data); /*遍历结点*/ if(top=0) break; /*RPostorder*/*求二叉树的深度算法,补充递归算法*/int depth(BiTree t) int lc,rc; if(t=NULL) return 0; /若为空树,则返回零 else lc=depth(t-lchild); /递归求t的左子树深度 rc=depth(t-rchild);/递归求t的右子树深度 if(lcrc) return(lc+1); else return(rc+1); /*depth*/*建立结点*/BiTree gettreenode(char x,BiTree lptr,BiTree rptr) BiTree t; t=(BiTree)malloc(sizeof(struct BTNode); t- data = x; t-lchild = lptr; t-rchild = rptr; return(t);/*gettreenode*/*以后序遍历的方式递归复制二叉树*/BiTree copytree(BiTree t) BiTree newlptr,newrptr,newnode; if(t=NULL) return NULL; if(t-lchild!=NULL) newlptr = copytree(t-lchild); else newlptr = NULL; if(t-rchild!=NULL) newrptr = copytree(t-rchild); else newrptr = NULL; newnode = gettreenode(t-data, newlptr, newrptr); return(newnode);/*copytree*/*交换二叉树的结点的左右孩子*/BiTree swap(BiTree b) BiTree t,t1,t2; if(b=NULL) t=NULL; else t=(BiTree)malloc(sizeof(struct BTNode); t-data=b-data; t1=swap(b-lchild);/*递归交换左子树上的结点*/ t2=swap(b-rchild);/*递归交换右子树上的结点*/ t-lchild=t2;/*交换根t的左右子树*/ t-rchild=t1; return(t);/*swap*/*利用循环队列实现层次遍历*/void ccOrder(BiTree t) BiTree p; SqQueue qlist,*q; /利用循环队列,实现层次遍历 q=&qlist; q-rear=0; q-front=0; /初始化队列 p=t; if(p!=NULL) printf(%c,p-data); /访问根节点 q-dataq-rear=p; /根节点入队 q-rear=(q-rear+1)%MAX; /修改队尾指针 while(q-front!=q-rear) p=q-dataq-front; /出队操作 q-front=(q-front+1)%MAX; if(p-lchild!=NULL) /访问出队节点的左孩子,并且入队 printf(%c,p-lchild-data); q-dataq-rear=p-lchild; q-rear=(q-rear+1)%MAX; if(p-rchild!=NULL) /访问出队节点的右孩子,并且入队 printf(%c,p-rchild-data); q-dataq-rear=p-rchild; q-rear=(q-rear+1)%MAX; /*ccOrder*/*统计二叉树叶子结点,补充递归算法*/int Leaves(BiTree t) if(t=NULL) return 0; if(t-lchild=NULL&t-rchild=NULL) return 1; return (Leaves(t-lchild)+Leaves(t-rchild); /左子数叶子节点加上右子数叶子结点数/*Leaves*/*释放二叉树*/void release(BiTree t) if(t!=NULL) release(t-lchild); release(t-rchild); free(t); /*release*/int main() BiTree t=NULL,copyt=NULL; int select; do printf(n*MENU*n); printf( 1. 按先序序列建立二叉树n); printf( 2. 遍历二叉树(三种递归方法)n); printf( 3. 遍历二叉树(三种非递归方法)n); printf( 4. 层次遍历二叉树n); printf( 5. 输出二叉树的深度n); printf( 6. 统计二叉树的叶子结点数(递归)n); printf( 7. 后序遍历方式复制一棵二叉树n); printf( 8. 交换二叉树所有结点的左右孩子n); printf( 0. EXIT); printf(n*MENU*n); printf(ninput choice:); scanf(%d,&select); getchar(); switch(select) case 1: printf(n1-按先序序列建立二叉树:n); printf(请依次输入结点序列:n); / BiTree gettreenode(x,&lptr,&rptr); createBiTree(&t); if(t!=NULL) printf(二叉树创建成功!n); else printf(二叉树未创建成功!n); break; case 2: printf(n2-遍历二叉树(三种递归方法):n); printf(n先序遍历序列:); PreOrder(t); printf(n中序遍历序列:); InOrder(t); printf(n后序遍历序列:); PostOrder(t); printf(n); break; case 3: printf(n3-遍历二叉树(三种非递归方法):n); printf(n先序遍历的非递归:); RPreorder(t); printf(n中序遍历的非递归:); RInorder(t); printf(n后序遍历的非递归:); RPostorder(t); printf(n); break; case 4: printf(n4-层次遍历二叉树:n); printf(n按层次遍历:); ccOrder(t); printf(n); break; case 5: printf(n5-输出二叉树的深度:n); printf(n二叉树的深度:%d,depth(t); printf(n); break; case 6: printf(n6-统计二叉树的叶子结点数(递归):n); printf(n叶子结点数为:%d,Leaves(t); printf(n); break; case 7: printf(n7-后序遍历方式复制一棵二叉树:n); copyt=copytree(t); if(copyt!=NULL) printf(n先序递归遍历复制的二叉树:); PreOrder(copyt); else printf(n复制失败!); printf(n); break; case 8: printf(n8-交换二叉树所有结点的左右孩子:n); printf(n先序递归遍历交换后的二叉树:); PreOrder(swap(t); /*如需输出中序和后序遍历的结果,增加调用*/ printf(n); break; case 0: release(t); /*释放二叉树*/ break; default: break; while(select); return 0;exp6_1.c实验结果:(1) 按照先序序列建立二叉树:(2)该二叉树的三种递归遍历序列为:(3)遍历二叉树(三种非递归方法):(4)层次遍历二叉树:(5)输出二叉树的深度(6)统计二叉树的叶子结点数(递归)(7)后序遍历方式复制一棵二叉树(8)交换二叉树所有结点的左右孩子2、 编写程序exp6_2.c,实现哈夫曼树的建立和哈夫曼编码。若有一组字符序列a,c,e,i,s,t,w,对应的出现频率为10,1,15,12,3,4,13。以此序列创建哈夫曼树和哈夫曼编码。回答下列问题,补充完整程序,并调试运行验证结果。(1) 构造该序列的哈夫曼树,画出哈夫曼树的形态。(以结点值左小右大的原则)eT658t28T425i12T533e15T318w13s 3c1 t4T14a 10(2) 写出对应的哈夫曼编码。a的编码为111, c的编码为11000,e的编码为10,i的编码为00,s的编码为11001,t的编码为1101,w的编码为01(3) 计算编码的WPL。WPL=3*10+5*1+2*15+2*12+5*3+4*4+2*13=146exp6_2.c程序代码参考如下:#include#define MAXVALUE 10000 /*定义最大权值*/#define MAXLEAF 30 /*定义哈夫曼树中叶子结点个数*/#define MAXNODE MAXLEAF*2-1#define MAXBIT 10 /*定义哈夫曼编码的最大长度*/typedef struct /*哈夫曼编码结构*/ int bitMAXBIT; int start;HCodeType;typedef struct /*哈夫曼树结点结构*/ char data; int weight; int parent; int lchild; int rchild;HNodeType;void HuffmanTree(HNodeType HuffNode,int *hn);void HuffmanCode(HNodeType HuffNode,HCodeType HuffCode,int n);void HuffmanTree(HNodeType HuffNode,int *hn)/*哈夫曼树的构造算法*/ int i,j,m1,m2,x1,x2,n; printf(n:); scanf(%d,&n); getchar(); /*输入叶子结点个数*/ for (i=0; i2*n-1; i+) /*数组HuffNode 初始化*/ HuffNodei.parent=-1; HuffNodei.lchild=-1; HuffNodei.rchild=-1; printf(HuffNode:n); for (i=0; in; i+) scanf(%c,%d,&HuffNodei.data,&HuffNodei.weight); /*输入n个叶子结点的权值*/ getchar(); for (i=0; in-1; i+) /*构造哈夫曼树*/ m1=m2=MAXVALUE; x1=x2=0; for (j=0; jn+i; j+) if (HuffNodej.weightm1 & HuffNodej.parent=-1) m2=m1; x2=x1; m1=HuffNodej.weight; x1=j; else if (HuffNodej.weightm2 & HuffNodej.parent=-1) m2=HuffNodej.weight; x2=j; /*将找出的两棵子树合并为一棵子树*/ HuffNodex1.parent=n+i; HuffNodex2.parent=n+i; HuffNoden+i.weight=HuffNodex1.weight+HuffNodex2.

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论