问题标签 [binary-tree]

我正在阅读 Steve Yegge 关于单身人士的文章。在其中他提到他的老师告诉他 AVL 树是邪恶的。仅仅是红树和黑树是更好的解决方案吗？

我需要一个Java 中的IntervalTree或 RangeTree 实现，并且很难找到一个具有有效删除支持的实现。

sun.jvm.hotspot.utilities.IntervalTree有一个内置的，但是 RBTree 超类中的deleteNode方法指出：

尝试从树中删除节点最终会引发异常：

节点的最大端点未正确更新

delete在 sun.jvm.hotspot.utilities.IntervalTree 的子类中正确实现功能有多难？或者是否有另一个已经正确实现的间隔树实现？

目前我只是清除树并在每次删除时重新填充它，这远非理想（注意：在 RBTree 中设置 DEBUGGING=false 极大地加快了速度）。

完全二叉树被定义为一棵二叉树，其中除了可能最深的层外，每一层都被完全填满。在最深处，所有节点都必须尽可能地靠左。

我认为一个简单的递归算法将能够判断给定的二叉树是否完整，但我似乎无法弄清楚。

我创建了一个带有一些整数值的二叉树，我可以通过我的代码搜索树。但我不知道如何进行删除节点操作。

那么，如何删除节点？

寻找 C++ 中简单树迭代的示例，包括递归和迭代。(post, pre 和 in-order)

在树类中，我假设比较两个节点，因为您知道搜索和添加项目。我对如何使其具有可比性有一些问题。当向树添加数据（通用的，任何东西）时，调用 Tree 类，然后创建一个新的 Node 对象。如何在 Node 类中声明变量数据/元素，使其属于 E 类型（任何类型）并且仍然是 Comparable？说真的，我来回尝试过，但没有得出任何结论。

找出两个给定的二叉树是否在结构和内容上相等的有效算法是什么？

根据这个问题，一定大小的不同搜索树的数量等于一个加泰罗尼亚数。是否可以枚举这些树？也就是说，有人可以实现以下两个功能：

（我问是因为树的二进制代码（这个问题的答案之一）将是表示未知范围的任意大整数的非常有效的代码，即整数的可变长度代码

请注意，每个代码长度的整数个数是 1, 1, 2, 5,..（加泰罗尼亚语序列）。)

这里的二叉树不一定是二叉搜索树。
该结构可以被视为 -

我可以与朋友一起解决的最大解决方案是这种类型的 -
考虑一下这个二叉树：

中序遍历产生 - 8, 4, 9, 2, 5, 1, 6, 3, 7

并且后序遍历产生 - 8, 9, 4, 5, 2, 6, 7, 3, 1

例如，如果我们想找到节点 8 和 5 的共同祖先，那么我们在中序树遍历中列出所有介于 8 和 5 之间的节点，在这种情况下恰好是 [4, 9 , 2]。然后我们检查这个列表中的哪个节点在后序遍历中最后出现，即 2。因此 8 和 5 的共同祖先是 2。

这个算法的复杂性，我相信是 O(n) （O(n) 用于中序/后序遍历，其余步骤也是 O(n)，因为它们只不过是数组中的简单迭代）。但很有可能这是错误的。:-)

但这是一种非常粗糙的方法，我不确定它是否会在某些情况下失效。这个问题还有其他（可能更优化）的解决方案吗？

如何在 Perl 中创建二叉树？