二叉树的应用举例实验报告(燕山大学).docx

《二叉树的应用举例实验报告(燕山大学).docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、题目：二叉树的应用举例班级：信息一班姓名：冯琴琴学号：1得分：实验三二叉树的应用举例一、实验目的要求学生必须掌握二叉树的建立及先序、中序、后序三种遍历方式，在此基础上实现树的一些简单应用问题二、实验内容及步骤1.二叉链表的建立，先（中、后）序遍历输入：字符串序列输出：先（中、后）序序列处理方法：通过补虚结点，使二叉树中各实际结点均具有左右孩子，再对该二叉树按先序遍历进行输入。以字符串的形式:根、左子树、右子树定义一棵二叉树：1)空树以

2、空白字符‘#’表示2)只含一个根结点的二叉树（图1示）以字符串‘A##’表示3)一般的二叉树，以图2为例，以下列字符串表示：AB#C##D##4)无论先序、中序、后序遍历二叉树，遍历时的搜索路线是相同的：从根节点出发，逆时针沿二叉树外缘移动，对每个节点均途经三次。先序遍历：第一次经过节点时访问。中序遍历：第二次经过节点时访问。后序遍历：第三次经过节点时访问图1图22.统计二叉树中叶子结点的个数，计算二叉树的深度。输入：字符串序列输出：叶子结点的个数，二叉树的深度处理方法：1)先序遍历二叉树。在遍历过程中查

3、找叶子结点，并计数。由此，需在遍历算法中增添一个“计数”的参数，并将算法中“访问结点”的操作改为：若是叶子，则计数器增1。2)后序遍历二叉树。从二叉树深度的定义可知，二叉树的深度应为其左、右子树深度的最大值加1。由此，先分别求得左、右子树的深度，算法中“访问结点”的操作为：求得左、右子树深度的最大值，然后加1。程序：#include#include#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineOVE

4、RFLOW-1typedefcharTElemType;typedefintStatus;constintMAX_TREE_SIZE=100;constintTREEINCREMENT=10;typedefstructBiTNode{//结点结构TElemTypedata;BiTNode*lchild,*rchild;//左右孩子指针}BiTNode,*BiTree;StatusInitBiTree(BiTree&T){if(!(T=newBiTNode))returnERROR;T->lchild=NU

5、LL;T->rchild=NULL;returnOK;}//InitBiTreevoidCreateBiTree(BiTree&T){TElemTypee;cin>>e;T->data=e;if(e!='#'){InitBiTree(T->lchild);InitBiTree(T->rchild);CreateBiTree(T->lchild);CreateBiTree(T->rchild);}}voidvisit(TElemTypee){cout<

6、(BiTreeT,void(*call)(TElemTypee))//先序遍历这里的函数指针调用输出函数call--调用{if(T->data!='#'){call(T->data);PreOrderTraverse(T->lchild,visit);PreOrderTraverse(T->rchild,visit);}}voidInOrderTraverse(BiTreeT,void(*call)(TElemTypee))//中序遍历{if(T->data!='#'){InOrderTraverse(T

7、->lchild,visit);call(T->data);InOrderTraverse(T->rchild,visit);}}voidPostOrderTraverse(BiTreeT,void(*call)(TElemTypee))//后序遍历{if(T->data!='#'){PostOrderTraverse(T->lchild,visit);PostOrderTraverse(T->rchild,visit);call(T->data);}}voidCountLeaf(BiTreeT,int&

8、count){if(T->data!='#'){if((T->lchild->data=='#')&&(T->rchild->data=='#'))count++;//对叶子结点计数CountLeaf(T->lchild,count);CountLeaf(T->rchild,count);}}intBiTreeDepth(BiTreeT){intldepth,rdepth,depth;if(T->data=='#')depth