二叉树及其应用(实验五)

1、实验 五 二叉树及其应用 1.目的要求：（1） 通过实验掌握二叉树的两种基本的存储结构，及二叉树的建立、遍历，并加以应用。（2） Huffman 树建立、编码。2.实验内容：（1） 按先序次序输入二叉树中结点的值，建立一棵以二叉链表作存储结构的二叉树，然后按先序、中序、后序顺序分别遍历这棵二叉树，并完成二叉树的相应信息的统计（如各种结点数目、二叉树的高度等） ；（2） 建立一棵二叉排序树，并对其进行先序、中序、后序遍历。（3） 应用队列结构实现二叉树的层次遍历。（4） 设计一个完整的编码系统：针对一篇文档，统计各个字符的出现次数，并为其设计 Huffman 编码。注：（1）（2）必做， （3）（4）选做。三.实验主要流程、基本操作或核心代码、算法片段（该部分如不够填写，请另加附页）（1） 按先序次序输入二叉树中结点的值，建立一棵以二叉链表作存储结构的二叉树，然后按先序、中序、后序顺序分别遍历这棵二叉树，并完成二叉树的相应信息的统计（如各种结点数目、二叉树的高度等） ； 程序代码：头文件：#ifndef _H_#define _H_#define OK 1#define ERROR 0#

2、define OVERFLOW -2typedef int Status;typedef char TElemType;typedef struct BiTNodeTElemType e;struct BiTNode *LChild,*RChild;BiTNode,*BiTree;Status Create(BiTree Status PreOrderTraver(BiTree T,Status (* visit)(TElemType e);Status InOrderTraver(BiTree T,Status (* visit)(TElemType e);Status PostOrderTraver(BiTree T,Status (* visit)(TElemType e);Status Count(BiTree T);Status Countleaf(BiTree T);Status Counttwo(int n);Status Countone(int n,int n0,int n2);Status Depth(BiTree T);#endif主函数：#include#inc

3、lude#include1.hint main()BiTree T;printf(请按照先序输入树值:n);if(!Create(T) printf(存储空间分配失败n);printf(先序遍历该树为：n);if(!PreOrderTraver(T,PrintElemType) printf(打印函数出错n);printf(n);printf(中序遍历该树为：n);if(!InOrderTraver(T,PrintElemType) printf(打印函数出错n);printf(n);printf(后序遍历该树为：n);if(!PostOrderTraver(T,PrintElemType) printf(打印函数出错n);printf(n);printf(总结点数有：%dn,Count(T);printf(其中叶子结点数有：%dn,Countleaf(T);printf(其中一度结点数有：%dn,Countone(Count(T),Countleaf(T),Counttwo(Countleaf(T);printf(其中二度结点数有：%dn,Counttwo(Countleaf(T);

4、printf(该二叉树的深度为：%dn,Depth(T);return 0;功能函数：#include#include#include1.h/先序建立二叉Status Create(BiTree &T)char ch;scanf(%c,if(ch= ) T=NULL;elseif(!(T=(BiTree)malloc(sizeof(BiTNode) exit(OVERFLOW);T-e=ch;Create(T-LChild);Create(T-RChild);return OK;/输出结点中的数值Status PrintElemType(TElemType e)printf(%c ,e);return OK;/先序遍历Status PreOrderTraver(BiTree T,Status (* visit)(TElemType e)if(T)if(visit(T-e)if(PreOrderTraver(T-LChild,visit)if(PreOrderTraver(T-RChild,visit) return OK;return ERROR;else return OK;/中序遍

5、历Status InOrderTraver(BiTree T,Status (* visit)(TElemType e)if(T) if(InOrderTraver(T-LChild,visit)if(visit(T-e)if(InOrderTraver(T-RChild,visit) return OK;return ERROR;else return OK;/后序遍历Status PostOrderTraver(BiTree T,Status (* visit)(TElemType e)if(T)if(PostOrderTraver(T-LChild,visit)if(PostOrderTraver(T-RChild,visit)if(visit(T-e) return OK;return ERROR;else return OK;/总结点数Status Count(BiTree T)int num1,num2,num;if(T=NULL) num=0;elsenum1=Count(T-LChild);num2=Count(T-RChild);num=num1+num2+1;ret

6、urn num;/叶子结点数Status Countleaf(BiTree T) int num1,num2,num;if(T=NULL) num=0;elseif(T-LChild=NULLelsenum1=Countleaf(T-LChild);num2=Countleaf(T-RChild);num=num1+num2; return num;/二度结点数Status Counttwo(int n)/n 为终端结点数 终端结点数=二度结点数+1int num;num=n-1;return num;/一度结点数Status Countone(int n,int n0,int n2)/一度结点数=总数-0 度结点数-2 度结点数int num;num=n-n0-n2;return num;/二叉树深度Status Depth(BiTree T)int dep,depl,depr;if(T=NULL) dep=0;elsedepl=Depth(T-LChild);depr=Depth(T-RChild);dep=1+(depldepr?depl:depr);return dep; 运行

7、结果：（2） 建立一棵二叉排序树，并对其进行先序、中序、后序遍历。程序代码部分：头文件：#ifndef _H_#define _H_#define OK 1#define ERROR 0#define OVERFLOW -2typedef int Status;typedef int TElemType;typedef struct BiTNodeTElemType e;struct BiTNode *LChild,*RChild;BiTNode,*BiTree;Status Insert(BiTree void Create(BiTree Status PrintElemType(TElemType e);Status PreOrderTraver(BiTree T,Status (* visit)(TElemType e);Status InOrderTraver(BiTree T,Status (* visit)(TElemType e);Status PostOrderTraver(BiTree T,Status (* visit)(TElemType e);#endif主函数

8、：#include#include#include1.hint main()BiTree T=NULL;printf(请输入树值建立二叉排序数（输-1 表示输入结束）:n);Create(T);printf(先序遍历该树为： n);if(!PreOrderTraver(T,PrintElemType) printf(打印函数出错n);printf(n);printf(中序遍历该树为： n);if(!InOrderTraver(T,PrintElemType) printf(打印函数出错n);printf(n);printf(后序遍历该树为： n);if(!PostOrderTraver(T,PrintElemType) printf(打印函数出错n);printf(n);return 0;功能函数：#include#include#include1.h/插入结点Status Insert(BiTree &T,TElemType e)if(T=NULL) if(!(T=(BiTree )malloc(sizeof(BiTNode) exit(OVERFLOW);T-e=e;T-LChil

9、d=T-RChild=NULL;elseif(ee) Insert(T-LChild,e);if(eT-e) Insert(T-RChild,e);return OK;/建立二叉排序void Create(BiTree &T)TElemType e;for(scanf(%d,scanf(%d,&e)Insert(T,e);/输出结点中的数值Status PrintElemType(TElemType e)printf(%d ,e);return OK;/先序遍历Status PreOrderTraver(BiTree T,Status (* visit)(TElemType e)if(T)if(visit(T-e)if(PreOrderTraver(T-LChild,visit)if(PreOrderTraver(T-RChild,visit) return OK;return ERROR; else return OK;/中序遍历Status InOrderTraver(BiTree T,Status (* visit)(TElemType e)if(T)if(InOrderTraver(T-LChild,visit)if(visit(T-e)if(InOrderTraver(T-RChild,visit) return OK;return ERROR;else return OK;/后序遍历Status PostOrderTraver(BiTree T,Status (* visit)(TEle

《二叉树及其应用(实验五)》由会员第***分享，可在线阅读，更多相关《二叉树及其应用(实验五)》请在金锄头文库上搜索。