2023年6月22日发(作者：)

实验十一 二叉树的应用

姓名：高翠莹 学号：6103315009 专业班级：数媒151

一、实验项目名称

二叉树的应用

二、实验目的

1.通过实验理解二叉树的逻辑结构；

2.通过实验掌握二叉树的二叉链表存储结构；

3.通过实验掌握二叉树的应用。

三、实验基本原理

1、数据结构

typedef struct BiTNode{

char data;

struct BiTNode *lchild,*rchild;

}BiTNode,*BiTree;

2、算法思想

这次实验主要是对二叉树的一些应用：

（1）在二叉树中查找值为value的结点：

即寻找每一个节点的data,若与value相同则返回；

（2）统计出二叉树中叶子结点的数目：

如果一个左孩子和右孩子都为空，则返回1，然后递归访问左子树和右子树，统计

出所有的叶子结点；

（3）统计出二叉树中非叶子结点的数目：

用所有结点个数减去叶子结点个数即可；

（4）统计出二叉树中所有结点的数目：

递归调用，返回左子树结点个数加右结点个数，再加1；

（5）求二叉树的高度

递归求左子树高度h1和右子树高度h2，如果h1>h2，则返回h1+1,否则返回h2+1；

3、算法描述

见代码

四、主要仪器设备及耗材

1、硬件环境

2、开发平台

Dev C++

五、实验步骤

1.分析题目，确定数据结构类型，设计正确的算法；

2.编写代码；

3.运行及调试程序；

4.修改程序，提高其健壮性。

六、实验数据及处理结果

1、程序清单

#include

#include

using namespace std;

typedef struct BiTNode{

char data;

struct BiTNode *lchild,*rchild;

}BiTNode,*BiTree;

//按先序序列创建二叉树

int CreateBiTree(BiTree &T){

char data;

scanf("%c",&data);

if(data == '#'){

T = NULL;

}

else{

T = (BiTree)malloc(sizeof(BiTNode));

//生成根结点

T->data = data;

//构造左子树

CreateBiTree(T->lchild); //构造右子树

CreateBiTree(T->rchild);

}

return 0;

}

//输出

void Visit(BiTree T){

if(T->data != '#'){

printf("%c ",T->data);

}

}

//先序遍历

void PreOrder(BiTree T){

if(T != NULL){

//访问根节点

Visit(T);

//访问左子结点

PreOrder(T->lchild);

//访问右子结点

PreOrder(T->rchild);

}

}

//叶子结点个数

int Calleaf(BiTree T)

{

if (T == NULL)

return 0;

if (T->lchild == NULL && T->rchild == NULL)

return 1;

return Calleaf(T->lchild) + Calleaf(T->rchild);

} //统计树的高度

int BTreeHigh(BiTNode *tree)

{

int h1,h2;

if(tree == NULL)

return 0;

else

{

h1 = BTreeHigh(tree->lchild);//左子树高度

h2 = BTreeHigh(tree->rchild);//右子树高度

if(h1 > h2)

return h1+1;

else

return h2+1;

}

}

//树的节点

int countBTreeNode (BiTree tree)

{

if(tree == NULL)

return 0;

else

return (countBTreeNode(tree->lchild) + countBTreeNode(tree->rchild) + 1);

}

//查找值为value的节点

void locate(BiTree t, char x)//在二叉树t中查找值为x的结点

{

BiTree p;

p=t;

if (t == NULL) printf("无此节点n"); else if( t->data == x) printf("%cn",p->data);

else

{ p=t->lchild;

if(p) locate(t->lchild, x);

else

locate(t->rchild, x);

}

}

void Tips(){

}

int main(){

cout<<"***************二叉树的应用*************"<

cout<<"一、创建二叉树"<

BiTree T;

cout<<"按先序次序输入二叉树中结点的值（一个字符），‘#’表示空树"<

CreateBiTree(T);

cout<<"先序遍历这课树： "<

PreOrder(T);

cout<

cout<<"二、具体操作"<

Tips();

int op;

char x;

cout<

cout<<"按相应数字进行操作"<

cout<<"1.计算二叉树中所有结点的数目"<

cout<<"2.计算二叉树中所有叶子结点的数目"<

cout<<"3.计算二叉树中所有非叶子结点的数目"<

cout<<"4.查找二叉树中值为value的结点"<

cout<<"5.求二叉树中的高度"<

cout<<"0.退出"<

cin>>op;

while(op){

switch(op){

case 1:

case 2:

cout<<"所有叶子结点个数为： ";

cout<

break;

case 3:

int count;

cout<<"非叶子结点的个数为： "<

case 4:

cout<<"请输入value的值：";

cin>>x;

cout<<"值为"<

cout<<"树的所有节点个数为： ";

cout<

break;

Calleaf(T)<

}

locate(T,x);

break;

case 5:

cout<<"树的高度为： ";

cout<

break;

Tips(); cin>>op;

}

}

2、运行结果

（1）创建

（2）操作

求所有结点个数：

求所有叶子结点个数：

求所有非叶子结点个数：

求值为value的结点：

求二叉树的高度：

七、思考讨论题或体会或对改进实验的建议

这次实验之后，我更加了解树的逻辑结构，它有很强的递归属性，所以只要理解了递归的本质，就不难理解本次实验的操作，因为在操作时基本上都用到了递归方法，可以用少量的代码就能实现功能。

八、参考资料

参考1：《数据结构C语言版》清华大学出版社