二叉树的基本操作
- 格式：doc
- 大小：96.50 KB
- 文档页数：11
下载文档原格式
合集下载
二叉树的基本操作
二叉树的基本操作二叉树是一种常见的数据结构，它由节点组成，每个节点最多有两个子节点。
二叉树在计算机领域中得到广泛应用，它的基本操作包括插入、删除、查找、遍历等。
1.插入操作：二叉树的插入操作是将一个新的节点添加到已有的二叉树中的过程。
插入操作会按照一定规则将新节点放置在正确的位置上。
插入操作的具体步骤如下：-首先，从根节点开始，比较新节点的值与当前节点的值的大小关系。
-如果新节点的值小于当前节点的值，则将新节点插入到当前节点的左子树中。
-如果新节点的值大于当前节点的值，则将新节点插入到当前节点的右子树中。
-如果当前节点的左子树或右子树为空，则直接将新节点插入到该位置上。
-如果当前节点的左子树和右子树都不为空，则递归地对左子树或右子树进行插入操作。
2.删除操作：二叉树的删除操作是将指定节点从二叉树中删除的过程。
删除操作有以下几种情况需要考虑：-如果待删除节点是叶子节点，则直接将其从二叉树中删除即可。
-如果待删除节点只有一个子节点，则将其子节点替换为待删除节点的位置即可。
-如果待删除节点有两个子节点，则需要找到其左子树或右子树中的最大节点或最小节点，将其值替换为待删除节点的值，然后再删除最大节点或最小节点。
3.查找操作：二叉树的查找操作是在二叉树中查找指定值的节点的过程。
查找操作的具体步骤如下：-从根节点开始，将待查找值与当前节点的值进行比较。
-如果待查找值等于当前节点的值，则返回该节点。
-如果待查找值小于当前节点的值，则在当前节点的左子树中继续查找。
-如果待查找值大于当前节点的值，则在当前节点的右子树中继续查找。
-如果左子树或右子树为空，则说明在二叉树中找不到该值。
4.遍历操作：二叉树的遍历操作是按照一定规则依次访问二叉树中的每个节点。
有三种常用的遍历方式：- 前序遍历（Preorder Traversal）：先访问根节点，然后递归地前序遍历左子树和右子树。
- 中序遍历（Inorder Traversal）：先递归地中序遍历左子树，然后访问根节点，最后递归地中序遍历右子树。
二叉树的基本操作课件浙教版(2019)高中信息技术选修1(24张PPT)
如下图所示的是二叉树及其对应的二叉链表实现示意图。
A
B
D
C
E
F
G
头指针
二叉树的list实现
二叉树节点可以看成是一个三元组，元素是左、右子树和本节点数据。
Python的list可以用于组合这样的三个元素。
下面介绍用list构造二叉树的方法。
（1）空树用None表示。
（2）非空二叉树用包含三个元素的列表[d,l,r]表示，其中：d表示根节点的元素，l和r是两棵子树，采用与整个二叉树同样结构的list表示。
二叉树的遍历
在完成二叉树的建立操作后，就可以对二叉树的各个节点进行访问，即遍历操作。二叉树的遍历，是指按照一定的规则和次序访问二叉树中的所有节点，使得每个节点都被访问一次且仅被访问一次。按照不同的遍历方式对节点进行访问，其处理效率不完全相同。二叉树的遍历方式有很多，主要有前序遍历、中序遍历和后序遍历等。
1.数组实现
用数组来表示二叉树时，分为以下两种情况。
（1）完全二叉树从二叉树的根节点开始，按从上而下、自左向右的顺序对n个节点进行编号，根节点的编号为0，最后一个节点的编号为n-1。然后依次将二叉树的节点用一组连续的数组元素来表示，节点编号与数组的下标一一对应。如下图中图甲所示的完全二叉树所对应的一维数组表示如图乙所示。
A
B
C
A
B
C
甲 原二叉树
乙 补全后的二叉树
0
1
2
3
4
5
6
7
丙 数组实现示意图
A
B
C
对于完全二叉树而言，一维数组的表示方式既简单又节省存储空间。但对于一般的二叉树来说，采用一维数组表示时，结构虽然简单，却容易造成存储空间的浪费。
A
B
D
C
E
F
G
头指针
二叉树的list实现
二叉树节点可以看成是一个三元组，元素是左、右子树和本节点数据。
Python的list可以用于组合这样的三个元素。
下面介绍用list构造二叉树的方法。
（1）空树用None表示。
（2）非空二叉树用包含三个元素的列表[d,l,r]表示，其中：d表示根节点的元素，l和r是两棵子树，采用与整个二叉树同样结构的list表示。
二叉树的遍历
在完成二叉树的建立操作后，就可以对二叉树的各个节点进行访问，即遍历操作。二叉树的遍历，是指按照一定的规则和次序访问二叉树中的所有节点，使得每个节点都被访问一次且仅被访问一次。按照不同的遍历方式对节点进行访问，其处理效率不完全相同。二叉树的遍历方式有很多，主要有前序遍历、中序遍历和后序遍历等。
1.数组实现
用数组来表示二叉树时，分为以下两种情况。
（1）完全二叉树从二叉树的根节点开始，按从上而下、自左向右的顺序对n个节点进行编号，根节点的编号为0，最后一个节点的编号为n-1。然后依次将二叉树的节点用一组连续的数组元素来表示，节点编号与数组的下标一一对应。如下图中图甲所示的完全二叉树所对应的一维数组表示如图乙所示。
A
B
C
A
B
C
甲 原二叉树
乙 补全后的二叉树
0
1
2
3
4
5
6
7
丙 数组实现示意图
A
B
C
对于完全二叉树而言，一维数组的表示方式既简单又节省存储空间。但对于一般的二叉树来说，采用一维数组表示时，结构虽然简单，却容易造成存储空间的浪费。
二叉树的建立与基本操作
二叉树的建立与基本操作二叉树是一种特殊的树形结构，它由节点（node）组成，每个节点最多有两个子节点。
二叉树的基本操作包括建立二叉树、遍历二叉树、查找二叉树节点、插入和删除节点等。
本文将详细介绍二叉树的建立和基本操作，并给出相应的代码示例。
一、建立二叉树建立二叉树有多种方法，包括使用数组、链表和前序、中序、后序遍历等。
下面以使用链表的方式来建立二叉树为例。
1.定义二叉树节点类首先，定义一个二叉树节点的类，包含节点值、左子节点和右子节点三个属性。
```pythonclass Node:def __init__(self, value):self.value = valueself.left = Noneself.right = None```2.建立二叉树使用递归的方法来建立二叉树，先构造根节点，然后递归地构造左子树和右子树。
```pythondef build_binary_tree(lst):if not lst: # 如果 lst 为空，则返回 Nonereturn Nonemid = len(lst) // 2 # 取 lst 的中间元素作为根节点的值root = Node(lst[mid])root.left = build_binary_tree(lst[:mid]) # 递归构造左子树root.right = build_binary_tree(lst[mid+1:]) # 递归构造右子树return root```下面是建立二叉树的示例代码：```pythonlst = [1, 2, 3, 4, 5, 6, 7]root = build_binary_tree(lst)```二、遍历二叉树遍历二叉树是指按照其中一规则访问二叉树的所有节点，常见的遍历方式有前序遍历、中序遍历和后序遍历。
1.前序遍历前序遍历是指先访问根节点，然后访问左子节点，最后访问右子节点。
```pythondef pre_order_traversal(root):if root:print(root.value) # 先访问根节点pre_order_traversal(root.left) # 递归访问左子树pre_order_traversal(root.right) # 递归访问右子树```2.中序遍历中序遍历是指先访问左子节点，然后访问根节点，最后访问右子节点。
二叉树的顺序存储及基本操作
二叉树的顺序存储及基本操作二叉树的顺序存储是将树中的节点按照完全二叉树从上到下、从左到右的顺序依次存储到一个一维数组中，采用这种方式存储的二叉树也被称为完全二叉树。
一、在使用顺序存储方式时，可以使用以下公式来计算一个节点的左右子节点和父节点：
1. 左子节点：2i+1（i为父节点的在数组中的下标）
2. 右子节点：2i+2
3. 父节点：(i-1)/2（i为子节点在数组中的下标）
二、基本操作：
1. 创建二叉树：按照上述公式将节点存储到数组中。
2. 遍历二叉树：可采用递归或非递归方式，进行前序、中序、后序、层次遍历。
3. 插入节点：先将节点插入到数组末尾，然后通过比较节点和其父节点的大小，进行上浮操作直到满足二叉树的性质。
4. 删除节点：先将待删除节点和最后一个节点交换位置，然后通过比较交换后的节点和其父节点的大小，进行下沉操作直到满足二
叉树的性质。
5. 查找节点：根据节点值进行查找，可采用递归或非递归方式。
6. 修改节点：根据节点值进行查找，然后进行修改操作。
二叉树的各种基本运算的实现实验报告
二叉树的各种基本运算的实现实验报告
一、实验目的
实验目的为了深入学习二叉树的各种基本运算，通过操作实现二叉树的建立、存储、查找、删除、遍历等各种基本运算操作。
二、实验内容
1、构造一个二叉树。
我们首先用一定的节点来构建一棵二叉树，包括节点的左子节点和右子节点。
2、实现查找二叉树中的节点。
在查找二叉树中的节点时，我们根据二叉树的特点，从根节点开始查找，根据要查找的节点的值与根节点的值的大小的关系，来决定接下来查找的方向，直到找到要查找的节点为止。
3、实现删除二叉树中的节点。
在删除二叉树节点时，我们要做的是找到要删除节点的父节点，然后让父节点的链接指向要删除节点的子节点，有可能要删除节点有一个子节点，有可能有两个极点，有可能没有子节点，我们要根据每种情况进行处理，来保持二叉树的结构不变。
4、对二叉树进行遍历操作。
二叉树的遍历有多种方法，本实验使用的是先序遍历。
首先从根节点出发，根据先序遍历的顺序，先访问左子树，然后再访问右子树，最后访问根节点。
三、实验步骤
1、构建二叉树：
我们用一个数组代表要构建的二叉树，第一项为根节点，第二项和第三项是根节点的子节点。
数据结构实验三——二叉树基本操作及运算实验报告
《数据结构与数据库》实验报告实验题目二叉树的基本操作及运算一、需要分析问题描述：实现二叉树（包括二叉排序树）的建立，并实现先序、中序、后序和按层次遍历，计算叶子结点数、树的深度、树的宽度，求树的非空子孙结点个数、度为2的结点数目、度为2的结点数目，以及二叉树常用运算。
问题分析：二叉树树型结构是一类重要的非线性数据结构，对它的熟练掌握是学习数据结构的基本要求。
由于二叉树的定义本身就是一种递归定义，所以二叉树的一些基本操作也可采用递归调用的方法。
处理本问题，我觉得应该：1、建立二叉树；2、通过递归方法来遍历（先序、中序和后序）二叉树；3、通过队列应用来实现对二叉树的层次遍历；4、借用递归方法对二叉树进行一些基本操作，如：求叶子数、树的深度宽度等；5、运用广义表对二叉树进行广义表形式的打印。
算法规定：输入形式：为了方便操作，规定二叉树的元素类型都为字符型，允许各种字符类型的输入，没有元素的结点以空格输入表示，并且本实验是以先序顺序输入的。
输出形式：通过先序、中序和后序遍历的方法对树的各字符型元素进行遍历打印，再以广义表形式进行打印。
对二叉树的一些运算结果以整型输出。
程序功能：实现对二叉树的先序、中序和后序遍历，层次遍历。
计算叶子结点数、树的深度、树的宽度，求树的非空子孙结点个数、度为2的结点数目、度为2的结点数目。
对二叉树的某个元素进行查找，对二叉树的某个结点进行删除。
测试数据：输入一：ABC□□DE□G□□F□□□（以□表示空格）,查找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）））输入二：ABD□□EH□□□CF□G□□□（以□表示空格）,查找10,删除B预测结果：先序遍历ABDEHCFG中序遍历DBHEAGFC后序遍历DHEBGFCA层次遍历ABCDEFHG广义表打印A（B(D,E(H)),C(F(,G))）叶子数3 深度4 宽度3 非空子孙数7 度为2的数目2 度为1的数目3查找10，失败。
二叉树实验报告
二叉树实验报告1. 引言二叉树是一种常用的数据结构，广泛应用于计算机科学和信息技术领域。
本实验旨在通过对二叉树的理解和实现，加深对数据结构与算法的认识和应用能力。
本报告将介绍二叉树的定义、基本操作以及实验过程中的设计和实现。
2. 二叉树的定义二叉树是一个有序树，其每个节点最多有两个子节点。
树的左子节点和右子节点被称为二叉树的左子树和右子树。
3. 二叉树的基本操作3.1 二叉树的创建在实验中，我们通过定义一个二叉树的节点结构来创建一个二叉树。
节点结构包含一个数据域和左右指针，用于指向左右子节点。
创建二叉树的过程可以通过递归或者迭代的方式来完成。
3.2 二叉树的插入和删除二叉树的插入操作是将新节点插入到树中的合适位置。
插入时需要考虑保持二叉树的有序性。
删除操作是将指定节点从树中删除，并保持二叉树的有序性。
在实验中，我们可以使用递归或者循环的方式实现这些操作。
3.3 二叉树的遍历二叉树的遍历是指按照某种次序访问二叉树的所有节点。
常见的遍历方式包括前序遍历、中序遍历和后序遍历。
前序遍历先访问根节点，然后按照左孩子-右孩子的顺序递归遍历左右子树。
中序遍历按照左孩子-根节点-右孩子的顺序递归遍历左右子树。
后序遍历按照左孩子-右孩子-根节点的顺序递归遍历左右子树。
3.4 二叉树的查找查找操作是指在二叉树中查找指定的值。
可以通过递归或者循环的方式实现二叉树的查找操作。
基本思路是从根节点开始，通过比较节点的值和目标值的大小关系，逐步向左子树或者右子树进行查找，直到找到目标节点或者遍历到叶子节点。
4. 实验设计和实现在本实验中，我们设计并实现了一个基于Python语言的二叉树类。
具体实现包括二叉树的创建、插入、删除、遍历和查找操作。
在实验过程中，我们运用了递归和迭代的方法实现了这些操作，并进行了测试和验证。
4.1 二叉树类的设计我们将二叉树的节点设计为一个类，其中包括数据域和左右子节点的指针。
另外，我们设计了一个二叉树类，包含了二叉树的基本操作方法。
二叉树实验知识点总结
二叉树实验知识点总结
一、二叉树的基本概念
二叉树是一种特殊的树形结构，其每个节点最多只有两个子节点。
二叉树分为满二叉树、完全二叉树和普通二叉树等类型。
二、遍历方式
1.前序遍历：先访问当前节点，再遍历左子树和右子树；
2.中序遍历：先遍历左子树，再访问当前节点，最后遍历右子树；
3.后序遍历：先遍历左子树和右子树，最后访问当前节点；
4.层次遍历：按照从上到下、从左到右的顺序依次访问每个节点。
三、常见操作
1.插入节点：在二叉搜索树中插入一个新的节点；
2.删除节点：在二叉搜索树中删除一个指定的节点；
3.查找节点：在二叉搜索树中查找一个指定的节点；
4.求深度：计算二叉搜索树的深度。
四、平衡二叉树
平衡二叉树是一种特殊的二叉搜索树，其左右子树高度差不能超过1。
常见的平衡二叉搜索包括红黑树、AVL 树等。
五、应用场景
1.数据库索引；
2.哈夫曼编码；
3.表达式求值；
4.图形处理等。
六、注意事项
1.二叉树的插入、删除和查找操作需要保证二叉树的结构不被破坏；
2.平衡二叉树的实现需要注意平衡因子的计算和旋转操作的实现；
3.在使用二叉树进行算法设计时，需要考虑遍历方式和时间复杂度等问题。
七、总结
二叉树是一种重要的数据结构，在算法设计中有广泛的应用。
掌握二叉树的基本概念、遍历方式、常见操作和应用场景，可以帮助我们更好地理解和使用这种数据结构。
同时，我们需要注意在实际应用中遵循相关规范，保证程序的正确性和效率。
二叉树的基本操作与实现实验报告
二叉树的基本操作与实现实验报告二叉树是一种重要的数据结构，在计算机科学领域中被广泛应用。
本实验将介绍二叉树的基本操作与实现，并给出相应的实验报告。
一、引言二叉树是一种特殊的树状结构，每个节点至多有两个子节点。
二叉树有许多重要的特性，如平衡二叉树、二叉树等，应用广泛。
在本实验中，我们将介绍二叉树的基本操作和实现。
二、实验目的1.掌握二叉树的基本概念和特性；2.熟悉二叉树的基本操作，包括创建、插入、删除、遍历等；3.学会使用编程语言实现二叉树的基本操作。
三、实验内容本实验主要包括以下内容：1.二叉树的定义和基本概念；2.二叉树的基本操作，包括创建、插入、删除、遍历等；3.使用编程语言实现二叉树的基本操作；4.测试和验证二叉树的基本操作的正确性。
四、实验步骤1.二叉树的定义和基本概念二叉树是一种树状结构，每个节点至多有两个子节点。
二叉树的每个节点包含一个数据项和指向左子树和右子树的指针。
二叉树的特性有很多，如完全二叉树、平衡二叉树、二叉树等。
2.二叉树的基本操作（1）创建二叉树：可以通过手动输入节点数据来创建二叉树，也可以通过读取文件中的数据来创建二叉树。
（2）插入节点：在指定位置插入一个新节点。
（3）删除节点：删除指定位置的节点。
（4）遍历二叉树：有前序遍历、中序遍历和后序遍历三种遍历方式。
3.使用编程语言实现二叉树的基本操作实现二叉树的基本操作可以使用编程语言来完成。
我们可以定义一个二叉树的结构体，包含节点数据和指向左右子树的指针。
然后根据具体的需求，实现相应的操作函数。
4.测试和验证二叉树的基本操作的正确性在完成二叉树的基本操作后，我们可以编写测试代码来验证操作的正确性。
通过创建二叉树，并进行插入、删除和遍历操作，观察输出结果是否符合预期。
五、实验结果与分析在完成二叉树的基本操作后，我们可以进行测试和验证。
通过输出二叉树的遍历结果，比对预期结果来判断操作是否正确。
同时，我们还可以观察二叉树的结构和特性，如是否满足平衡二叉树或二叉树的条件。
二叉树的基本操作实验报告
二叉树的基本操作实验报告二叉树的基本操作实验报告引言：二叉树是一种常见的数据结构，它由节点组成，每个节点最多有两个子节点。
二叉树的基本操作包括创建、遍历、插入和删除等。
本实验旨在通过实践来深入了解二叉树的基本操作，并通过实验结果验证其正确性和有效性。
一、创建二叉树创建二叉树是二叉树操作中的第一步。
在本实验中，我们使用了递归算法来创建二叉树。
递归算法是一种重要的算法思想，通过将问题划分为更小的子问题来解决复杂的问题。
在创建二叉树时，我们首先创建根节点，然后递归地创建左子树和右子树。
二、遍历二叉树遍历二叉树是对二叉树中的每个节点进行访问的过程。
常见的遍历方式有前序遍历、中序遍历和后序遍历。
前序遍历先访问根节点，然后递归遍历左子树和右子树；中序遍历先递归遍历左子树，然后访问根节点，最后递归遍历右子树；后序遍历先递归遍历左子树和右子树，最后访问根节点。
三、插入节点插入节点是向二叉树中添加新节点的操作。
插入节点的过程需要遵循二叉树的特性，即左子节点的值小于父节点的值，右子节点的值大于父节点的值。
在插入节点时，我们需要找到合适的位置，将新节点插入到正确的位置上。
四、删除节点删除节点是从二叉树中移除节点的操作。
删除节点的过程相对复杂，需要考虑多种情况。
如果要删除的节点是叶子节点，直接删除即可。
如果要删除的节点只有一个子节点，将其子节点连接到父节点上。
如果要删除的节点有两个子节点，我们需要找到其后继节点或前驱节点来替代被删除的节点。
实验结果：通过实验，我们成功地实现了二叉树的基本操作。
创建二叉树的递归算法能够正确地创建出符合要求的二叉树。
遍历二叉树的算法能够按照指定的顺序遍历每个节点。
插入节点和删除节点的操作也能够正确地修改二叉树的结构。
讨论与总结：二叉树的基本操作是数据结构中的重要内容，对于理解和应用其他数据结构具有重要意义。
通过本次实验，我们深入了解了二叉树的创建、遍历、插入和删除等操作，并通过实验验证了其正确性和有效性。
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
浙江大学城市学院实验报告课程名称数据结构基础实验项目名称实验十二叉树的基本操作学生姓名吴奇专业班级信管1204 学号31201403实验成绩指导老师（签名）日期一.实验目的和要求1、掌握二叉树的链式存储结构。
2、掌握在二叉链表上的二叉树操作的实现原理与方法。
3、进一步掌握递归算法的设计方法。
二.实验内容1、按照下面二叉树二叉链表的存储表示，编写头文件binary_tree.h，实现二叉链表的定义与基本操作实现函数；编写主函数文件test4_1.cpp，验证头文件中各个操作。
二叉树二叉链表存储表示如下：struct BTreeNode {ElemType data; // 结点值域BTreeNode *lchild , *rchild ; // 定义左右孩子指针} ;基本操作如下：①void InitBTree( BTreeNode *&BT );//初始化二叉树BT②void CreateBTree( BTreeNode *&BT, char *a );//根据字符串a所给出的广义表表示的二叉树建立二叉链表存储结构③int EmptyBTree( BTreeNode *BT);//检查二叉树BT是否为空，空返回1，否则返回0④int DepthBTree( BTreeNode *BT);//求二叉树BT的深度并返回该值⑤int FindBTree( BTreeNode *BT, ElemType x);//查找二叉树BT中值为x的结点，若查找成功返回1，否则返回0⑥void PreOrder( BTreeNode *BT);//先序遍历二叉树BT⑦void InOrder( BTreeNode *BT);//中序遍历二叉树BT⑧void PostOrder( BTreeNode *BT);//后序遍历二叉树BT⑨void PrintBTree( BTreeNode *BT );//输出二叉树BT⑩void ClearBTree( BTreeNode *&BT );//清除二叉树BT2、选做：实现以下说明的操作函数，要求把函数添加到头文件binary_tree.h 中，并在主函数文件test4_1.cpp中添加相应语句进行测试。
①void LevelOrder( BTreeNode *BT )//二叉树的层序遍历②int Get_Sub_Depth( BTreeNode *T , ElemType x)//求二叉树中以元素值为x的结点为根的子树的深度3、填写实验报告，实验报告文件取名为report10.doc。
4、上传实验报告文件report10.doc、源程序文件test4_1.cpp及binary_tree.h 到Ftp服务器上自己的文件夹下。
三. 函数的功能说明及算法思路struct BtreeNode{elemtype data; //结点值域BtreeNode *lchild; //定义左孩子指针BtreeNode *rchild; //定义右孩子指针};struct lnode{ //定义队列结点结构用于二叉树层遍历BtreeNode *data1;lnode *next;};struct Queue{ //定义队列首尾指针lnode *front;lnode *back;};void initQueue(Queue &Q) //初始化队列{Q.front=Q.back=NULL;}void insertQueue(Queue &Q,BtreeNode *item) //元素入队列{lnode *newptr=new lnode;newptr->data1=item;newptr->next=NULL;if(Q.back==NULL)Q.front=Q.back=newptr;elseQ.back=Q.back->next=newptr;}BtreeNode *deleteQueue(Queue &Q) //队首元素出队列{BtreeNode *temp=Q.front->data1;lnode *p=Q.front;Q.front=p->next;if(Q.front==NULL)Q.back=NULL;delete p;return temp;}bool emptyQueue(Queue Q) //判断队列是否为空{return Q.front==NULL;}void initBtree(BtreeNode *&BT) //二叉树的初始化{BT=NULL;}void insertBtree(BtreeNode *&BT) //创建二叉树{elemtype ch;ch=getchar();if(ch=='$') //判断是不是结束标志BT=NULL;else{BT=new BtreeNode; //创建结点BT->data=ch; //赋值insertBtree(BT->lchild); //左子叶递归insertBtree(BT->rchild); //右子叶递归}}bool emptyBtree(BtreeNode *BT) //判断二叉树是否为空{return BT==NULL;}int depthBtree(BtreeNode *BT) //求二叉树的深度{if(emptyBtree(BT))return 0;else{int dep1=depthBtree(BT->lchild); //左子叶递归int dep2=depthBtree(BT->rchild); //右子叶递归return dep1>dep2?dep1+1:dep2+1; //判断哪个子叶的深度最大//树的深度为左右子叶的最大深度加上1 }}void preorder(BtreeNode *BT) //前序遍历{if(!emptyBtree(BT)){cout<<BT->data<<" "; //输出结点值preorder(BT->lchild); //左子叶递归preorder(BT->rchild); //右子叶递归}}void midorder(BtreeNode *BT) //中序遍历{if(!emptyBtree(BT)){midorder(BT->lchild); //左子叶递归cout<<BT->data<<" "; //输出结点值midorder(BT->rchild); //右子叶递归}}void laterorder(BtreeNode *BT) //后序遍历{if(!emptyBtree(BT)){laterorder(BT->lchild); //左子叶递归laterorder(BT->rchild); //右子叶递归cout<<BT->data<<" "; //输出结点值}}bool findBtree(BtreeNode *BT,elemtype x) //查找二叉树中结点元素为x值的结点{if(emptyBtree(BT)) //空树，返回falsereturn false;else{if(BT->data==x) //找到，返回truereturn true;else{if(findBtree(BT->lchild,x)) //左子叶递归查找return true;if(findBtree(BT->rchild,x)) //右子叶递归查找return true;return false;}}}void levelorder(BtreeNode *BT) //按层遍历二叉树{Queue queue; //用于存放二叉树结点的队列initQueue(queue);BtreeNode *P;if(!emptyBtree(BT)) //二叉树不为空，根节点入队insertQueue(queue,BT);while(!emptyQueue(queue)){ //当队列不为空时，队首元素出队列P=deleteQueue(queue);cout<<P->data<<" "; //输出出队元素值if(P->lchild!=NULL) //当左右子叶不为空时，递归insertQueue(queue,P->lchild);if(P->rchild!=NULL)insertQueue(queue,P->rchild);}}int Get_Sub_Depth(BtreeNode *BT,elemtype x)//求二叉树中以元素值为x的结点为根的子树的深度{int m,n;if(!emptyBtree(BT)){ //二叉树非空if(BT->data==x) //找到，返回其深度return depthBtree(BT);else{m=Get_Sub_Depth(BT->lchild,x); //左右子叶递归，返回深度n=Get_Sub_Depth(BT->rchild,x);return m>n?m:n;}}elsereturn 0;}void printBtree(BtreeNode *BT,int n) //打印二叉树{int i;if(emptyBtree(BT)) //二叉树为空，返回return;printBtree(BT->rchild,n+1); //先递归输出右子树for(i=0;i<n;i++)cout<<" "; //前导空格，表示层次cout<<"---";cout<<BT->data; //结点的值cout<<endl;printBtree(BT->lchild,n+1); //再递归输出右子树}void PrintBtree(BtreeNode *BT) //二叉树的广义表打印{if(!emptyBtree(BT)){cout<<BT->data;if(!emptyBtree(BT->lchild)||!emptyBtree(BT->rchild)){cout<<"(";PrintBtree(BT->lchild);if(!emptyBtree(BT->rchild))cout<<",";PrintBtree(BT->rchild);cout<<")";}}}四. 实验结果与分析五.心得体会通过这次实验，我掌握了二叉树的基本操作，对非线性储存结构有了一定的了解，相对于之前的线性储存结构来说，非线性储存结构确实是比较抽象、困难的，在接下来的时间里，要好好对非线性储存结构了解一番。