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

《二叉树及其应用(实验五)》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实验五二叉树及其应用1•目的要求：（1）通过实验掌握二叉树的两种基本的存储结构，及二叉树的建立、遍历，并加以应用。（2）Huffman树建立、编码。2.实验内容：（1）按先序次序输入二义树中结点的值，建立一棵以二义链表作存储结构的二义树,然示按先序、屮序、后序顺序分别遍历这棵二叉树，并完成二叉树的相应信息的统计（如各种结点数冃、二叉树的鬲度等）；（2）建立一棵二义排序树，并对其进行先序、中序、后序遍历。（3）M用队列结构实现二叉树的层次遍历。（4）设计一个完整的编码系统：针对一篇文档，统计各个字符的出现次数，并为其设计Huffman编码。注：（1

2、）~（2）必做，（3）〜（4）选做。三.实验主要流程、棊木操作或核心代码、算法片段（该部分如不够填写，请另加附页）（1）按先序次序输入二义树中结点的值，建立一棵以二义链表作存储结构的二义树,然后按先序、中序、后序顺序分别遍历这棵二叉树，并完成二叉树的相应信息的统计（如各种结点数目、二叉树的高度等）；程序代码:头文件:#ifndef_H一#define_H_#dcfincOK1#defineERROR0#defineOVERFLOW-2typedefintStatus;typedefcharTElemType;typedefstructBiTNod

3、e{TElemTypee;structBiTNode*LChild,*RChild;}BiTNode,*BiTrcc;StatusCreate(BiTree&T);StatusPrintElemType(TElemTypee);StatusPreOrderTraver(BiTreeT,Status(*visit)(TElemTypee));StatusInOrderTraver(BiTreeT,Status(*visit)(TElemTypee));StatusPostOrderTraver(BiTreeT,Status(*visit)(TEle

4、mTypee));StatusCount(BiTreeT);StatusCountleaf(BiTreeT);StatusCounttwo(intn);StatusCountone(intn,intn(),intn2);StatusDepth(B汀reeT);#endif主函数：#include#include#includeHl.hHintmain(){BiTreeT;printf(”请按照先序输入树值:");if(!Create(T))printf(”存储空间分配失败”);printf(”先序遍历

5、该树为：”)；if(!PreOrderTraver(T,PrintElemType))printf(H打印函数11J错”)；printf(””);printf("中序遍历该树为:M);if(!InOrderTraver(T,PrintElemType))printf(u打印函数出错”);printf("M);printf(”后序遍历该树为:");if(!PostOrderTraver(T,PrintElemType))printf(M打印函数出错K);printf(nn);printfC'总结点数有:%d"

6、,Count(T));printf(”其中叶子结点数有：%dH,Countleaf(T));printfC'其屮一度结点数育：%d",Countone(Count(T),Countleaf(T),Counttwo(Countleaf(T))));printf("其中二度结点数有:%d",Counttwo(Countleaf(T)));printfC该二叉树的深度为：%dH,Depth(T));return0;功能函数:#include#includc#includeMl.hn〃先序建立二叉St

7、atusCreate(BiTree&T)charch;scanf("%c",&ch);if(ch==,')T二NULL;else{if(!(T=(BiTree)malloc(sizeof(BiTNode))))exit(OVERFLOW);T->e=ch;Create(T->LChild);Create(T->RChild);}returnOK:}〃输出结点中的数值StatusPrintElemType(TElemTypee){printf("%c",e);returnOK;}〃先序遍丿力StatusPrcOrdcrTravcr(BiTrccT,

8、Status(*visit)(TElcmTypcc)){if(T){if(visit(T->e)){if(PreOrderTraver(