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

题目：二叉树的应用举例班级：信息一班姓名：冯琴琴学号：120108010001得分：实验三二叉树的应用举例一、实验目的要求学生必须掌握二叉树的建立及先序、中序、后序三种遍历方式，在此基础上实现树的一些简单应用问题二、实验内容及步骤1.二叉链表的建立，先（中、后）序遍历输入：字符串序列输出：先（中、后）序序列处理方法：通过补虚结点，使二叉树中各实际结点均具有左右孩子，再对该二叉树按先序遍历进行输入。以字符串的形式:根、左子树、右子树定义一棵二叉树：1)空树以空白字符‘#’表示2)只含一个根结点的二叉树（图1示）以字符串‘A##’表示3)一般的二叉树，以图2为例，以下列字符串表示：AB#C##D##4)无论先序、中序、后序遍历二叉树，遍历时的搜索路线是相同的：从根节点出发，逆时针沿二叉树外缘移动，对每个节点均途经三次。先序遍历：第一次经过节点时访问。中序遍历：第二次经过节点时访问。后序遍历：第三次经过节点时访问图1图22.统计二叉树中叶子结点的个数，计算二叉树的深度。输入：字符串序列输出：叶子结点的个数，二叉树的深度处理方法：1)先序遍历二叉树。在遍历过程中查找叶子结点，并计数。由此，需在遍历算法中增添一个“计数”的参数，并将算法中“访问结点”的操作改为：若是叶子，则计数器增1。2)后序遍历二叉树。从二叉树深度的定义可知，二叉树的深度应为其左、右子树深度的最大值加1。由此，先分别求得左、右子树的深度，算法中“访问结点”的操作为：求得左、右子树深度的最大值，然后加1。程序：#includeiostream.h#includestdlib.h#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=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){coute'';}voidPreOrderTraverse(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-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&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=0;else{ldepth=BiTreeDepth(T-lchild);rdepth=BiTreeDepth(T-rchild);depth=1+(ldepthrdepth?ldepth:rdepth);}returndepth;}voidmain(){BiTreeT;intdepth,count=0;InitBiTree(T);CreateBiTree(T);cout先序遍历:;PreOrderTraverse(T,visit);coutendl;cout中序遍历:;InOrderTraverse(T,visit);coutendl;cout后序遍历:;PostOrderTraverse(T,visit);coutendl;CountLeaf(T,count);cout此二叉树叶子节点为:;coutcount;coutendl;depth=BiTreeDepth(T);cout此二叉树深度为:;coutdepth;coutendl;}运行结果：3.中序线索二叉链表的建立及遍历输入：字符串序列输出：结点的相关信息，中序序列处理方法:1)在中序遍历过程中修改结点的左、右指针域，以保存当前访问结点的“前驱”和“后继”信息。2)遍历过程中，附设指针pre,并始终保持指针pre指向当前访问的指针p所指结点的前驱。3)中序线索二叉树结构对称。其中：第一个结点是最左下的结点，最后一个结点是最右下的结点。4)在中序线索二叉树上找结点的(直接)后继/前驱方法：a)若该结点有右孩子，其后继为其右子树中最左下的结点；b)若该结点无右孩子，其后继由rchild指向：其后继为满足以下条件的最小子树的根r：该结点为r的左子树中最右下的结点。程序：#includeiostream.h#includestdlib.h#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineOVERFLOW-1typedefcharTElemType;typedefintStatus;typedefenum{Link,Thread}PointerThr;//Link==0指针,Thread==1线索typedefstructBiThrNode{TElemTypedata;BiThrNode*lchild,*rchild;//左右指针PointerThrLTag,RTag;//左右标志}BiThrNode,*BiThrTree;StatusInitBiThrTree(BiThrTree&T){if(!(T=newBiThrNode))returnERROR;T-lchild=NULL;T-rchild=NULL;T-LTag=Link;T-RTag=Link;returnOK;}voidCreateBiThrTree(BiThrTree&T){TElemTypee;cine;T-data=e;if(e!='#'){InitBiThrTree(T-lchild);InitBiThrTree(T-rchild);CreateBiThrTree(T-lchild);CreateBiThrTree(T-rchild);}}voidInThreading(BiThrTree&pre,BiThrTree&p){if(p-data!='#'){InThreading(pre,p-lchild);if(p-lchild-data=='#'){p-LTag=Thread;p-lchild=pre;}if(pre-rchild-data=='#'){pre-RTag=Thread;pre-rchild=p;}pre=p;InThreading(pre,p-rchild);}}StatusInOrderThreading(BiThrTree&Thrt,BiThrTree&T){BiThrTreepre,p;Thrt-RTag=Thread;Thrt-rchild=Thrt;if(!T)Thrt-lchild=Thrt;else{Thrt-lchild=T;pre=Thrt;p=T;InThreading(pre,p);pre-RTag=Thread;pre-rchild=Thrt;Thrt-rchild=pre;}returnOK;}voidvisit(TElemTypee){coute'';}voidInOrderTraverse_Thr(BiThrTreeT,void(*call)(TElemTypee)){BiThrTreep;p=T-lchild;while(p-LTag!=Thread){p=p-lchild;}while(p-RTag!=Thread||p-rchild!=T){visit(p-data);p=p-rchild;}coutp-data;}voidmain(){BiThrTreeT,Thrt;InitBiThrTree(Thrt);InitBiThrTree(T);CreateBiThrTree(T);InOrderThreading(Thrt,T);cout中序线索二叉链表的遍历:;InOrderTraverse_Thr(Thrt,visit);coutendl;}运行结果：