实验五二叉树及其应用
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
#define OVERFLOW -2
typedef int Status;
typedef char TElemType;
typedef struct BiTNode
{
TElemType e;
struct BiTNode *LChild,*RChild;
}BiTNode,*BiTree;
Status Create(BiTree &T);
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));
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
#include
#include"1.h"
int 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("总结点数有：%d\n",Count(T));
printf("其中叶子结点数有：%d\n",Countleaf(T));
printf("其中一度结点数有：%d\n",Countone(Count(T),Countleaf(T),Counttwo(Countleaf(T))));
printf("其中二度结点数有：%d\n",Counttwo(Countleaf(T)));
printf("该二叉树的深度为：%d\n",Depth(T));
return 0;
}
功能函数：
#include
#include
#include"1.h"
//先序建立二叉
Status Create(BiTree &T)
{
char ch;
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);
}
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;
}
//中序遍历
Status InOrderTraver(BiTree T,Status (* visit)(TElemType e))
{
if(T)
