二叉树及其应用（实验五）

实验 五 二叉树及其应用

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\ int main() {

BiTree T;

printf(\请按照先序输入树值:\\n\

if(!Create(T)) printf(\存储空间分配失败\\n\ printf(\先序遍历该树为：\\n\

if(!PreOrderTraver(T,PrintElemType)) printf(\打印函数出错\\n\ printf(\

printf(\中序遍历该树为：\\n\

if(!InOrderTraver(T,PrintElemType)) printf(\打印函数出错\\n\ printf(\

printf(\后序遍历该树为：\\n\

if(!PostOrderTraver(T,PrintElemType)) printf(\打印函数出错\\n\ printf(\

printf(\总结点数有：%d\\n\

printf(\其中叶子结点数有：%d\\n\

printf(\其中一度结点数有：%d\\n\ printf(\其中二度结点数有：%d\\n\ printf(\该二叉树的深度为：%d\\n\ return 0; }

功能函数：

#include #include #include\

//先序建立二叉 Status Create(BiTree &T) {

char ch; scanf(\ 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(\ }

//先序遍历

Status PreOrderTraver(BiTree T,Status (* visit)(TElemType e)) { if(T) {

if(visit(T->e)) }

//中序遍历

Status InOrderTraver(BiTree T,Status (* visit)(TElemType e)) { if(T)

{

if(PreOrderTraver(T->LChild,visit)) }

return ERROR;

if(PreOrderTraver(T->RChild,visit)) return OK;

return OK;

}else return OK;

{

if(InOrderTraver(T->LChild,visit)) }

//后序遍历

Status PostOrderTraver(BiTree T,Status (* visit)(TElemType e)) { if(T) {

if(PostOrderTraver(T->LChild,visit)) }

//总结点数

Status Count(BiTree T) {

int num1,num2,num; if(T==NULL) num=0; else {

num1=Count(T->LChild);

num2=Count(T->RChild); num=num1+num2+1; {

if(PostOrderTraver(T->RChild,visit)) }

return ERROR;

if(visit(T->e)) return OK; {

if(visit(T->e)) }

return ERROR;

if(InOrderTraver(T->RChild,visit)) return OK;

}else return OK;

}else return OK;

}

return num; }

//叶子结点数

Status Countleaf(BiTree T) {

int num1,num2,num; if(T==NULL) num=0; else {

if(T->LChild==NULL&&T->RChild==NULL) num=1;

else {

num1=Countleaf(T->LChild);

num=num1+num2;

num2=Countleaf(T->RChild);

}

}

return num; }

//二度结点数

Status Counttwo(int n)//n为终端结点数 终端结点数==二度结点数+1 {

int 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; else {

depl=Depth(T->LChild); depr=Depth(T->RChild);

dep=1+(depl>depr?depl:depr); } return dep; }

? 运行结果：

（2） 建立一棵二叉排序树，并对其进行先序、中序、后序遍历。

程序代码部分：

头文件：

#ifndef _H_ #define _H_

#define OK 1 #define ERROR 0 #define OVERFLOW -2

typedef int Status; typedef int TElemType; typedef struct BiTNode {

TElemType e;

struct BiTNode *LChild,*RChild; }BiTNode,*BiTree;

Status Insert(BiTree &T,TElemType e); void 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)); #endif

主函数：

#include #include #include\ int main() {

BiTree T=NULL;

printf(\请输入树值建立二叉排序数（输-1表示输入结束）:\\n\ Create(T);

printf(\先序遍历该树为：\\n\

if(!PreOrderTraver(T,PrintElemType)) printf(\打印函数出错\\n\ printf(\

printf(\中序遍历该树为：\\n\

if(!InOrderTraver(T,PrintElemType)) printf(\打印函数出错\\n\ printf(\

printf(\后序遍历该树为：\\n\

if(!PostOrderTraver(T,PrintElemType)) printf(\打印函数出错\\n\ printf(\ return 0; }

功能函数：

#include #include #include\

//插入结点

Status Insert(BiTree &T,TElemType e) { if(T==NULL) {

if(!(T=(BiTree )malloc(sizeof(BiTNode)))) exit(OVERFLOW); T->e=e; T->LChild=T->RChild=NULL; } else { if(ee) Insert(T->LChild,e); if(e>T->e) Insert(T->RChild,e); }

return OK; }

//建立二叉排序

void Create(BiTree &T) {

TElemType e;

for(scanf(\ {

Insert(T,e); } }

//输出结点中的数值

Status PrintElemType(TElemType e) {

printf(\ 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)(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; }

? 运行结果：

（3）应用队列结构实现二叉树的层次遍历。

程序代码：

头文件:

#define OK 1 #define ERROR 0 #define OVERFLOW -2

typedef char ElemType; typedef int Status;

//二叉树结点 typedef struct BiTNode {

ElemType e;

struct BiTNode *lchild,*rchild; }BiTNode,*BiTree;

//队列结点

typedef struct QNode {

本文来源：https://www.bwwdw.com/article/3kp2.html