山东大学计科院实验十一：二叉搜索树操作与实现

本篇文档是山东大学计算机科学与技术学院2017级学生李港在2019年12月5日进行的实验十一——二叉搜索树的相关报告。实验主要目标是深入理解和掌握二叉搜索树（BST）的基本概念，包括其结构定义、描述方法和关键操作实现。 实验内容主要围绕以下几个方面展开： 1. 数据结构设计：创建了一个带索引的二叉搜索树类，使用链表作为存储结构。这个类支持插入、删除、按名次删除、查找、按名次查找和升序输出等操作。通过键盘录入整数，并将它们组织成二叉搜索树的形式，同时输出树的高度。 2. 操作实现：插入操作之外，报告描述了其他操作的执行过程。查找操作涉及比较元素的过程，需要理解如何在二叉搜索树中进行逐层比较，利用二叉搜索树的特性优化查找效率。按名次查找则利用节点结构体中的"left_size"成员，减少查询的时间复杂度。 3. 算法描述：整体思路是基于二叉搜索树的性质，即左子树小于根节点，右子树大于等于根节点，升序输出可以通过前序遍历实现。计算树的高度则采用了之前学习的二叉树实验中常用的数组法。 4. 代码实现：设计了节点类模板`node`，包含数据成员`data`、`left_size`（表示节点在树中的位置）、`left`和`right`（分别指向左子树和右子树的指针）。提供了空构造函数和带子节点的构造函数，确保节点的初始化。 通过这次实验，学生不仅锻炼了编程技能，还深化了对二叉搜索树理论的理解，学会了如何高效地在实际场景中应用这些数据结构和算法。