二叉树及其应用实验报告

1、为了适应公司新战略的发展，保障停车场安保新项目的正常、顺利开展，特制定安保从业人员的业务技能及个人素质的培训计划二叉树及其应用实验报告题目：班级：姓名：学号：得分：二叉树的应用举例信息一班冯琴琴1XX实验三二叉树的应用举例一、实验目的要求学生必须掌握二叉树的建立及先序、中序、后序三种遍历方式，在此基础上实现树的一些简单应用问题二、实验内容及步骤1.二叉链表的建立，先序遍历输入：字符串序列输出：先序序列处理方法：通过补虚结点，使二叉树中各实际结点均具有左右孩子，再对该二叉树按先序遍历进行输入。以字符串的形式:根、左子树、右子树定义一棵二叉树：1)空树以空白字符#表示2)只含一个根结点的二叉树以字符串A#表示3)一般的二叉树，以图2为例，以下列字符串表示：AB#C#D#4)无论先序、中序、后序遍历二叉树，遍历时的搜索路线是相同的：从根节点出发，逆时针沿二叉树外缘移动，对每个节点均途经三次。先序遍历：第一次经过节点时访问。中序遍历：第二次经过节点时访问。后序遍历：第三次经过节点时访问图1图22.统计二叉树中叶子结点的个数，计算二叉树的深度。输入：字符串序列输出：叶子结点的个数，二叉树的深度处

2、理方法：1)先序遍历二叉树。在遍历过程中查找叶子结点，并计数。由此，需在遍历算法中增添一个“计数”的参数，并将算法中“访问结点”的操作改为：若是叶子，则计数器增1。2)后序遍历二叉树。从二叉树深度的定义可知，二叉树的深度应为其左、右子树深度的最大值加1。由此，先分别求得左、右子树的深度，算法中“访问结点”的操作为：求得左、右子树深度的最大值，然后加1。程序：#include#include#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineOVERFLOW-1typedefcharTElemType;typedefintStatus;constintMAX_TREE_SIZE=100;constintTREEINCREMENT=10;typedefstructBiTNode/结点结构TElemTypedata;BiTNode*lchild,*rchild;/左右孩子指针BiTNode,*BiTree;StatusInitBiTree(BiTree&T)if(!(T=newBiTNode)returnERROR;T-lchild=

3、NULL;T-rchild=NULL;returnOK;/InitBiTreevoidCreateBiTree(BiTree&T)TElemTypee;cine;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(

4、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;elseldepth=BiTreeDepth(T-lchild);rdepth=BiTreeDepth(T-rchild);voidmain()BiTreeT;intdepth,count=0;InitBiTree(T);depth=1+(ldept

5、hrdepth?ldepth:rdepth);returndepth;CreateBiTree(T);cout#include#defineTRUE1#defineFALSE0#defineSta(来自:写论文网:二叉树及其应用实验报告)ck_Size50typedefstructNodechardata;structNode*LChild;structNode*RChild;BiTNode,*BiTree;typedefBiTreeStackElementType;typedefstructStackElementTypeelemStack_Size;inttop;SeqStack;/初始化voidInitStack(SeqStack*S)S-top=-1;/进栈intPush(SeqStack*S,StackElementTypex)if(S-top=Stack_Size-1)return(FALSE);S-top+;S-elemS-top=x;return(TRUE);/出栈intPop(SeqStack*S,StackElementType*x)if(S-top=-1)retu

6、rn(FALSE);else*x=S-elemS-top;S-top-;return(TRUE);/先序遍历voidPreOrder(BiTreeroot)if(root!=NULL)printf(%c,root-data);PreOrder(root-LChild);PreOrder(root-RChild);/中序遍历voidInOrder(BiTreeroot)if(root!=NULL)InOrder(root-LChild);printf(%c,root-data);InOrder(root-RChild);/后序遍历voidPostOrder(BiTreeroot)if(root!=NULL)PostOrder(root-LChild);PostOrder(root-RChild);printf(%c,root-data);山东工商学院数据结构实验指导及报告书XX/XX学年姓名：学号：班级：指导教师：Xx学院XX年11月25日第一学期实验三二叉树一、实验目的1、掌握二叉树的基本特性2、掌握二叉树的先序、中序、后序的递归遍历算法3、理解二叉树的先序、中序、后序的非递归遍历算法

7、4、通过求二叉树的深度、叶子结点数和层序遍历等算法，理解二叉树的基本特性二、实验预习说明以下概念1、二叉树：是另一种树型结构，它的特点是每个结点至多只有两棵子树，并且二叉树有左右之分，其次序不能任意颠倒。2、递归遍历：1、非递归遍历：4、层序遍历：三、实验内容和要求1、阅读并运行下面程序，根据输入写出运行结果，并画出二叉树的形态。#include#include#defineMAX20typedefstructBTNode/*节点结构声明*/chardata;/*节点数据*/structBTNode*lchild;structBTNode*rchild;/*指针*/*BiTree;BiTreecreateBiTree(BiTreet)/*先序遍历创建二叉树*/chars;printf(npleaseinputdata:(exitfor#);s=getche();if(s=#)t=NULL;returnt;t=(BiTree)malloc(sizeof(structBTNode);if(t=NULL)printf(Memoryallocfailure!);exit(0);t-data=s

8、;t-lchild=createBiTree(t-lchild);/*递归建立左子树*/t-rchild=createBiTree(t-rchild);/*递归建立右子树*/returnt;voidPreOrder(BiTreep)/*先序遍历二叉树*/if(p!=NULL)printf(%c,p-data);PreOrder(p-lchild);PreOrder(p-rchild);voidInOrder(BiTreep)/*中序遍历二叉树*/if(p!=NULL)InOrder(p-lchild);printf(%c,p-data);InOrder(p-rchild);voidPostOrder(BiTreep)/*后序遍历二叉树*/if(p!=NULL)PostOrder(p-lchild);PostOrder(p-rchild);printf(%c,p-data);voidPreorder_n(BiTreep)/*先序遍历的非递归算法*/BiTreestackMAX,q;inttop=0,i;for(i=0;idata);if(q-rchild!=NULL)stacktop+=q-rchild;if(q-lchild!=NULL)q=q-lchild;elseif(top0)q=stac

《二叉树及其应用实验报告》由会员bin****86分享，可在线阅读，更多相关《二叉树及其应用实验报告》请在金锄头文库上搜索。