问题标签 [binary-search-tree]

给定 BST 的定义并使用 BST 的通用版本 fold，我如何检查 BST 是否有效？

这个想法是检查节点值是否大于左子树中的所有值并小于其右子树中的所有值。这必须True适用于树中的所有节点。一个函数bstList简单地输出 BST 中的（有序）值列表。

当然这样的事情是行不通的：

因为，例如，将 fold 函数应用于节点19最终会all (<19) (bstList True) && all (>19) (bstList True).

我了解二叉搜索树是如何实现的，但我不确定使用它相对于大多数编程语言已内置到其标准库中的哈希表有什么优势。

有人可以提供可以用二叉搜索树解决的现实问题的例子吗？

我花了几个小时阅读与该问题相关的帖子，以尝试提出解决方案，但我并没有真正成功地提出解决方案。

所以这里是这样的：我曾经在一次采访中被问到，如果文件中存在特定的单词，我将使用哪种数据结构来搜索。该文件也被认为大到无法放入内存中，面试官确实在寻找磁盘上的解决方案。

B-Tree 是磁盘上的数据结构吗？

二叉搜索树是一种内存数据结构，不是吗？

你好 StackOverflow 社区！

我试图弄清楚如何在不构造树的情况下仅在给定前序或后序遍历（它不应该有太大区别）的情况下计算 BST 的内部路径长度；也就是说，我只想使用上面提到的遍历之一。这对你们大多数人来说可能是一个简单的答案，但你可能已经认为我对树木很陌生。

好吧，任何想法都会受到赞赏和感谢。

我目前有一个二叉搜索树设置，利用模板让我可以轻松地更改二叉搜索树中的数据类型。目前，我无法重载包含要存储在树中的数据的 studentRecord 类。我需要重载此类中的比较运算符，以便我的 BST 可以根据其中一个内容（在本例中为学生 ID）正确比较两个对象。但是，尽管重载了 studentRecord 中的运算符，但仍然没有进行正确的比较。

详情如下：

目前，bst 对象 studentTree 已创建，类型为

studentRecord 是以下类：

每当将新项目添加到我的 BST 时，都必须将它们相互比较。因此，我想重载 studentRecord 类，以便在发生此比较过程时比较 studentID（否则将进行无效比较）。

但是，我的插入函数从不使用我的重载比较函数。相反，它似乎是以其他方式比较这两个对象，导致 BST 中的排序无效。下面是我的插入函数的一部分——重要的是要注意 toInsert 和 nodePtr->data 都应该是 studentRecord 类型，因为正在发生模板过程。

此外，这是 BST 类定义的一部分

关于可能导致这种情况的任何想法？我是否重载了错误的类或错误的函数？感谢您提供任何帮助-我似乎迷路了，因为同时发生了许多不同的事情。

我需要实现两个等级查询[rank(k)和select(r)]。但在我开始之前，我需要弄清楚这两个函数是如何工作的。

据我所知，rank(k)返回给定键的排名k，并select(r)返回给定排名的键r。

所以我的问题是：

1.) 如何计算 AVL（自平衡 BST）中节点的等级？

2.) 是否有可能多个键具有相同的等级？如果是这样，会select(r)返回什么？

我将包含一个示例 AVL 树，如果它有助于回答问题，您可以参考它。

谢谢！

我无法追踪我在哪里犯了错误以及为什么它没有退出 while 循环。

我必须使用二叉搜索树来实现一个行为类似于字符串映射的类。这是我实现的类：

老实说，我不知道如何实现该功能getNextPair()。
如果有人可以帮助我，我将不胜感激。

以我正在处理的任务为例。我们将使用二叉搜索树来查找一组数据中的一部分，然后使用链表查找该组中的另一部分。教授建议的方法是：

其中 data 是包含每条记录的详细信息的类。显然，由于它的设置，treeNode 不能存在于链表中。

会不会更简单：

然后我们可以声明：

并将两种插入算法都包含在类中。

有什么我想念的吗？

我正在做这个作业，我需要按前序、后序和中序打印我的二叉搜索树。但是，似乎只有我的中序方法有效。我使用以下测试用例来检查我的工作。

你能看看我下面的代码，看看我做错了什么。任何帮助/方向将不胜感激。你不必为我解决它，只要让我知道我做错了什么。谢谢。