问题标签 [binary-search-tree]

我有一个用 C 语言创建的二叉搜索树。问题是我找不到删除所有节点的有效方法，例如 id>5。

当我遍历树时，如果我删除一个节点，递归就会出错，因为结构不一样。

有什么办法，而不是在从树中删除数据之前使用帮助堆栈来保留数据？

以下二叉搜索树 (BST)的实现有什么问题？有人告诉我，最好在插入函数中使用指向struct节点的指针作为参数。

我有这个代码片段

当我insert像它一样调用函数时，insert(5); insert(8);它总是打印root is null。

有什么问题？？

我正在为何时使用二叉搜索树以及何时使用字典的概念而苦苦挣扎。

在我的应用程序中，我做了一个小实验，它使用了 C5 库TreeDictionary（我相信它是一个红黑二叉搜索树）和 C# 字典。字典在添加/查找操作时总是更快，而且总是使用更少的内存空间。例如，在 16809<int, float>个条目中，字典使用 342 KiB，而树使用 723 KiB。

我认为 BST 的内存效率应该更高，但树的一个节点似乎比字典中的一个条目需要更多的字节。是什么赋予了？BST 是否比字典更好？

另外，作为一个附带问题，有没有人知道是否有比上述任何一种结构更快+内存效率更高的数据结构来存储<int, float>字典类型访问的对？

这应该遍历 BST 并删除每个节点，包括根节点。但是，最后，我收到消息“根仍有左节点”。为什么不是所有节点都被删除？

我正在尝试计算一棵树的高度。我不喜欢下面写的代码。

它给了我正确的结果。但是在一些帖子（谷歌页面）中建议做一个后序遍历并使用这个高度方法来计算高度。有什么具体原因吗？

我知道“if right[x] != NIL then return tree-min”是什么意思，我把它翻译成：

其余的我很难理解。

我们总是看到（二叉搜索）树上的操作具有 O(logn) 最坏情况的运行时间，因为树的高度是 logn。我想知道我们是否被告知算法的运行时间是 logn 的函数，例如 m + nlogn，我们是否可以得出结论它必须涉及（增强的）树？

编辑：感谢您的评论，我现在意识到分治和二叉树在视觉/概念上是如此相似。我从来没有在两者之间建立联系。但我想到了一个 O(logn) 不是分治算法的情况，它涉及一棵没有 BST/AVL/红黑树属性的树。

这是具有 Find/Union 操作的不相交集数据结构，其运行时间为 O(N + MlogN)，其中 N 是元素的数量，M 是 Find 操作的数量。

如果我错过了某事，请告诉我，但我看不出分治法是如何在这里发挥作用的。我只是在这个（不相交集）案例中看到它有一个没有 BST 属性的树，并且运行时间是 logN 的函数。所以我的问题是关于为什么/为什么我不能从这个案例中做出概括。

我想让我的avl-tree支持重复键，但是具有重复项的默认行为存在问题，binary search tree即旋转可以使具有相同键的节点位于父级的左侧和右侧。

例如，当添加三个节点都带有键 A 时，会导致树进行旋转，如下所示：

因此，使用该键获取所有条目将是一个问题……并且双向搜索并不好。

我想到的解决方案是让每个节点存储一个重复的数组，所以当添加一个已经存在的新项目时，只需向数组中添加一个新项目，使用键删除项目将删除整个节点，同时查找所有项目with key 将返回该数组。

是否有任何其他方法来处理重复？

插入项需要一个键和一个值..所以我需要存储值以便通过 findAll 使用某些键方法返回它们。

我对 C 很陌生，我正在尝试在 C 中实现一个二叉树，它将存储一个数字和一个字符串，然后将它们打印出来，例如

我到目前为止的代码是：

目前它似乎适用于ints 但描述部分仅打印出最后输入的内容。我认为它与char数组上的指针有关，但我没有运气让它工作。有什么想法或建议吗？