在 BST 中实现前向迭代器

为二叉搜索树 (BST) 开发前向迭代器需要开发一个类，该类允许以特定顺序（通常是升序）遍历树。迭代器需要能够从 BST 中最小的元素遍历到最大的元素。

1. 了解二叉搜索树

二叉搜索树是一种分层数据结构，它存储数据，以便能够快速查找、添加和删除项目。

主要思想

• 每个节点存储一个键（如整数）和额外的数据。
• 节点按层次结构组织，任何节点左侧的键都小于该节点的键，右侧的键都大于该节点的键。
• 查找某个键是否存在非常快——可以根据每个节点的比较快速遍历树。
• 添加和删除节点也依赖于遍历期间的比较，以在层次结构中找到正确的插入或删除位置。

2. 节点和树结构

以下是二叉搜索树 (BST) 中节点和树结构的解释

节点

• 树中存储数据的基本构建块。
• 每个节点包含
• 键：用于排序数据的唯一标识符（例如整数）。
• 值：实际存储的数据。
• 左：指向左子节点的指针。
• 右：指向右子节点的指针。
• 父：指向父节点的指针。

树结构

• 根节点：根节点是树中最高的节点。
• 子节点：直接连接在另一个节点下方的节点。
• 叶节点：最底层没有子节点的节点。
• 边：一个节点与另一个节点之间的连接。
• 路径：从一个节点到另一个节点的一系列边。
• 高度：从根节点到最底层节点的边数。
• 深度：从一个节点到根节点的边数
• 层：从根节点开始计数的层数（从 0 开始）

具有父节点左右子节点之间键比较的分层结构可实现快速排序、插入和删除。目标是在二叉搜索树上实现具有以下功能的前向迭代器。

curr()

二叉搜索树 (BST) 实现中的 curr() 函数用于访问遍历期间当前指向的节点。

具体来说

• 它返回一个指向 BST 节点的指针，该节点被认为是遍历正在检查的“当前”节点。
• 它允许调用者根据需要轻松访问此当前节点中存储的键、值和其他数据。

关于 curr(): 需要注意的几点

• 它通常在循环内部重复调用，遍历 BST 以访问每个节点。
• 它通常通过在每次迭代时调用 next() 来迭代，以更新指向序列中下一个节点的指针。
• curr() 返回的指针通常在每次循环迭代时进行本地缓存，而不是多次调用 curr()。
• 检查 curr() 是否返回 null 是检测遍历是否已到达树末尾的常用方法。

next()

二叉搜索树 (BST) 实现中的 next() 函数用于在遍历期间迭代树，根据遍历顺序的规则将当前节点更新为序列中的下一个节点。

具体来说，next() 执行以下关键操作

• 根据遍历排序规则，将遍历中指向“当前”节点的指针更新为指向后继节点。
• 对于 BST，此排序通常是按中序遍历，按排序顺序访问左分支、当前节点和右分支。
• 要找到下一个节点，它会查看当前节点的右子节点并找到其下最左侧的节点。
• 如果不存在右子节点，它会向上遍历父指针，直到找到一个父节点，该父节点是其父节点的左子节点。
• 通过在循环内部重复调用 next()，可以按顺序访问 BST 中的所有节点。

isEnd()

二叉搜索树 (BST) 实现中的 isEnd() 函数用于检查树的遍历是否已到达末尾。

具体来说，它执行以下操作

• 检查遍历期间维护的当前节点指针是否已变为 null。
• 如果当前节点为 null，则返回布尔值 true，表示遍历已到达末尾。
• 如果当前节点指向树中的有效节点，则返回 false。

它之所以有用是因为

• 通过迭代 BST 数据结构进行遍历需要一种检测何时到达末尾的方法。
• 检查 null 指针比检查当前节点是否等于某个哨兵值更简洁。
• 它将指针检查逻辑从调用者代码中抽象出来，将结束检测封装在 BST 类中。

因此，本质上，isEnd() 提供了一个简单的接口来检查迭代 BST 遍历是否已完成。将其返回值与 null 指针指示符进行比较比在代码中暴露指针检查逻辑更简洁。

典型用法是

它使调用者编写迭代 BST 遍历更简单、更简洁。

实现二叉搜索树 (BST) 前向迭代器的 C++ 程序

输出

2 3 4 5 6 7 8