实验三二叉树的基本操作实现及其应用.docx

《实验三二叉树的基本操作实现及其应用.docx》由会员分享，可在线阅读，更多相关《实验三二叉树的基本操作实现及其应用.docx（8页珍藏版）》请在三一办公上搜索。

1、实验三 二叉树的基本操作实现及其应用二叉树的基本操作实现及其应用 一、实验目的 1熟悉二叉树结点的结构和对二叉树的基本操作。 2掌握对二叉树每一种操作的具体实现。 3学会利用递归方法编写对二叉树这种递归数据结构进行处理的算法。 4.会用二叉树解决简单的实际问题。 二、实验内容 设计程序实现二叉树结点的类型定义和对二叉树的基本操作。该程序包括二叉树结构类型以及每一种操作的具体的函数定义和主函数。 1 按先序次序建立一个二叉树 ， 2按遍历输出二叉树的所有结点 以上比做，以下选做 3求二叉树中所有结点数 4求二叉树的深度 三、实验步骤 、数据结构与核心算法的设计描述 /* 定义DataType为c

2、har类型 */ 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二叉树初始化成功!ch; if(ch=#) BT=NULL; else if(!(BT=(BitTree)mall

3、oc(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; else cout不是空二叉树!endl; 4、/*按任一种遍历次序输出二叉树中的所有结点 */ void BinTraverse(BitTree &BT)/按先序序列建立二叉树 if(BT!=NULL) coutdata; BinTr

4、averse(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+(depthLeftdepthRight?depthLeft:depthRight); else depthval=0; return depthval; 6、/* 求二叉树中所有结点数 */ int

5、BinTreeCount(BitTree BT) int node; if(BT) int lchild=BinTreeCount(BT-lchild); int rchild=BinTreeCount(BT-rchild); node=lchild+rchild+1; else node=0; return node; 、函数调用及主函数设计 主函数 初始化二叉树 TreeInit(BitTree *BT) 按先序次序建立一个二叉树BinTreeCreat(BitTree *BT) 先序序列遍历二叉树BinTraverse(BitTree *BT) 球二叉树的深度BintBinTreeDep

6、th(BitT求二叉树的所有节点数ree BT) BinTreeCount(BitTree BT) 程序调试及运行结果分析 测试数据： 1、初始化二叉树； 2、按先序序列建立二叉树；3、判断二叉树是否为空；4、先序序列遍历二叉树；5、求二叉树的深度；6、求二叉树节点的个数。 数据测试如下截图： 实验总结 通过这次二叉树的基本操作的代码设计与算法设计的学习，我学会了这章学的二叉树的基本操作的等基础值，同时也发现了自己的一些问题，比如基本知识不是太扎实，很多只是还不是太熟悉等问题，需要在今后的学习中更加努力，学好接下来的课程。 四、主要算法流程图及程序清单 1、主要算法流程图： 开始界面 主函数

7、初始化二叉先序建立 判空 先序遍历 求深度 求节点总数 输出数据 结束 2、程序清单 #include #include 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二叉树初始化成功!ch; if(ch=#) BT=NULL; else

8、if(!(BT=(BitTree)malloc(sizeof(BitNode) exit(0); BT-data=ch; BinTreeCreat(BT-lchild); BinTreeCreat(BT-rchild); return 0; /cout按先序序列建立一个二叉树已经完成!data=NULL) cout是空二叉树!endl; else cout不是空二叉树!endl; void BinTraverse(BitTree &BT)/先序序列遍历二叉树 if(BT!=NULL) coutdata; BinTraverse(BT-lchild); BinTraverse(BT-rchild

9、); int BinTreeDepth(BitTree BT)/求二叉树的深度 int depthval; if(BT) int depthLeft=BinTreeDepth(BT-lchild); int depthRight=BinTreeDepth(BT-rchild); depthval=1+ (depthLeftdepthRight?depthLeft:depthRight); else depthval=0; return depthval; int BinTreeCount(BitTree BT)/求二叉树中所有结点数 int node; if(BT) int lchild=Bi

10、nTreeCount(BT-lchild); int rchild=BinTreeCount(BT-rchild); node=lchild+rchild+1; else node=0; return node; void main int i; BitTree BT; cout1、初始化二叉树:n2、按先序序列建立二叉树n3、判断二叉树是否为空:; coutn4、先序序列遍历二叉树n5、求二叉树的深度n6、求二叉树节点的个数endl; for(;) couti; 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; else return ;