数据结构实验报告六—BST(二叉查找树)实现动态查找表

数据结构实验报告班级：信息与计算科学专业1102班学号： 1108060214姓名：朱晓东设计日期：2013.6.6西安科技大学计算机学院1.实验报告编写一个演示运用二叉排序树进行数据的的排序、插入、删除、查找等操作的程序。

2.需求分析本演示程序用vc6.0编写，完成数据的排序功能，同时能够进行数据的创建、插入、删除、查找。

（1）输入的形式和输入值的范围：创建二叉排序树时输入较多的值；插入元素时需要输入插入的元素的值；删除元素时输入元素的值；查找操作时需要输入元素的值。

所有输入中，元素的值都是整数。

（2）输出的形式：在创建、插入、删除的操作后，均显示操作后的元素的排序状况，有小到大排序。

（3）程序所能达到的功能：完成二叉排序树的生成、插入、删除、查找操作。

（4）测试数据：①插入操作中依次输入10 9 11 8 12 0（本程序是以0元素为为结束标志）；②查找操作中输入13；③插入操作中输入13；3概要设计本程序包含8个函数：（1）主函数main()（2）创建二叉排序树函数BSTCreate(BiTree* bt)（3）显示操作菜单函数menu()（4）显示二叉排序树的内容函数BSTShow(BiTree bt)（5）插入元素函数BSTInsert(BiTree* bt,DataType key)（6）删除元素函数BSTDelete(BiTree* bt,DataType key)（7）查找元素函数BSTSearch(BiTree bt,DataType key)（8）查找要删除的元素的函数DeleteNode(BiTree* bt)各函数之间的关系如下：BSTCreate(BiTree* bt)menu()BSTShow(BiTree bt)mainBSTInsert(BiTree* bt,DataType key)BSTDelete(BiTree* bt,DataType key) DeleteNode(BiTree* bt)BSTSearch(BiTree bt,DataType key)4.详细设计实现概要设计中定义的所有数据类型，对每个操作给出伪码算法。

查找-动态查找表-⼆叉排序树⽂字描述 ⼆叉排序树的定义 ⼜称⼆叉查找树，英⽂名为Binary Sort Tree, 简称BST。

它是这样⼀棵树：或者是⼀棵空树；或者是具有下列性质的⼆叉树：(1)若它的左⼦树不空，则左⼦树上所有结点的值均⼩于它的根结点的值；(2)若它的右⼦树不空，则右⼦树上所有结点的值均⼤于它的根结点的值；(3)它的左、右⼦树也分别是⼆叉排序树。

⼆叉排序树的查找 其查找过程和次优⼆叉树类似。

即当⼆叉排序树不为空时，⾸先将给定值和根结点的关键字⽐较，若相等，则查找成功，否则将依据给定值和根结点的关键字之间的⼤⼩关系，分别在左⼦树或右⼦树上继续进⾏查找。

⼆叉排序树的插⼊ 和次优查找树相对，次优查找树是⼀种静态查找表。

⽽⼆叉排序树是⼀种动态树表，其特点是，树的结构通常不是⼀次⽣成的，⽽是在查找过程中，当树中不存在关键字等于给定值的结点时再进⾏插⼊。

新插⼊的结点⼀定是⼀个新添加的叶⼦结点，并且是查找不成功时查找路径上访问的最后⼀个结点的左孩⼦或右孩⼦结点。

⼆叉排序树的删除 在⼆叉排序树上删除⼀个结点相当于删除有序序列中的⼀个纪录，只要在删除某个结点之后依旧保持⼆叉排序树的特性即可。

假设被删除结点*p(指向结点的指针为p)，其双亲结点*f(结点类型为f)，且不失⼀般性，可设*p是*f的左孩⼦。

下⾯分3种情况进⾏讨论： (1)若*p结点为叶⼦结点，即PL和PR均为空树。

由于删除叶⼦结点*p不破坏整棵树的结构，则只需修改其双亲结点的指针即可。

(2)若*p结点只有左⼦树PL或只有右⼦树PR，此书只要令PL或PR直接成为其双亲结点*f的左⼦树即可。

(3)若*p结点的左⼦树和右⼦树均不为空。

从下图知，在删除*p之前，中序遍历该⼆叉树的序列为{…C L C…Q L QS L SPP R F…}, 在删除*p 之后，为保持其他元素之间的相对位置不变，可以有两种⽅法：[3.1]令*p的左⼦树为*f的左⼦树，⽽*p的右⼦树为*s的右⼦树。

二叉排序树的实验报告二叉排序树的实验报告引言：二叉排序树（Binary Search Tree，简称BST）是一种常用的数据结构，它将数据按照一定的规则组织起来，便于快速的查找、插入和删除操作。

本次实验旨在深入了解二叉排序树的原理和实现，并通过实验验证其性能和效果。

一、实验背景二叉排序树是一种二叉树，其中每个节点的值大于其左子树的所有节点的值，小于其右子树的所有节点的值。

这种特性使得在二叉排序树中进行查找操作时，可以通过比较节点的值来确定查找的方向，从而提高查找效率。

二、实验目的1. 理解二叉排序树的基本原理和性质；2. 掌握二叉排序树的构建、插入和删除操作；3. 验证二叉排序树在查找、插入和删除等操作中的性能和效果。

三、实验过程1. 构建二叉排序树首先，我们需要构建一个空的二叉排序树。

在构建过程中，我们可以选择一个节点作为根节点，并将其他节点插入到树中。

插入节点时，根据节点的值与当前节点的值进行比较，如果小于当前节点的值，则将其插入到当前节点的左子树中；如果大于当前节点的值，则将其插入到当前节点的右子树中。

重复这个过程，直到所有节点都被插入到树中。

2. 插入节点在已有的二叉排序树中插入新的节点时，我们需要遵循一定的规则。

首先，从根节点开始，将新节点的值与当前节点的值进行比较。

如果小于当前节点的值，则将其插入到当前节点的左子树中；如果大于当前节点的值，则将其插入到当前节点的右子树中。

如果新节点的值与当前节点的值相等，则不进行插入操作。

3. 删除节点在二叉排序树中删除节点时，我们需要考虑不同的情况。

如果要删除的节点是叶子节点，即没有左右子树，我们可以直接删除该节点。

如果要删除的节点只有一个子树，我们可以将子树连接到要删除节点的父节点上。

如果要删除的节点有两个子树，我们可以选择将其右子树中的最小节点或左子树中的最大节点替代该节点，并删除相应的替代节点。

四、实验结果通过对二叉排序树的构建、插入和删除操作的实验，我们得到了以下结果：1. 二叉排序树可以高效地进行查找操作。

HUNAN UNIVERSITY课程预习报告题目：BST学生XX学生学号201208专业班级指导老师完成日期一、需求分析（1）输入的形式和输入值的X围：建表的输入：第一次输入一个正整数N，代表接下来要输入的结点值的个数。

以后输入N个整数，分别代表N个结点的值，中间用空格隔开。

输入格式为：“34 76 45 18 26 54 92 65”。

查询的输入：输入一个整数，代表需要在表中查询的值。

不对非法输入做处理，即假设输入都是合法的。

（2）输出的形式：对于需要查询的数，如果存在表中则输出“查找成功”并输出比较的次数，如果不存在表中，则输出“查找不成功，已插入表中”。

（3）程序所能达到的功能：本程序可以创建一个动态查找链表，可以对用户输入的数据进行查询，输出查询数据过程中的比较次数，对于不存在的数据还可以动态插入到正确的位置。

（4）测试数据：输入：8//BST的节点个数34, 76, 45, 18, 26, 54, 92, 65 //8个数据45//查找45输出：查找成功 3 //返回成功和查找时比较的次数34//查找34输出：查找成功 1 //返回成功和查找时比较的次数100//查找100输出：查找不成功 3 //返回成功和查找时比较的次数二、概要设计抽象数据类型对于一个具有插入和查询功能的动态查询表，可以使用顺序表和链表来实现，但是在这个查找问题中，顺序表不够链表方便，我们需要插入和检索的时间效率更高，因此选择使用二叉查找树（BST）来实现这个动态查询表。

查询表中的数据类型作为BST的结点，所以需要定义一个结点类来实现数据及其关系的存储。

结点类的ADT如下：数据类型：D=(a1,a2…ai|aiЄZ)基本操作：int val() //返回结点的数值inline Node* left()const //获取左结点inline Node* right()const //获取右结点void setLeft(Node* it) //设置左结点void setRight(Node* it) //设置右结点BST的ADT如下：数据对象：Node类型数据关系：二叉树基本操作：bool insert(const int& it) //插入元素bool find(int& it,int& count) //查找元素算法的基本思想对于用户输入的n的值来确定表中所应该有的结点个数，将结点依次输入，按照BST树的要求，每个结点的左子树的所有结点值都比该结点值小，右子树的所有结点值都比该结点值大，查询时，将用户输入的元素进行查找操作，从根结点依次比较，若该元素存在并输出比较的次数，若不存在则输出提示语句。

数据结构二叉树的实验报告数据结构二叉树的实验报告一、引言数据结构是计算机科学中非常重要的一个领域，它研究如何组织和存储数据以便高效地访问和操作。

二叉树是数据结构中常见且重要的一种，它具有良好的灵活性和高效性，被广泛应用于各种领域。

本实验旨在通过实际操作和观察，深入了解二叉树的特性和应用。

二、实验目的1. 理解二叉树的基本概念和特性；2. 掌握二叉树的创建、遍历和查找等基本操作；3. 通过实验验证二叉树的性能和效果。

三、实验过程1. 二叉树的创建在实验中，我们首先需要创建一个二叉树。

通过输入一系列数据，我们可以按照特定的规则构建一棵二叉树。

例如，可以按照从小到大或从大到小的顺序将数据插入到二叉树中，以保证树的有序性。

2. 二叉树的遍历二叉树的遍历是指按照一定的次序访问二叉树中的所有节点。

常见的遍历方式有前序遍历、中序遍历和后序遍历。

前序遍历是先访问根节点，然后再依次遍历左子树和右子树；中序遍历是先遍历左子树，然后访问根节点，最后再遍历右子树；后序遍历是先遍历左子树，然后遍历右子树，最后访问根节点。

3. 二叉树的查找二叉树的查找是指在二叉树中寻找指定的节点。

常见的查找方式有深度优先搜索和广度优先搜索。

深度优先搜索是从根节点开始，沿着左子树一直向下搜索，直到找到目标节点或者到达叶子节点；广度优先搜索是从根节点开始，逐层遍历二叉树，直到找到目标节点或者遍历完所有节点。

四、实验结果通过实验，我们可以观察到二叉树的特性和性能。

在创建二叉树时，如果按照有序的方式插入数据，可以得到一棵平衡二叉树，其查找效率较高。

而如果按照无序的方式插入数据，可能得到一棵不平衡的二叉树，其查找效率较低。

在遍历二叉树时，不同的遍历方式会得到不同的结果。

前序遍历可以用于复制一棵二叉树，中序遍历可以用于对二叉树进行排序，后序遍历可以用于释放二叉树的内存。

在查找二叉树时，深度优先搜索和广度优先搜索各有优劣。

深度优先搜索在空间复杂度上较低，但可能会陷入死循环；广度优先搜索在时间复杂度上较低，但需要较大的空间开销。

问题描述利用二叉查找树（BST）实现一个动态查找表基本要求（1）使用二叉树（BST）来实现。

（2）二叉树使用链式结构（二叉链表）实现。

（3）实现BST的构建，查找两个功能。

一需求分析1.输入的形式：输入要存储元素的个数n （正整数），n个元素的值（设为整数）和要查找元素的值；2.输出的形式：输出是否找到（查找成功\不成功）和查找时比较的次数（正整数）：3.程序所能达到的功能：要求输入用户设定个元素，再输入要查找的元素，输出是否找到和查找时比较的次数；4.测试数据输入：5//BST的节点数请输入数据：43 54 32 12 57 //五个数据请输入查找数：54 //查找54输岀：查找成功2 //返回成功和查找时比较的次数请输入查找数：12 //查找12输出：查找成功3 //返回成功和查找吋比较的次数请输入查找的数：50 //查找50输出：杏找不成功3 //返回成功和查找时比较的次数二概要设计抽象数据类型的定义BST,二叉查找树，先定义一个二叉树节点，然后实现二叉查找树的功能。

数据对象：整数数据关系：数裾元素属于同一集合，是二叉树，如果对其做屮序遍历呈递增序列基本操作：遍历，二叉树的构建，查找，插入算法的基本思想将输入的BST的元素川插入的方法存进BST巾（由于BST中任何结点的左孩子小于该节点，右孩子大于该节点，所以用递归方法比较插入）。

判断输入要查找的元素是否在BST中（递归比较要查找的元素与当前元素的值的大小，若小于当前值，则查找其左子树；若大于，则查找其右子树），若在，则输出位罝；若不在，则插入到BST中，并输出其位罝程序的流程:程序由三个模块组成：（1）输人模块：输入二叉查找树的元素个数、元素的值，以及要查找的数（2）查找模块：判断该元素是否在二叉查找树中，若未找到，则插入到二叉查找树中。

（3）输出模块：输出是否找到。

若找到，则输出位置；若未找到，则输出插入的位置。

三详细设计(1)物理数据类型因为要实现一个动态杏找表，对一个数进行查找，用线性表实现所用的时间代价比较高，而用二叉查找表来实现的话时间代价显剧较低，故可以构建一个二叉查找树，来实现动态查找。

HUNAN UNIVERSITY实验报告题目： BST学生姓名李湃学生学号专业班级指导老师完成日期2012/4/29一、需求分析（1）利用二叉查找数（BST）实现一个动态查找表（2）输入格式:n //BST的节点个数//n个数据m //要查找的数据输出格式查找成功x //返回成功和查找时比较的次数查找不成功x //返回成功和查找时比较的次数（3）测试数据：输入：8//BST的节点个数34, 76, 45, 18, 26, 54, 92, 65 //8个数据45//查找45输出：查找成功 3 //返回成功和查找时比较的次数34//查找34输出：查找成功 1 //返回成功和查找时比较的次数100//查找100输出：查找不成功 3 //返回成功和查找时比较的次数二、概要设计抽象数据类型数据对象：查找表中元素为整数数据关系：满足二叉树所要求的基本关系。

另外，每个节点如果有左子树，则左子树中任意元素小于该节点值，如果有右子树，则右子树中任意元素大于该节点值基本操作：BST的部分基本操作，包括初始化二叉树、初始化节点，插入节点、查找和销毁等操作。

算法的基本思想根据题目要求，用二叉查找树来实现动态查找表。

插入元素e时，先判断该二叉树是否为空，若为空，将e作为该二叉树的根节点。

否则，从根节点开始，比较e与节点n 的大小。

如果e的值更小，判断n的左子树是否为空，若为空，将e作为节点n的左孩子并返回e，否则比较e与n左孩子的值，依此循环下去；如果e的值更大，判断n的右子树是否为空，若为空，将e作为节点n的右孩子并返回e，否则比较e与n右孩子的值，依此循环下去。

查找元素的算法与插入算法大同小异，从根节点开始，比较e与节点n的大小，若相等，返回True；如果e比节点n的值小，判断n的左子树是否为空，若为空，返回False，不为空则比较e与n左孩子的值，依次循环下去；如果e比节点n的值大，判断n的右子树是否为空，若为空，返回False，不为空则比较e与n右孩子的值，依次循环下去。

数据结构实验报告—二叉树数据结构实验报告—二叉树引言二叉树是一种常用的数据结构，它由节点和边构成，每个节点最多有两个子节点。

在本次实验中，我们将对二叉树的基本结构和基本操作进行实现和测试，并深入了解它的特性和应用。

实验目的1. 掌握二叉树的基本概念和特性2. 熟练掌握二叉树的基本操作，包括创建、遍历和查找等3. 了解二叉树在实际应用中的使用场景实验内容1. 二叉树的定义和存储结构：我们将首先学习二叉树的定义，并实现二叉树的存储结构，包括节点的定义和节点指针的表示方法。

2. 二叉树的创建和初始化：我们将实现二叉树的创建和初始化操作，以便后续操作和测试使用。

3. 二叉树的遍历：我们将实现二叉树的前序、中序和后序遍历算法，并测试其正确性和效率。

4. 二叉树的查找：我们将实现二叉树的查找操作，包括查找节点和查找最大值、最小值等。

5. 二叉树的应用：我们将探讨二叉树在实际应用中的使用场景，如哈夫曼编码、二叉搜索树等。

二叉树的定义和存储结构二叉树是一种特殊的树形结构，它的每个节点最多有两个子节点。

节点被表示为一个由数据和指向其左右子节点的指针组成的结构。

二叉树可以分为三类：满二叉树、完全二叉树和非完全二叉树。

二叉树可以用链式存储结构或顺序存储结构表示。

- 链式存储结构：采用节点定义和指针表示法，通过将节点起来形成一个树状结构来表示二叉树。

- 顺序存储结构：采用数组存储节点信息，通过计算节点在数组中的位置来进行访问和操作。

二叉树的创建和初始化二叉树的创建和初始化是二叉树操作中的基础部分。

我们可以通过手动输入或读取外部文件中的数据来创建二叉树。

对于链式存储结构，我们需要自定义节点和指针，并通过节点的方式来构建二叉树。

对于顺序存储结构，我们需要定义数组和索引，通过索引计算来定位节点的位置。

一般来说，初始化一个二叉树可以使用以下步骤：1. 创建树根节点，并赋初值。

2. 创建子节点，并到父节点。

3. 重复步骤2，直到创建完整个二叉树。

实习报告一、需求分析1、问题描述利用平衡二叉树实现一个动态查找表。

（1）实现动态查找表的三种基本功能：查找、插入和删除。

（2）初始时，平衡二叉树为空树，操作界面给出查找、插入和删除三种操作供选择。

每种操作均要提示输入关键字。

在查找时，如果查找的关键字不存在，则把其插入到平衡二叉树中。

每次插入或删除一个结点后，应更新平衡二叉树的显示。

（3）每次操作的关键字都要从文件中读取，并且关键字的集合限定为短整型数字{1，2，3······}，关键字出现的顺序没有限制，允许出现重复的关键字，并对其进行相应的提示。

（4）平衡二叉树的显示采用图形界面画出图形。

2、系统功能打开数据文件，用文件中的关键字来演示平衡二叉树操作的过程。

3、程序中执行的命令包括：（1）(L)oad from data file //在平衡的二叉树中插入关键字；（2）(A)ppend new record //在平衡的二叉树中查找关键字；（3）(U)pate special record //显示调整过的平衡二叉树；（4）(D)elete special record //删除平衡二叉树中的关键字；（5）(Q)uit //结束。

4、测试数据：平衡二叉树为：图 1 插入关键字10之前的平衡二叉树插入关键字：10；调整后：图 2 插入关键字10之后的平衡二叉树删除关键字：14；调整后：图 3 删除关键字14后的平衡二叉树查找关键字：11；输出：The data is here!图 3 查找关键字11后的平衡二叉树二、概要设计本次实验目的是为了实现动态查找表的三种基本功能：查找、插入和删除。

动态查找表可有不同的表示方法，在此次实验中主要是以平衡二叉树的结构来表示实现的，所以需要两个抽象数据类型：动态查找表和二叉树。

1、动态查找表的抽象数据类型定义为：ADT DynamicSearchTable{数据对象D ：D是具有相同特性的数据元素的集合。

HUNAN UNIVERSITY 课程实验报告题目：BST的构建与查找学生姓名：学生学号：专业班级：指导老师：李晓鸿老师完成日期：2014年11月22号一．需求分析输入形式在该程序中，用户需要输入节点个数和节点数据以及查找的节点，节点数据间使用空格隔开，当用户输入有误时提示用户输入错误并重新输入。

具体格式如下：请输入节点个数：请依次节点数据：请输入需查找的节点：输出形式若用户需查找的节点查找成功，则输出查找成功以及比较的次数，若查找不成功则输入查找失败，具体格式如下：查找成功，比较次数为__查找失败, 比较次数为__程序功能该程序可以通过使用二叉链表构建一个BST，并实现BST内节点的插入和查找功能测试数据1.请输入节点个数：8请依次节点数据：12,4,35,78,56,34,89,0请输入需查找的节点：89查找成功，比较次数为32.请输入节点个数：8请依次节点数据：12,4,35,78,56,34,89,0请输入需查找的节点：678查找失败，比较次数为33．请输入节点个数：c输入有误请重新输入4. 请输入节点个数：8请依次节点数据：12,4,35,78,56,&,89.3,A输入有误，请重新输入二．概要设计抽象数据类型1.在本程序中，需要对插入的节点进行检索，而BST的插入和检索的速率都是很高的，所以我们选用构建BST的方法来解决这项问题；2.由用户输入的节点个数及节点数据均为正整数，可使用整型数据进行存储，并构建一个BST存储这些节点数据；3.为了节约空间，使用二叉链表实现BST；4.为了能查询表中数据，定义一个二叉树节点类，其ADT设计如下：数据类型：整型数据数据关系：二叉树所对应的数据关系基本操作：int val() ; //返回结点的数值void setLeft(Node* ) ; //设置左结点void setRight(Node* ); //设置右结点Node* left()const; //返回左结点Node* right()const ;//返回右结点4.为了存储这些数据，构建一个二叉查找树，其ADT设计如下：数据类型：整型数据数据关系:二叉树所对应的数据关系基本操作：void clear();//初始化操作bool insert（const Elem&）;//插入元素的操作bool find(const Elem&)const;//查找元素的操作算法基本思想该算法主要包括表的构建和查询两项：①在表的构建上，通过用户输入的数据，将第一个输入的节点数据存入根节点中，从第二个节点元素开始，与根节点数据进行比较，如果该元素大于根节点的值，则与根节点的右子节点相比较，若右子节点为空，则将该元素存入这个节点，若不为空，则将该右子节点视为根节点，重复上述步骤。

实验5：树（二叉树）（采用二叉链表存储）一、实验项目名称二叉树及其应用二、实验目的熟悉二叉树的存储结构的特性以及二叉树的基本操作。

三、实验基本原理之前我们都是学习的线性结构，这次我们就开始学习非线性结构——树。

线性结构中结点间具有唯一前驱、唯一后继关系，而非线性结构中结点的前驱、后继的关系并不具有唯一性。

在树结构中，节点间关系是前驱唯一而后继不唯一，即结点之间是一对多的关系。

直观地看，树结构是具有分支关系的结构（其分叉、分层的特征类似于自然界中的树）。

四、主要仪器设备及耗材Window 11、Dev-C++5.11五、实验步骤1.导入库和预定义2.创建二叉树3.前序遍历4.中序遍历5.后序遍历6.总结点数7.叶子节点数8.树的深度9.树根到叶子的最长路径10.交换所有节点的左右子女11.顺序存储12.显示顺序存储13.测试函数和主函数对二叉树的每一个操作写测试函数，然后在主函数用while+switch-case的方式实现一个带菜单的简易测试程序，代码见“实验完整代码”。

实验完整代码：#include <bits/stdc++.h>using namespace std;#define MAX_TREE_SIZE 100typedef char ElemType;ElemType SqBiTree[MAX_TREE_SIZE];struct BiTNode{ElemType data;BiTNode *l,*r;}*T;void createBiTree(BiTNode *&T){ElemType e;e = getchar();if(e == '\n')return;else if(e == ' ')T = NULL;else{if(!(T = (BiTNode *)malloc(sizeof (BiTNode)))){cout << "内存分配错误!" << endl;exit(0);}T->data = e;createBiTree(T->l);createBiTree(T->r);}}void createBiTree2(BiTNode *T,int u) {if(T){SqBiTree[u] = T->data;createBiTree2(T->l,2 * u + 1);createBiTree2(T->r,2 * u + 2); }}void outputBiTree2(int n){int cnt = 0;for(int i = 0;cnt <= n;i++){cout << SqBiTree[i];if(SqBiTree[i] != ' ')cnt ++;}cout << endl;}void preOrderTraverse(BiTNode *T) {if(T){cout << T->data;preOrderTraverse(T->l);preOrderTraverse(T->r);}}void inOrderTraverse(BiTNode *T) {if(T){inOrderTraverse(T->l);cout << T->data;inOrderTraverse(T->r);}}void beOrderTraverse(BiTNode *T){if(T){beOrderTraverse(T->l);beOrderTraverse(T->r);cout << T->data;}}int sumOfVer(BiTNode *T){if(!T)return 0;return sumOfVer(T->l) + sumOfVer(T->r) + 1;}int sumOfLeaf(BiTNode *T){if(!T)return 0;if(T->l == NULL && T->r == NULL)return 1;return sumOfLeaf(T->l) + sumOfLeaf(T->r);}int depth(BiTNode *T){if(!T)return 0;return max(depth(T->l),depth(T->r)) + 1;}bool LongestPath(int dist,int dist2,vector<ElemType> &ne,BiTNode *T) {if(!T)return false;if(dist2 == dist)return true;if(LongestPath(dist,dist2 + 1,ne,T->l)){ne.push_back(T->l->data);return true;}else if(LongestPath(dist,dist2 + 1,ne,T->r)){ne.push_back(T->r->data);return true;}return false;}void swapVer(BiTNode *&T){if(T){swapVer(T->l);swapVer(T->r);BiTNode *tmp = T->l;T->l = T->r;T->r = tmp;}}//以下是测试程序void test1(){getchar();cout << "请以先序次序输入二叉树结点的值，空结点用空格表示:" << endl; createBiTree(T);cout << "二叉树创建成功!" << endl;}void test2(){cout << "二叉树的前序遍历为:" << endl;preOrderTraverse(T);cout << endl;}void test3(){cout << "二叉树的中序遍历为:" << endl;inOrderTraverse(T);cout << endl;}void test4(){cout << "二叉树的后序遍历为:" << endl;beOrderTraverse(T);cout << endl;}void test5(){cout << "二叉树的总结点数为：" << sumOfVer(T) << endl;}void test6(){cout << "二叉树的叶子结点数为：" << sumOfLeaf(T) << endl; }void test7(){cout << "二叉树的深度为：" << depth(T) << endl;}void test8(){int dist = depth(T);vector<ElemType> ne;cout << "树根到叶子的最长路径:" << endl;LongestPath(dist,1,ne,T);ne.push_back(T->data);reverse(ne.begin(),ne.end());cout << ne[0];for(int i = 1;i < ne.size();i++)cout << "->" << ne[i];cout << endl;}void test9(){swapVer(T);cout << "操作成功!" << endl;}void test10(){memset(SqBiTree,' ',sizeof SqBiTree);createBiTree2(T,0);cout << "操作成功!" << endl;}void test11(){int n = sumOfVer(T);outputBiTree2(n);}int main(){int op = 0;while(op != 12){cout << "-----------------menu--------------------" << endl;cout << "--------------1：创建二叉树--------------" << endl;cout << "--------------2：前序遍历----------------" << endl;cout << "--------------3：中序遍历----------------" << endl;cout << "--------------4：后序遍历----------------" << endl;cout << "--------------5：总结点数----------------" << endl;cout << "--------------6：叶子节点数--------------" << endl;cout << "--------------7：树的深度----------------" << endl;cout << "--------------8：树根到叶子的最长路径----" << endl;cout << "--------------9：交换所有节点左右子女----" << endl;cout << "--------------10：顺序存储---------------" << endl;cout << "--------------11：显示顺序存储-----------" << endl;cout << "--------------12：退出测试程序-----------" << endl;cout << "请输入指令编号:" << endl;if(!(cin >> op)){cin.clear();cin.ignore(INT_MAX,'\n');cout << "请输入整数!" << endl;continue;}switch(op){case 1:test1();break;case 2:test2();break;case 3:test3();break;case 4:test4();break;case 5:test5();break;case 6:test6();break;case 7:test7();break;case 8:test8();break;case 9:test9();break;case 10:test10();break;case 11:test11();break;case 12:cout << "测试结束!" << endl;break;default:cout << "请输入正确的指令编号!" << endl;}}return 0;}六、实验数据及处理结果测试用例：1.创建二叉树（二叉链表形式）2.前序遍历3.中序遍历4.后序遍历5.总结点数6.叶子结点数7.树的深度8.树根到叶子的最长路径9.交换所有左右子女10.顺序存储七、思考讨论题或体会或对改进实验的建议通过这次实验，我掌握了二叉树的顺序存储和链式存储，体会了二叉树的存储结构的特性，掌握了二叉树的树上相关操作。

一、实验目的1. 理解树的概念及其在计算机科学中的应用。

2. 掌握几种常见树的查找方法，如二叉查找树、平衡树等。

3. 分析不同查找方法的效率，比较其优缺点。

4. 提高编程能力，巩固数据结构知识。

二、实验内容1. 二叉查找树（Binary Search Tree，BST）2. 平衡树（AVL树）3. 堆（Heap）三、实验环境1. 操作系统：Windows 102. 编程语言：Python3.73. 开发环境：PyCharm四、实验步骤1. 创建二叉查找树```pythonclass TreeNode:def __init__(self, val):self.val = valself.left = Noneself.right = Nonedef insert(root, val):if root is None:return TreeNode(val)if val < root.val:root.left = insert(root.left, val) else:root.right = insert(root.right, val) return rootdef inorder_traversal(root):if root:inorder_traversal(root.left)print(root.val, end=' ')inorder_traversal(root.right)# 创建二叉查找树root = Nonevalues = [8, 3, 10, 1, 6, 14, 4, 7, 13]for value in values:root = insert(root, value)print("二叉查找树的中序遍历：")inorder_traversal(root)```2. 创建平衡树（AVL树）```pythonclass AVLNode:def __init__(self, val):self.val = valself.left = Noneself.right = Noneself.height = 1def get_height(node):if not node:return 0return node.heightdef get_balance(node):if not node:return 0return get_height(node.left) - get_height(node.right)def right_rotate(y):x = y.leftT2 = x.rightx.right = yy.left = T2y.height = 1 + max(get_height(y.left), get_height(y.right)) x.height = 1 + max(get_height(x.left), get_height(x.right)) return xdef left_rotate(x):y = x.rightT2 = y.lefty.left = xx.right = T2x.height = 1 + max(get_height(x.left), get_height(x.right))y.height = 1 + max(get_height(y.left), get_height(y.right))return ydef insert(root, val):if not root:return AVLNode(val)if val < root.val:root.left = insert(root.left, val)else:root.right = insert(root.right, val)root.height = 1 + max(get_height(root.left), get_height(root.right)) balance = get_balance(root)if balance > 1 and val < root.left.val:return right_rotate(root)if balance < -1 and val > root.right.val:return left_rotate(root)if balance > 1 and val > root.left.val:root.left = left_rotate(root.left)return right_rotate(root)if balance < -1 and val < root.right.val:root.right = right_rotate(root.right)return left_rotate(root)return root# 创建平衡树root = Nonevalues = [8, 3, 10, 1, 6, 14, 4, 7, 13]for value in values:root = insert(root, value)print("平衡树的中序遍历：")inorder_traversal(root)```3. 创建堆（Heap）```pythondef heapify(arr, n, i):largest = il = 2 i + 1r = 2 i + 2if l < n and arr[i] < arr[l]:largest = lif r < n and arr[largest] < arr[r]:largest = rif largest != i:arr[i], arr[largest] = arr[largest], arr[i] heapify(arr, n, largest)def build_heap(arr):n = len(arr)for i in range(n // 2 - 1, -1, -1):heapify(arr, n, i)def extract_max(arr):n = len(arr)max_val = arr[0]arr[0] = arr[n - 1]n -= 1heapify(arr, n, 0)return max_val# 创建堆values = [8, 3, 10, 1, 6, 14, 4, 7, 13]heap = values.copy()build_heap(heap)print("堆的中序遍历：")inorder_traversal(heap)```五、实验结果与分析1. 二叉查找树：在插入过程中，树会保持有序，查找效率较高，但可能会出现不平衡的情况。

湖南⼤学数据结构BST的实现和插⼊HUNAN UNIVERSITY 课程实习报告题⽬： BST的实现和插⼊学⽣姓名学⽣学号专业班级指导⽼师李晓鸿完成⽇期问题描述利⽤⼆叉查找树（BST）实现⼀个动态查找表。

基本要求(1)使⽤⼆叉树（BST）来实现。

(2)⼆叉树使⽤链式结构（⼆叉链表）实现。

(3)实现BST的构建，查找两个功能。

实现提⽰输⼊：8//BST的节点个数34, 76, 45, 18, 26, 54, 92, 65 //8个数据45//查找 45输出：查找成功 3 //返回成功和查找时⽐较的次数34//查找 34输出：查找成功 1 //返回成功和查找时⽐较的次数100//查找 100输出：查找不成功 3 //返回成功和查找时⽐较的次数⼀、需求分析⼆叉排序树⼜称⼆叉查找树其定义为：⼆叉排序树或者是空树，或者是满⾜如下性质的⼆叉树：①若它的左⼦树⾮空，则左⼦树上所有结点的值均⼩于根结点的值；②若它的右⼦树⾮空，则右⼦树上所有结点的值均⼤于根结点的值；③左、右⼦树本⾝⼜各是⼀棵⼆叉排序树。

上述性质简称⼆叉排序树性质(BST性质)，故⼆叉排序树实际上是满⾜BST性质的⼆叉树。

1.输⼊的形式和输⼊值的范围：初始化时需要输⼊初始化时输⼊的数据个数，以及这⼀组需要输⼊的数据。

由于BST的性质，数据为关键码（即可以⽐较⼤⼩），为简单起见，均设为整数类型，查找时需要输⼊被查找的数据对象，也为整数类型2.输出的形式：查找时如果在存储的数据中查找到被查找的数据，需要显⽰查找成功，并显⽰查找时⽐较的次数，如果查找不成功，也需要显⽰查找不成功，并输出查找时⽐较的次数。

3.功能:建⽴存储数据的结构，初始化时将输⼊的数据存储，在查找时能够在存储的数据中进⾏搜索以寻找被查找的数据，并进⾏相关显⽰。

并且对于输⼊的不符合规范的数据个数与被查找数据要求能报错。

4.测试数据输⼊：8//BST的节点个数34, 76, 45, 18, 26, 54, 92, 65 //8个数据45//查找45输出：查找成功，查找了3次//返回成功和查找时⽐较的次数34//查找34输出：查找成功，查找了1次//返回成功和查找时⽐较的次数100//查找100输出：查找不成功查找了3次//返回成功和查找时⽐较的次数⼆、概要设计1.抽象数据类型由于BST的特殊性，需要⽐⼤⼩，于是需要关键码，这⾥选取整数作为关键码（1）ADT BinNode数据对象：D={ai|ai数据关系：R1={|ai-1,ai基本操作：int val() //返回结点的数值Void setVal（const Elem&）//设置节点的值inline BinNode* left()const //获取左结点inline BinNode* right()const //获取右结点void setLeft(Node* it) //设置左结点void setRight(Node* it) //设置右结点Bool isLeaf（）//是叶⼦节点吗（2）ADT BST数据对象BinNode数据关系⼆叉查找树基本操作searchTree(Node* subroot,int data)//执⾏查找基本操作的函数需要⼀个数据作为被查找的数据，查找成功，或失败进⾏相关显⽰，输出⽐较次数。

HUNAN UNIVERSITY课程实习报告题目： BST实现动态查找表学生姓名：学生学号：专业班级：指导老师：李晓鸿完成日期： 2015 11 21一、需求分析1、程序任务：本程序是利用二叉查找树（BST）来实现；二叉树使用链式结构（二叉链表）实现，本程序要实现BST的构建，查找BST树中元素中两个功能。

2、输入形式：输入整数n//BST的节点个数n。

输入n个数，其取值范围为（0，216），对非法输入做处理。

3、输出形式：若查找成功整数m（次数）//返回成功和查找时比较的次数若查找不成功整数m（次数） //返回不成功和查找时比较的次数若输入错误“输入了无效的元素”4、测试数据：①.正常的输入10 //BST的节点个数50 1 3 2 78 65 100 59 43 18 //10个数据输入：50输出：查找成功,查找次数1输入：1输出：查找成功，查找次数6输入：3输出：查找成功，查找次数4输入：100输出：查找成功，查找次数5输入：19输出：查找失败②．只有左子树的情况10 //BST的节点个数100 1 12 35 43 95 54 82 78 93 //10个数据输入：1输出：查找成功,查找次数1输入：12输出：查找成功，查找次数6输入：35输出：查找成功，查找次数4输入：95输出：查找成功，查找次数5输入：19输出：查找失败③．错误的节点数输入-2 //BST的节点个数输出：错误的结点数输入④．错误的结点值的输入（字母）10 //BST的结点个数1 q23456789 //10个数据输出：无效的结点输入⑤．错误的结点值的输入（负数）10 //BST的结点个数1 -2 23456789 //10个数据输出：无效的结点输入二叉树中任意结点的值大于左节点的值，小于右节点的值，满足BST树的性质，所以用BST树来实现。

二．概要设计1.抽象数据类型二叉树中任意结点的值大于左节点的值，小于右节点的值，满足BST树的性质，同时本题在建树时需要大量的插入操作，运用链式结构比较方便，所以用链式结构的二叉树来满足BST树的构建。