二叉树的基本操作实现及其应用一、实验目的1．熟悉二叉树结点的结构和对二叉树的基本操作。

2．掌握对二叉树每一种操作的具体实现。

3．学会利用递归方法编写对二叉树这种递归数据结构进行处理的算法。

4.会用二叉树解决简单的实际问题。

二、实验内容设计程序实现二叉树结点的类型定义和对二叉树的基本操作。

该程序包括二叉树结构类型以及每一种操作的具体的函数定义和主函数。

1 按先序次序建立一个二叉树，2按（A:先序 B:中序 C:后序）遍历输出二叉树的所有结点以上比做，以下选做3求二叉树中所有结点数4求二叉树的深度三、实验步骤㈠、数据结构与核心算法的设计描述/* 定义DataType为char类型 */typedef char DataType;/* 二叉树的结点类型 */typedef struct BitNode{ DataType data;struct BitNode *lchild,*rchild;}*BitTree;相关函数声明：1、/* 初始化二叉树，即把树根指针置空 */void BinTreeInit(BitTree *BT){BT=(BitTree)malloc(sizeof(BitNode));BT->data=NULL;cout<<"二叉树初始化成功!"<<endl;}2、/* 按先序次序建立一个二叉树*/int BinTreeCreat(BitTree &BT){char ch;cin>>ch;if(ch=='#') BT=NULL;else{if(!(BT=(BitTree)malloc(sizeof(BitNode))))exit(0);BT->data=ch;BinTreeCreat(BT->lchild);BinTreeCreat(BT->rchild);}return 0;}3、/* 检查二叉树是否为空 */void BinTreeEmpty(BitTree &BT){if(BT->data==NULL)cout<<"是空二叉树!"<<endl;elsecout<<"不是空二叉树!"<<endl;}4、/*按任一种遍历次序（包括按先序、中序、后序、按层次）输出二叉树中的所有结点 */void BinTraverse(BitTree &BT)//按先序序列建立二叉树{if(BT!=NULL){cout<<BT->data;BinTraverse(BT->lchild);BinTraverse(BT->rchild);}}5、/* 求二叉树的深度 */int BinTreeDepth(BitTree BT){int depthval;if(BT){int depthLeft=BinTreeDepth(BT->lchild);int depthRight=BinTreeDepth(BT->rchild);depthval=1+(depthLeft>depthRight?depthLeft:depthRight);}else depthval=0;return depthval;}6、/* 求二叉树中所有结点数 */int BinTreeCount(BitTree BT){int node;if(BT){int lchild=BinTreeCount(BT->lchild);int rchild=BinTreeCount(BT->rchild);node=lchild+rchild+1;}elsenode=0;return node;}㈡、函数调用及主函数设计㈢程序调试及运行结果分析测试数据： 1、初始化二叉树； 2、按先序序列建立二叉树；3、判断二叉树是否为空；4、先序序列遍历二叉树；5、求二叉树的深度；6、求二叉树节点的个数。

数据测试如下截图：㈣实验总结通过这次二叉树的基本操作的代码设计与算法设计的学习，我学会了这章学的二叉树的基本操作的等基础值，同时也发现了自己的一些问题，比如基本知识不是太扎实，很多只是还不是太熟悉等问题，需要在今后的学习中更加努力，学好接下来的课程。

四、主要算法流程图及程序清单1、主要算法流程图：2、程序清单#include<iostream.h>#include<stdlib.h>typedef char DataType;typedef struct BitNode{DataType data;struct BitNode *lchild,*rchild;}*BitTree;void BinTreeInit(BitTree &BT)//初始化二叉树，即把树根指针置空{BT=(BitTree)malloc(sizeof(BitNode));BT->data=NULL;cout<<"二叉树初始化成功!"<<endl;}int BinTreeCreat(BitTree &BT)//按先序次序建立一个二叉树{char ch;cin>>ch;if(ch=='#') BT=NULL;else{if(!(BT=(BitTree)malloc(sizeof(BitNode))))exit(0);BT->data=ch;BinTreeCreat(BT->lchild);BinTreeCreat(BT->rchild);}return 0;//cout<<"按先序序列建立一个二叉树已经完成!"<<endl;}void BinTreeEmpty(BitTree &BT)//检查二叉树是否为空{if(BT->data==NULL)cout<<"是空二叉树!"<<endl;elsecout<<"不是空二叉树!"<<endl;}void BinTraverse(BitTree &BT)//先序序列遍历二叉树{if(BT!=NULL){cout<<BT->data;BinTraverse(BT->lchild);BinTraverse(BT->rchild);}}int BinTreeDepth(BitTree BT)//求二叉树的深度{int depthval;if(BT){int depthLeft=BinTreeDepth(BT->lchild);int depthRight=BinTreeDepth(BT->rchild);depthval=1+(depthLeft>depthRight?depthLeft:depthRight);}else depthval=0;return depthval;}int BinTreeCount(BitTree BT)//求二叉树中所有结点数{int node;if(BT){int lchild=BinTreeCount(BT->lchild);int rchild=BinTreeCount(BT->rchild);node=lchild+rchild+1;}elsenode=0;return node;}void main(){int i;BitTree BT;cout<<"1、初始化二叉树:"<<"\n2、按先序序列建立二叉树"<<"\n3、判断二叉树是否为空:";cout<<"\n4、先序序列遍历二叉树"<<"\n5、求二叉树的深度"<<"\n6、求二叉树节点的个数"<<endl;for(;;){cout<<"输出你所需的操作:";cin>>i;if(i==1)BinTreeInit(BT);else if(i==2){cout<<"输入你要建立的二叉树:"<<endl;BinTreeCreat(BT);}else if(i==3)BinTreeEmpty(BT);else if(i==4)BinTraverse(BT);else if(i==5)cout<<"二叉树的深度:"<<BinTreeDepth(BT)<<endl;else if(i==6)cout<<"二叉树的节点数"<<BinTreeCount(BT)<<endl;elsereturn ;}}。