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

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

2、 无论先序、中序、后序遍历二叉树，遍历时的搜索路线是相同的：从根节点出发，逆时针沿二叉树外缘移动，对每个节点均途经三次。先序遍历：第一次经过节点时访问。中序遍历：第二次经过节点时访问。后序遍历：第三次经过节点时访问图1 图2 2. 统计二叉树中叶子结点的个数，计算二叉树的深度。输入：字符串序列输出：叶子结点的个数，二叉树的深度处理方法：1) 先序遍历二叉树。在遍历过程中查找叶子结点，并计数。由此，需在遍历算法中增添一个“计数”的参数，并将算法中“访问结点”的操作改为：若是叶子，则计数器增1。2) 后序遍历二叉树。从二叉树深度的定义可知，二叉树的深度应为其左、右子树深度的最大值加1。由此，先分别

3、求得左、右子树的深度，算法中“访问结点”的操作为：求得左、右子树深度的最大值，然后加 1 。程序：#include#include #define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW -1typedef char TElemType ;typedef int Status ;const int MAX_TREE_SIZE =100 ;const int TREEINCREMENT= 10 ;typedef struct BiTNode /结点结构 TElemType data; BiTNode *lc

4、hild,*rchild; / 左右孩子指针 BiTNode, *BiTree;Status InitBiTree(BiTree &T) if (!(T=new BiTNode) return ERROR; T-lchild=NULL; T-rchild=NULL; return OK; /InitBiTreevoid CreateBiTree(BiTree &T) TElemType e;cine;T-data=e;if(e!=#)InitBiTree(T-lchild);InitBiTree(T-rchild);CreateBiTree(T-lchild);CreateBiTree(T-r

5、child); void visit(TElemType e)coutedata!=#)call(T-data); PreOrderTraverse ( T-lchild, visit);PreOrderTraverse ( T-rchild, visit);void InOrderTraverse (BiTree T, void(*call)(TElemType e) /中序遍历if(T-data!=#) InOrderTraverse( T-lchild, visit);call(T-data); InOrderTraverse( T-rchild, visit);void PostOrd

6、erTraverse (BiTree T, void(*call)(TElemType e) /后序遍历if(T-data!=#) PostOrderTraverse( T-lchild, visit); PostOrderTraverse( T-rchild, visit);call(T-data); void CountLeaf (BiTree T, int &count)if(T-data!=#) if (T-lchild-data=#)&(T-rchild-data=#) count+; / 对叶子结点计数 CountLeaf( T-lchild, count); CountLeaf(

7、 T-rchild, count); int BiTreeDepth (BiTree T) int ldepth,rdepth,depth; if(T-data=#) depth=0; else ldepth=BiTreeDepth (T-lchild); rdepth=BiTreeDepth (T-rchild); depth=1+(ldepthrdepth?ldepth:rdepth); return depth;void main() BiTree T;int depth,count=0;InitBiTree(T); CreateBiTree(T);cout先序遍历:;PreOrderT

8、raverse ( T, visit);coutendl;cout中序遍历:; InOrderTraverse( T, visit);coutendl;cout后序遍历:;PostOrderTraverse( T, visit);coutendl;CountLeaf (T, count);cout此二叉树叶子节点为:;coutcount;coutendl; depth=BiTreeDepth ( T);cout此二叉树深度为:;cout depth;coutendl;运行结果：3.中序线索二叉链表的建立及遍历输入：字符串序列输出：结点的相关信息，中序序列处理方法: 1) 在中序遍历过程中修改结

9、点的左、右指针域，以保存当前访问结点的“前驱”和“后继”信息。2) 遍历过程中，附设指针pre, 并始终保持指针pre指向当前访问的指针p所指结点的前驱。3) 中序线索二叉树结构对称。其中：第一个结点是最左下的结点，最后一个结点是最右下的结点。4) 在中序线索二叉树上找结点的(直接)后继/前驱方法：a) 若该结点有右孩子，其后继为其右子树中最左下的结点；b) 若该结点无右孩子，其后继由rchild指向：其后继为满足以下条件的最小子树的根r：该结点为r的左子树中最右下的结点。程序：#include#include #define TRUE 1#define FALSE 0#define OK 1

10、#define ERROR 0#define OVERFLOW -1typedef char TElemType ;typedef int Status ;typedef enum Link, Thread PointerThr; /Link=0指针, Thread =1线索typedef struct BiThrNode TElemType data; BiThrNode *lchild, *rchild; /左右指针 PointerThr LTag, RTag; /左右标志 BiThrNode, *BiThrTree;Status InitBiThrTree(BiThrTree &T) i

11、f (!(T=new BiThrNode) return ERROR; T-lchild=NULL; T-rchild=NULL;T-LTag=Link;T-RTag=Link; return OK; void CreateBiThrTree(BiThrTree &T) TElemType e;cine;T-data=e;if(e!=#)InitBiThrTree(T-lchild);InitBiThrTree(T-rchild);CreateBiThrTree(T-lchild);CreateBiThrTree(T-rchild); void InThreading(BiThrTree &p

12、re, 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); Status InOrderThreading(BiThrTree &Thrt, BiThrTree &T) BiThrTree pre,p;Thrt-RTag=Thread;Thrt-rchild=Thrt;if(!T)Thrt-lchild=Thrt;elseThrt-lchild=T;pre=Thrt; p=T; InThreading(pre, p); pre-RTag = Thread; pre-rchild = Thrt; Thrt-rchild=pre; return OK; void visit(TElemType e)coutelchild; while (p-LTag!=Thread)p=p-lchild;while(p-RTag!=Thread|p-rchild!=T) visit(p-d