数据结构实验三——二叉树基本操作及运算实验报告

1、数据结构与数据库实验报告实验主题二叉树的基本操作与运算一、需要分析问题说明：实现二叉树(包括二叉树)的构建，实现先序、中序、后序和分层扫描，修正叶节点数、树的深度、树的宽度，求出树的非空子孙节点数、度为2的节点数、度为2的节点数、二叉树的常用运算。问题分析：二叉树的树型结构是一种重要的非线性数据结构，其熟练掌握是学习数据结构的基本要求。 由于二叉树的定义本身就是递归定义，所以二叉树的一些基本操作也可以采用递归调用方法。 我认为，为了处理这个问题，应该如下考虑1 .做二叉树2 .用递归方法扫描二叉树(先序、中序和后序)3 .通过队列应用程序实现二叉树的分层遍历4、借用递归方法对二叉树进行一些基本

2、操作。 例如，求出叶数、树的深度宽度等5 .使用广义表对二叉树进行广义表形式的印刷。算法规定：输入形式：为了方便操作，二叉树的要素类型全部为文字类型，允许各种文字类型的输入，没有要素的节点用空格输入表示，本实验按顺序输入。输出形式：以先顺序、中顺序、后顺序扫描木材的各文字类型要素的方法扫描打印，以广义表形式打印。 对于二叉树的一些运算结果作为整数被输出。程序功能：实现二叉树的先顺序、中顺序、后顺序的遍历、层次的遍历。 修正叶节点数、树的深度、树的宽度，求出树的非空子孙节点数、度2的节点数、度2的节点数。 搜索具有二叉树的元素，删除具有二叉树的节点。输入测试数据： abcdegf(用表示空格)，

3、找到5，删除e预测结果：依次遍历abcdegf中正向扫描cbegdfa之后扫描cgefdba分层扫描abcdefg广义表印刷a(b(c，d(e，g，f ) ) )叶数3深5宽2非空子孙数6度2的数2度1的数2检索5，成功，检索的要素为e删除e后，以广义表形式打印a(b(c，d (，f ) )输入abdehcfg(用表示空格)，找到10，删除b预测结果：依次遍历abdehcfg中顺扫描dbheagfc之后扫描dhebgfca分层扫描abcdefhg广义表印刷a(b(d，e(h ) )，c(f (，g ) )叶数3深4宽3非空子孙数7度2的数2度1的数3无法检索10。删除b后，以广义表格形式打印a

4、 (，c(f (，g ) )二、概要设定修订程序包含二叉树和队列两种抽象数据类型。1 .设定“二叉树”的抽象数据类型定义：阿德特比树。数据对象d:d是具有相同特性的数据元素的集合。数据关系r :如果是的话，把bitree称为空二叉树如果是，h是以下二项关系(1)在d中存在被称为唯一根的数据要素root，在关系h下没有前体(2)存在且(3)中存在唯一的元素，并且存在上述关系，则中存在唯一的元素，并且存在上述关系(4)是符合本定义的二叉树，称为根的左子树，是符合本定义的二叉树，称为根的有字树基本操作：createbitreet )操作结果：按照t的定义构建二叉树。bitreedepth(t )初始

5、条件：二叉树t已经存在。操作结果：返回t的深度。比特宽度(t )初始条件：二叉树t已经存在。操作结果：返回t的宽度。preodertraverset )初始条件：二叉树t已经存在。操作结果：依次扫描印刷t，索引战争(t )初始条件：二叉树t已经存在。操作结果：中顺扫描印刷t。postodertraverse(t )初始条件：二叉树t已经存在。操作结果：依次扫描印刷t。级别追踪(t )初始条件：二叉树t已经存在。操作结果：层次遍历t。删除树(t，t元素x )初始条件：二叉树已存在。操作结果：删除要素x的节点及其左子树和右子树。复制树(t )初始条件：二叉树t已经存在。操作结果：以t为模板，复制另

6、一个二叉树。 adt bi树状结构2 .设置队列的抽象数据类型定义adt队列。数据对象： d=。数据关系： r1=|，i=2，n约定的一端是队列标头，另一端是队列的末尾。基本操作：初始队列(q )操作结果：创建空队列q。排队(q，e )初始条件：队列q已存在。操作结果：插入元素e为q的新队列元素。求逆(q )初始条件：队列q已存在。操作结果：删除q的开头要素，返回其值。队列实力(q )初始条件：队列q已存在。操作结果：如果q为空队列则返回1，否则返回0。 adt队列3 .本程序包括四个模块1 )主程序模块void主机()。初始化依次输入二叉树的各节点元素各种扫描二叉树进行二叉树中常见的运算复制

7、二叉树对复制的二叉树进行二叉树的常见操作是2 )二叉树模块实现二叉树的抽象数据类型和基本操作2 )队列模块实现队列的抽象数据类型和本次操作3 )广义表打印模块以广义表格式打印二叉树4 )二叉树运算模块二叉树的叶、非空子孙节点数、度2或1的节点数三、详细设定修订1 .主程序所需的全过程量要计算#define m 10 /二叉树的宽度，必须按数组存储每个层的宽度。 这个m表示数组的长度2 .队列创建和基本操作类型结构节点。二叉树数据； /队列中存储的元素类型结构节点*下一步； /指向二叉树节点的指针qnode、*queueptr；类型结构。伫列ptr前端； /队列的队列标头指针伫列前列； /队列的

8、队列结束指针链接队列；算法说明：应用于队列以分层扫描二叉树，因为“先接入的节点也必须先接入其子节点”。 相反，考虑到通过分层扫描进行队列操作的需要，只需检查队列初始化、入队和出队以及队列是否为空即可。伪码算法：发起队列(链路队列* q )初始化队列请求节点q-front=q-rear=(队列ptr )大小(正交(qnode ) )。国际货币基金组织正前方exit(1)； /存储分配失败处理q-front-next=空值； /构成起始节点上的空链列是链接队列* q、比特树插入元素以e为q的队列元素伫列ptr q；q=(队列ptr )大小(小节点) :国际货币基金组织问exit(1)；q数据=e；

9、q-next=空值；下一步=q； /元素e的节点输入问卷=q；是联系人队列(链接队列* q )从队列中删除队列标头元素，并直接返回调用的主函数队列ptr p；比特树q；if (正前方=正后方)队列为空打印机(错误！ n )；exit(1)；是p=q -前端下一个；q=对数据；q前下一个=p下一个。 /删除此节点国际货币基金组织q正面=q正面；自由(p )；返回q； /转到队列标头元素是英特尔队列实力(链路队列* q )检查队列是否为空，如果为空则返回真值，否则返回0if (正前方=正后方)返回1；埃尔斯返回0；是3 .二叉树的建立和基本操作类型结构位节点。电子数据； /存储在二叉树节点中的元素

10、类型结构位元*液晶、*液晶； 二叉树左右孩子的指针|比特节点，*比特树；算法分析：二叉树的基本操作是本程序的核心，二叉树的定义如果考虑采用递归定义，那么对二叉树的操作很容易通过递归调用来实现。1 )二叉树的扫描算法说明：在二叉树中，常常要求在树中寻找具有某些特征的节点，或者对树中的所有节点一个一个地进行某些处理，需要扫描二叉树。 也就是说，必须在一个路径中搜索树中的每个节点，以确保每个节点只被访问一次，只被访问一次。回顾二叉树的递归定义，可知二叉树由根节点、左子树、右子树三个基本单元构成。 因此，如果能够依次扫描这3个部分，就是扫描了整个二叉树。 表示分别在l、d、r上扫描左子树、访问根节点、

11、扫描右子树时，有dlr、ldr、lrd、drl、rdl、rld这6种扫描二叉树的方案。 从右向左限定，只有前3种情况，分别称为最初(根)顺序扫描。 中(根)顺序扫描和后(根)顺序扫描。 基于二叉树的递归定义，得到如下扫描二叉树的递归定义算法。依次遍历二叉树的操作定义二叉树如果是空的，空操作否则(1)访问根节点(2)首先依次扫描左子树(3)首先依次扫描右子树。伪码算法：语音预先验证(bi树t )采用/二叉链表的记忆结构国际足联。putchar(t-data )； /最简单的接入节点方法输出节点元素，在此首先接入根节点预演唱会(t-lchild )；预演唱会(t-rchild )；是是按中顺序扫描

12、二叉树的操作定义：二叉树如果是空的，空操作否则(1)按中顺序扫描左子树(2)访问根节点(3)依次扫描右侧子树。伪码算法：语音索引(bi树)采用/二叉链表的记忆结构国际足联。索引(t-lchild )； /首先遍历左子树putchar(t-data )； /最简单的访问节点法，输出节点元素，这里是第二个访问根节点索引(t-rchild )；是是后扫描二叉树的操作定义：二叉树如果是空的，空操作否则(1)扫描后序左子树(2)依次扫描右子树(3)访问根节点。伪码算法：void邮箱验证(bi树)采用/二叉链表的记忆结构国际足联。后现象(t-lchild )； /首先遍历左子树后现象(t-rchild )

13、； /重新扫描右子树putchar(t-data )； /最后访问根节点是是2 )二叉树的制作算法说明：在对二叉树的“扫描”基本操作已经建立的基础上，可以在方便的过程中对节点进行各种各样的操作。 例如，在扫描过程中生成节点，建立二叉树的记忆结构。要使用第一次扫描创建二叉树链表，请执行以下步骤(1)依次输入二叉树结点的要素，在换行符输入之前用空格表示空格(2)如果元素值为空，则代入null，除此之外，生成新的节点，向该节点的数值字段分配元素值(3)创建此到达节点的左侧子树(4)创建该根节点的右子树。伪码算法双树创建树(双树t )构筑二叉树t，依次输入二叉树中的节点值(1个字符)，空白表示空树查尔斯；if(ch=getchar()=)t=空值；埃尔斯电视接口！=n )。国际货币基金组织(t=(二叉树)大小(比特) )exit(1)；t数