问题标签 [binary-search-tree]

嗨，我正在编写 BST 并编写了以下添加子函数。

我给出“23 12 122 1 121 15”作为输入。根是我在类的构造函数中创建的节点 23。

问题：当我进行树遍历时，我只得到 23 和 15 作为输出。 问题：我在这个函数中做错了什么？

如果二叉搜索树的前序遍历是6、2、1、4、3、7、10、9、11，那么如何得到后序遍历呢？

我最近一直在编写一堆不同的二叉搜索树实现（AVL、splay、treap），我很好奇是否有一种特别“好”的方式来编写迭代器来遍历这些结构。我现在使用的解决方案是让 BST 中的每个节点都存储指向树中下一个和上一个元素的指针，这将迭代减少到标准的链表迭代。但是，我对这个答案并不满意。它通过两个指针（下一个和上一个）增加了每个节点的空间使用量，在某种意义上它只是作弊。

我知道一种构建二叉搜索树迭代器的方法，该迭代器使用 O(h) 辅助存储空间（其中 h 是树的高度），通过使用堆栈来跟踪边界节点以便稍后探索，但我由于内存使用，我拒绝对此进行编码。我希望有某种方法可以构建一个只使用常量空间的迭代器。

我的问题是 - 有没有办法在具有以下属性的二叉搜索树上设计迭代器？

1. 元素按升序访问（即中序遍历）
2. next()并且hasNext()查询在 O(1) 时间内运行。
3. 内存使用量为 O(1)

为了更容易，如果您假设树结构在迭代期间没有改变形状（即没有插入、删除或旋转），那很好，但如果有一个确实可以处理这个问题的解决方案，那就太酷了。

可能重复：
C/C++ 中的 BST 超级节点生成

有人可以帮我实现带有超级节点的二叉搜索树的生成、添加和删除吗？我真的需要 C/C++ 中的算法。

我今天去参加一个面试，我被要求序列化一棵二叉树。我实现了一种基于数组的方法，其中节点 i 的子节点（按级别顺序遍历编号）位于左子节点的 2*i 索引处，右子节点位于 2*i + 1 处。面试官似乎或多或少很高兴，但我想知道序列化到底是什么意思？它是否特别涉及扁平化树以写入磁盘，或者序列化树是否还包括将树转换为链表，例如。另外，我们如何将树扁平化为（双）链表，然后重建它？你能从链表中重新创建树的确切结构吗？

我用 natbib 使用 Vim LaTeX 六个月，没有任何问题。但是为了使用新的 bib 样式文件（即 rfs.bst），我开始使用 harvard.sty，这给了我两个小问题：

(1) 语法高亮不完整；对于\citeasnoun，Vim 只高亮显示\cite部分。使用另一个 Vim 插件 (Vim-plugin-R) 我可以更新语法突出显示，但我不知道如何在 Vim 中执行此操作。我刷新了 MikTex 中的数据库，但是没有用。

(2) Vim LaTeX 会根据需要自动重新运行以获取正确的引用——Vim 中的状态窗口显示它经过多次运行，结果符合预期——但我仍然收到此警告：

我该如何解决这些问题？谢谢！

请帮助我一直在尝试生成大小为 1024 的随机二叉搜索树，并且元素需要是随机排序集......我可以通过手动添加元素来编写代码来手动创建二叉搜索树，但我'我无法编写一个代码，该代码将生成大小为 1024 的随机平衡二叉树，然后尝试在该树中找到一个密钥......请提前谢谢你......

从评论中编辑添加的代码

是的，这是家庭作业……这就是我目前得到的代码：

我是 C++ 的初学者，在寻找 BST 的最小元素时遇到了问题。BST 是这样实现的：

InOrder、Destroy 和 Insert 方法的实现如下：

我用来打印数字的主要函数和函数如下所示：

正如您可能注意到的，InOrder 方法也被实现了，也许它可以以某种方式帮助解决我的问题......对不起我的英语不好：/

我已经探索了T-tree和 B-/B+ 树的定义。从网络上的论文中，我了解到 B 树在分层内存中表现更好，例如磁盘驱动器和缓存内存。

我无法理解的是为什么 T-trees 甚至被用于平面内存？

它们被宣传为 AVL 树的节省空间的替代品。

在最坏的情况下，T 树的所有叶节点只包含一个元素，所有内部节点都包含允许的最小数量，接近满。这意味着平均只使用了一半的分配空间。除非我弄错了，否则这与 B 树的最坏情况相同，即 B 树的节点是半满的。

假设两棵树都将键本地存储在节点中，但使用指针来引用记录，唯一的区别是 B 树必须为每个分支存储指针。这通常会导致高达 50% 或更少的开销（在 T-tree 上），具体取决于键的大小。事实上，这接近于 AVL 树中预期的开销，假设没有父指针、嵌入在节点中的记录、嵌入在记录中的键。这是阻止我们使用 B-trees 的预期效率增益吗？

T 树通常在 AVL 树之上实现。AVL 树比 B 树更平衡。这可以与T-trees的应用联系起来吗？

运行fold (+) 0 sample会给我一个关于 (+) 应用于太多参数的错误。为什么？

参见：折叠