问题标签 [binary-search-tree]

我即将创建一个“智能”字典，如果用户的单词不在字典中，它可以生成相似的单词。

字典从读取带有单词的文件开始，单词应该添加到二叉树和哈希表中。哈希表用于判断词或相似词是否在字典中，哈希表会产生布尔效应，因此我们可以快速查看二叉搜索树是否包含该词。哈希表必须是我们字典长度的十倍左右，因为我们还包括与哈希表相似的单词。作为 Java 的新手，我想了解如何制作适合我情况的散列函数的提示和建议。

我正在研究创建一个通用的 BST。没有什么喜欢没有 COTS，但我正在尝试确定跟踪 void* 类型的最佳方法。这是节点的接口：

但是，当我编写添加/删除时，我需要进行比较，因此我需要跟踪“数据”指向的数据类型，对吧？

基本思想是有一个枚举 Node_Type 和一个函数 compareTreeNodes，它接收两个 TreeNode 和枚举作为第三个参数。这将允许函数确定将 void* 转换为什么。

还有其他/更好的想法吗？

我正在阅读二叉搜索树，并在想我们为什么需要 BST？据我所知，所有事情也可以使用简单的排序数组来实现。例如-为了构建具有 n 个元素的 BST，我们需要n*O(log n)时间，即O(nlog n)查找时间为O(log n). 但是这个东西也可以用数组来实现。我们可以有一个排序的数组（需要O(nlog n)时间），并且其中的查找时间也是O(log n)二进制搜索算法。那么为什么我们需要另一个数据结构呢？BST 是否还有其他用途/应用使它们如此特别？

——拉维

我正在阅读Peter Brass 的《高级数据结构》。

在搜索树一章的开头，他指出搜索树有两种模型——一种是节点包含实际对象（树用作字典时的值），另一种是所有对象都存储在叶子和内部节点仅用于比较。

第二个模型比第一个模型有什么优势？

为了准备数据结构的期中考试，教授给了我们去年的测试，其中一个问题涉及将示例树重新排列成完整的二叉搜索树。我尝试了几种不同版本的写出树的方法，但是 Wolfram Mathematica 提供的这个完整的二叉树示例根本没有帮助，因为它也符合完整的定义。教科书将完整的二叉树定义为通过 n-1 级的树是完美的，在 n 级有一些额外的叶节点，全部左对齐。

节点是A E I L N O P R S T U, n=11 个节点。这是我想出的最佳答案：

但这适合 WM 的树示例，但不适合书籍示例。那么哪个是正确答案呢？

我知道以前有人问过类似的问题，但我认为我的解决方案要简单得多。特别是与维基百科相比。

请证明我错了！

如果您有一棵树，其节点具有给定的数据结构：

你可以写一个这样的函数：

这段代码非常简单，最坏的情况是 O(n)，平均情况可能是 O(logn)，特别是如果树是平衡的（其中 n 是树中的节点数）。

与哈希表相比，二叉搜索树的优势是什么？

哈希表可以在 Theta(1) 时间内查找任何元素，并且添加元素同样容易......但我不确定反过来的优势。

我正在使用 Racket 博士，语言相当大，并且我正在尝试“在？”中创建一个简单的二叉搜索树。方法，如果一个值是否在二叉搜索树中，它将返回。它必须是通用的，接受任何类型的搜索树（无论它是否包含字符串、整数等），但我遇到了这个让我发疯的错误消息。任何帮助表示赞赏，这里是代码：

EDITED:: 它现在可以工作了，但除了数字之外什么都不能（或者至少不能用字符串）.. 新问题：

我收到的错误说：

使用时：

作为输入。

如何从 BST 中删除节点？

我需要一个算法来在 Dr. Scheme 中做到这一点。

给定下图所示的二叉树，假设调用函数 A(root)，确定访问下图所示二叉树节点的顺序。假设树节点和指针的定义如图所示。假设 root 是一个指向包含 60 的节点的指针。 我对这个问题的回答如下。这是正确的吗？我做错什么了？

答案： 在 void A 中，它说首先打印 node_ptr-> data 所以打印 60 然后函数调用 B(node_ptr->left) 然后在 B 内，调用 A (node_ptr->left) 然后打印该数据是 5 . 然后调用 A(node_ptr->right) 返回到 A，打印该数据，以便打印 8。现在我不太确定下一步该做什么，但从逻辑上讲，打印 30 是有意义的，但我不确定 ptr 如何从 8 变为 30。然后如果你继续以相同的模式打印 38 并打印 32。对于右子树... 90 77 62 88