2022年数据结构实验三归纳 .pdf

《2022年数据结构实验三归纳 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构实验三归纳 .pdf（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、实验三实验课程名：二叉树的操作及应用专业班级：11计科（ 3）班学号：39 姓名：廖万君实验时间：11.26 12.7 实验地点K4-206 指导教师：冯珊一、实验目的1、进一步掌握指针变量、动态变量的含义。2、掌握二叉树的结构特性，以及各种存储结构的特点和适用范围。3、掌握用指针类型描述、访问和处理二叉树的运算。二、实验内容1、以二叉链表作存储结构，试编写计算二叉树深度、所有结点总数、叶子结点数、双孩子结点个数、单孩子结点个数的算法(1)代码如下 : 1.Tree.h 头文件定义如下：#ifndef _Tree #define _Tree #include using namespace s

2、td; typedef char ElemType; typedef struct TreeNode ElemType data; struct TreeNode *lchild,*rchild; TreeNode,*Tree; void CreateTree(Tree &t,char *str,int len) static int i=0; if(i=len) return; if(stri=32) t=NULL; i+; return; t=(Tree)malloc(sizeof(TreeNode); t-lchild=NULL; t-rchild=NULL; memcpy(&t-dat

3、a,&stri+,sizeof(ElemType); CreateTree(t-lchild,str,len); CreateTree(t-rchild,str,len); void Deepth(Tree t,int deep,int &max) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 8 页 - - - - - - - - - deep+; int flag=1; if(t-lchild) Deepth(t-lchild,deep,max); flag=0;

4、if(t-rchild) Deepth(t-rchild,deep,max); flag=0; if(flag) if(deepmax) max=deep; return; int NodeCount(Tree t) if(t=NULL) return 0; return NodeCount(t-lchild)+NodeCount(t-rchild)+1; int DoubleChildNodeCount(Tree t) if(t-rchild&t-lchild) return DoubleChildNodeCount(t-lchild)+DoubleChildNodeCount(t-rchi

5、ld)+1; else return 0; int SingleChildNodeCount(Tree t) if(!(t-rchild|t-lchild) return 0; else if(t-lchild&!t-rchild) return 1+SingleChildNodeCount(t-lchild); else if(t-rchild&!t-lchild) return 1+SingleChildNodeCount(t-rchild); else return SingleChildNodeCount(t-lchild)+SingleChildNodeCount(t-rchild)

6、; #endif 2.main 函数名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 8 页 - - - - - - - - - #include “ Tree.h ”int main() Tree t; cout ” 请输入一颗树的构造，空间点用空格表示，例如：abdf e c “ endl; char str56; gets(str); CreateTree(t,str,strlen(str); int max=0; Deepth(t,0,max); cout ” 树的

7、深度为： ” ; coutmaxendl; cout ” 树的所有结点数为： ” ; coutNodeCount(t)endl; cout ” 双孩子的结点个数为 : ” ; coutDoubleChildNodeCount(t)endl; cout ” 单孩子的结点数位 : ” ; coutSingleChildNodeCount(t)endl; return 0; (2)运行结果 : 2、 赫夫曼树与赫夫曼编码：已知某系统在通信联络中只可能出现8 种字符 a,b,c,d,e,f,g,h，其概率分别为 0.05 ，0.29 ，0.07 ，0.08 ，0.14 ，0.23 ，0.03 ，0.1

8、1 ，试设计 Huffman 编码，并计算其平均长度代码如下：#include “ Tree.h ”#include #include void GetCode(Tree t,int I,string str) static int flag=0; if(flag+) str+=i+48; if(t-lchild=NULL) coutdata.v” : ” strlchild,0,str); GetCode(t-rchild,1,str); bool HaveLeft(Tree t,int n,int flag,int &fmin) int I; int count=0; for(i=0;in

9、;i+) if(flagi!=1&count+) return true; return false; void select(Tree t,int n,int flag,int &fmin,int &smin) int I; int isFirst=0; for(i=0;idata.wdata.w) fmin=I; isFirst=0; for(i=0;idata.wdata.w) smin=I; int main() char v9=” abcdefgh ” ; double w8=0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11; 名师资料总结 - - -精

10、品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 8 页 - - - - - - - - - int flag8=0; Tree t8; for(int i=0;idata.v=vi; ti-data.w=wi; ti-lchild=NULL; ti-rchild=NULL; int fmin ,smin; while(HaveLeft(t, 8,flag,fmin) select(t,8,flag,fmin,smin); Tree tmp=new TreeNode; tmp-lchild=tfmi

11、n; tmp-rchild=tsmin; tmp-data.w=tfmin-data.w+tsmin-data.w; tmp-data.v=0; tfmin=tmp; flagfmin=2; flagsmin=1; string str; GetCode(tfmin,0,str); 运行结果 : 3、分别以顺序存储结构和二叉链表作存储结构，试编程实现前序、中序、后序及层次顺序遍历二叉树的算法。（1）Tree.h 头文件定义如下#ifndef _Tree #define _Tree #include using namespace std; 名师资料总结 - - -精品资料欢迎下载 - - -

12、- - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 8 页 - - - - - - - - - typedef char ElemType; typedef struct TreeNode ElemType data; struct TreeNode *lchild,*rchild; TreeNode,*Tree; void CreateTree(Tree &t,char *str,int len) static int i=0; if(i=len) return; if(stri=32) t=NULL; i+; return;

13、 t=(Tree)malloc(sizeof(TreeNode); t-lchild=NULL; t-rchild=NULL; memcpy(&t-data,&stri+,sizeof(ElemType); CreateTree(t-lchild,str,len); CreateTree(t-rchild,str,len); void PreOrderTree(Tree t) if(t=NULL) return ; coutdatalchild); PreOrderTree(t-rchild); void InOrderTree(Tree t) if(t=NULL) return ; InOr

14、derTree(t-lchild); coutdatarchild); void LastOrderTree(Tree t) if(t=NULL) return ; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 8 页 - - - - - - - - - LastOrderTree(t-lchild); LastOrderTree(t-rchild); coutdata ” “ ; void LevelOrderTree(Tree t) if(t=NULL) retur

15、n; int front=0,rear=0; ElemType e; Tree array52; coutdatalchild) coutlchild-datalchild; if(p-rchild) coutrchild-datarchild; #endif (2)实现代码如下：#include “ Tree.h”int main() char str52; Tree t; cout” 请输入你要构建的树，空节点用空格表示，例如abd e c” endl; gets(str); int len=strlen(str); CreateTree(t,str,len); cout” 先序遍历 :”

16、 ; PreOrderTree(t); coutendl; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 8 页 - - - - - - - - - cout” 中序遍历 :” ; InOrderTree(t); coutendl; cout” 后序遍历 :” ; LastOrderTree(t); coutendl; cout” 层次遍历 :” ; LevelOrderTree(t); coutendl; return 0; 运行结果如下：三、实验总结此次实验，进一步掌握了指针变量，动态变量的含义，二叉树的结构特性，以及各种存储结构的特点和适用范围，掌握用指针类型描述、访问和处理二叉树的运算。四、教师批阅及成绩日期：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 8 页 - - - - - - - - -