问题标签 [binary-search-tree]

为什么std::map实现为红黑树？

那里有几种平衡二叉搜索树（BST）。选择红黑树时的设计权衡是什么？

我正在尝试使用 BST 实现数据库接口。我有一个内部类 BTSEntry，它代表一个带有变量键、值和左/右节点的节点。每个左节点小于（按字母顺序）其父节点，而每个右节点大于其父节点。

第一个问题是我不知道 Entry 内部类中的“nextNode()”应该是什么。它只是正确的节点吗？还是我在下面做了什么？

第二个问题是我真的不知道如何实现“Int value get(Str key)”方法。编辑：我试图做 get(key) 方法。这是正确的吗？递归会为此工作吗？

这是我到目前为止所做的。任何帮助将不胜感激！:)

在学校作业中，我应该完成一个方法，该方法应该按升序返回节点元素数组。节点组装在二叉搜索树中，因此为了正确排序它们，我得到了一个技巧来创建一个递归方法来完成这项工作。

问题在于，根据测试输出，这甚至不会产生集合中的所有元素（java.lang.AssertionError: toArray() 不会返回集合中的所有元素。）

我想不出任何其他方法来处理数组，而且我不太确定递归是否有效。任何帮助深表感谢。下面是我的代码：

测试输出：

java.lang.AssertionError：toArray() 不返回集合中的所有元素。：TestPerson("Bender").compareTo(TestPerson("Fry")) == 0 预期：true 但在 inf1010.assignment 处为：false .IfiCollectionTest.assertCompareToEquals(IfiCollectionTest.java:74) 在 inf1010.assignment.IfiCollectionTest.assertCompareToEquals(IfiCollectionTest.java:83) 在 inf1010.assignment.IfiCollectionTest.assertCompareToEqualsNoOrder(IfiCollectionTest.java:100) 在 inf1010.assignment.IfiCollection( IfiCollectionTest.java:202)

我不知道我是否应该发布更多的测试代码，它相当广泛，对于一个帖子来说可能有点太多了？

我们知道前序、中序和后序遍历。什么算法将重建 BST？

我必须为 BST 编写一些方法，我有一些问题，让我解释一下。

我有以下结构：

和

以及以下功能：

和

在我的主体中，我必须称之为（例如）：

我要做的是使用递归创建函数 insertKey(int i, struct tree *T)。

我想做类似的事情

但它并没有走得太远，使用递归可以让我再次调用 insertKey 但我似乎无法以相同的方式使用节点和树。

有谁知道我如何在不改变给定结构的情况下做到这一点？

非常感谢你。

我收到这样的错误：

mybst.cpp:262: 错误: '*' 标记之前的预期构造函数、析构函数或类型转换

主要原因在于这个功能：

叶*&树::createBST(int preOrder, int inOrder, int len)

该算法由如何使用 {pre,in,post} 顺序遍历结果重建 BST提供

为什么我会收到此错误？

***************Edited:***************************

Compile free error. But I got segmentation fault after run.

Run it under gcc.

主要问题在功能上

注意：我已经发布了两个关于此的问题。因为我修改了很多代码，所以我开始了一个新的帖子。

这是一个头文件。我不明白search函数，为什么返回类型node**？

编辑：在此处添加搜索功能：

我有一个 BST，我从 1...n 随机插入密钥（每个排列都以 1/n！概率完成）。我的问题是为什么即使排列是统一的，结果树也不统一？