二叉树及其应用实验报告.docx

二叉树及其应用实验报告题目: 班级: 姓名: 学号:得分:二叉树的应用举例信息一班冯琴琴 1XX 实验三二叉树的应用举例一、实验目的要求学生必须掌握二叉树的建立及先序、中序、后序三种遍历方式,在此基础上实现树的一些简单应用问题二、实验内容及步骤 ,先序遍历输入:字符串序列输出:先序序列处理方法:通过补虚结点,使二叉树中各实际结点均具有左右孩子,再对该二叉树按先序遍历进行输入。以字符串的形式:根、左子树、右子树定义一棵二叉树: 1)空树以空白字符‘#’表示 2)只含一个根结点的二叉树以字符串‘A##’表示 3)一般的二叉树,以图2为例,以下列字符串表示:AB#C##D## 4)无论先序、中序、后序遍历二叉树,遍历时的搜索路线是相同的:从根节点出发,逆时针沿二叉树外缘移动,对每个节点均途经三次。先序遍历:第一次经过节点时访问。中序遍历:第二次经过节点时访问。后序遍历:第三次经过节点时访问图1 图2 ,计算二叉树的深度。输入:字符串序列输出:叶子结点的个数,二叉树的深度处理方法: 1)先序遍历二叉树。在遍历过程中查找叶子结点,并计数。由此,需在遍历算法中增添一个“计数”的参数,并将算法中“访问结点”的操作改为:若是叶子,则计数器增1。 2)后序遍历二叉树。从二叉树深度的定义可知,二叉树的深度应为其左、右子树深度的最大值加1。由此,先分别求得左、右子树的深度,算法中“访问结点”的操作为:求得左、右子树深度的最大值,然后加1。程序: #include #include #RUE1 #defineFALSE0 #defineOK1 #defineERROR0 #defineOVERFLOW-1 typedefcharTElemType; typedefintStatus; constintMAX_TREE_SIZE=100; constintTREEINCREMENT=10; typedefstructBiTNode{//结点结构 TElemTypedata; BiTNode*lchild,*rchild; //左右孩子指针}BiTNode,*BiTree; StatusInitBiTree(BiTree&T) {if(!(T=newBiTNode))returnERROR; T->lchild=NULL;T->rchild=NULL; returnOK; }//InitBiTree voidCreateBiTree(BiTree&T) {TElemTypee; } cin>>e;T->data=e;if(e!='#'){InitBiTree(T->lchild);InitBiTree(T->rchild);CreateBiTree(T->lchild);CreateBiTree(T->rchild);} voidvisit(TElemTypee) { } voidPreOrderTraverse(BiTreeT,void(*call)(TElemTypee))//先序遍历这里的函数指针调用输出函数call--调用{if(T->data!='#'){ } voidInOrderTraverse(BiTreeT,void(*call)(TElemTypee))//中序遍历{if(T->data!='#'){ } voidPostOrderTraverse(BiTreeT,void(*call)(TElemTypee))//后序遍历{if(T->data!='#'){ } voidCountLeaf(BiTreeT,int&count){ if(T->data!='#'){PostOrderTraverse(T->lchild,visit);PostOrderTraverse(T->rchild,visit);}call(T->data);InOrderTraverse(T->lchild,visit);call(T->data);}call(T->data);PreOrderTraverse(T->lchild,visit);PreOrderTraverse(T->rchild,visit);coutrchild,visit);} 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=0;}else{ ldepth=BiTreeDepth(T->lchild)