数据结构实验：二叉搜索树与表达式树的实现与应用

# 数据结构实验：二叉搜索树与表达式树的实现与应用 ## 1. 二叉搜索树操作 ### 1.1 输出小于指定键的键 在二叉搜索树中，有时需要输出所有小于指定键的键。可以使用如下函数实现： ```cpp void writeLessThan ( KF searchKey ) const ``` 该函数的要求是无，结果是按升序输出二叉搜索树中小于 `searchKey` 的键，且 `searchKey` 不必是树中的键。 为了提高效率，避免搜索不可能包含小于 `searchKey` 的键的子树。例如，给定搜索键 37 和根节点键为 43 的二叉搜索树，可直接确定无需搜索根节点的右子树。 **操作步骤**： 1. 实现该操作并添加到 `bstree.cpp` 文件中，`bstree.h` 文件的 `BSTree` 类声明中包含了该操作的原型。 2. 通过移除 `test11.cpp` 文件中以 “//<” 开头的行的注释分隔符（和字符 ‘<’），激活测试程序中的 “<”（小于）命令。 3. 准备测试计划，包括各种树和 `searchKey` 值，如限制搜索到根节点左子树、根节点左子树和部分右子树、树中最左分支以及整棵树的测试用例。 4. 执行测试计划，若发现 `writeLessThan` 操作实现有误，修正后再次执行测试计划。 ### 1.2 二叉搜索树高度问题 对于由 N 个不同键构成的二叉搜索树，最短和最高的树的高度是多少？可以通过具体例子来说明。 ### 1.3 最短二叉搜索树操作时间复杂度分析 给定包含 N 个不同键的最短可能二叉搜索树，对以下二叉搜索树 ADT 操作的最坏情况执行时间进行数量级估计，并简要说明推理过程。 | 操作 | 时间复杂度 | 解释 | | ---- | ---- | ---- | | retrieve | O( ) | | | insert | O( ) | | | remove | O( ) | | | writeKeys | O( ) | | ## 2. 表达式树 ADT ### 2.1 表达式树概述 通常以线性形式书写算术表达式，但在求值时将其视为层次结构。例如，对于表达式 `(1 + 3) * (6 - 4)`，先计算 `1 + 3` 和 `6 - 4`，再将结果相乘。可以用二叉树表示这种层次结构，即表达式树。 ### 2.2 表达式树 ADT 数据项与结构 - **数据项**：表达式树的每个节点包含算术运算符或数值。 - **结构**：节点构成树，包含算术运算符的节点有一对子节点，每个子节点是表示运算符操作数的子树的根节点；包含数值的节点没有子节点。 ### 2.3 表达式树 ADT 操作 | 操作 | 要求 | 结果 | | ---- | ---- | ---- | | ExprTree () | 无 | 构造函数，创建空表达式树 | | ~ExprTree () | 无 | 析构函数，释放存储表达式树的内存 | | void build () throw ( bad_alloc ) | 无 | 从键盘读取前缀形式的算术表达式并构建相应的表达式树 | | void expression () const | 无 | 以完全括号化的中缀形式输出相应的算术表达式 | | float evaluate () const throw ( logic_error ) | 表达式树非空 | 返回相应算术表达式的值 | | void clear () | 无 | 移除表达式树中的所有数据项 | | void showStructure () const | 无 | 输出表达式树，其分支从左（根）到右（叶）定向，即树逆时针旋转 90 度输出；若树为空，输出 “Empty tree”，此操作用于测试/调试，假设算术表达式仅包含一位非负整数和加减乘除运算符 | ### 2.4 从前缀表达式构建表达式树 通常以中缀形式书写算术表达式，但在本实验中从前缀形式构建表达式树。例如，中缀表达式 `(1 + 3) * (6 - 4)` 的前缀形式为 `* + 1 3 - 6 4`。 构建过程如下： 1. 读取下一个算术运算符或数值。 2. 创建包含该运算符或数值的节点。 3. 若节点包含运算符，则递归构建对应操作数的子树；否则，该节点为叶节点。 ### 2.5 表达式树操作实现 使用递归函数实现表达式树 ADT 的操作，假设算术表达式由一位非负整数（‘0’..‘9’）和四个基本算术运算符（‘+’，‘-’，‘*’，‘/’）组成，且每个算术表达式以一行前缀形式从键盘输入。 **操作步骤**： 1. 使用链表树结构实现表达式树 ADT，基于 `exprtree.hs` 文件的声明，`show12.cpp` 文件中给出了 `showStructure` 操作的实现。 ```cpp class ExprTree; // Forward declaration of the ExprTree class class ExprTreeNode // Facilitator class for the ExprTree class { private: // Constructor ExprTreeNode ( char elem, ExprTreeNode *leftPtr, ExprTreeNode *rightPtr ); // Data members char dataItem; // Expression tree data item ExprTreeNode *left, // Pointer to the left child *right; // Pointer to the right child friend class ExprTree; }; class ExprTree { public: // Constructor ExprTree (); // Destructor ~ExprTree (); // Expression tree manipulation operations void build () // Build tree from prefix expression throw ( bad_alloc ); void expression () const; // Output expression in infix form float evaluate () const // Evaluate expression throw ( logic_error ); void clear (); // Clear tree // Output the tree structure -- used in testing/debugging void showStructure () const; private: // Recursive partners of the public member functions -- insert // prototypes of these functions here. ```