问题标签 [binary-tree]

有两个二叉树 T1 和 T2 存储字符数据，允许重复。
如何确定 T2 是否是 T1 的子树？.
T1 有数百万个节点，T2 有数百个节点。

我有一个二叉树，其中每个节点都可以有一个值。

我想在树中找到值为 null 并且最接近根的节点。如果有两个节点与根的距离相同，则任何一个都可以。我需要最小化对二叉树的读取访问次数。假设工作记忆仅限于 k 个节点。

DFS 到深度 k 是详尽的，但除非我先遍历整个树，否则不会找到最近的节点。BFS 会找到最接近的，但它可能会失败，因为 DFS 可以使用相同的内存找到更深的空值。

我希望对树的读取访问次数最少，并找到最近的空节点。

（我最终也需要在 n 路树中实现这一点，所以一个通用的解决方案会很好。没有对树的写访问权限，只是读取。）

我想对 BST 叶子中的所有值求和。显然，如果不遍历整棵树，我就无法到达树叶。这是真的？我可以在不花费 O(N) 时间的情况下到达树叶吗？

这是一道面试题

我想一个解决办法。它使用队列。

有什么比这更好的解决方案，不使用队列吗？

我正在编写一个迭代函数来搜索二叉树的某个值。在我了解如何泛化类之前，这已本地化为带符号的整数。

假设我的类是 BinarySearchTree，它有一个指向树根节点的指针。还假设节点是通过插入函数插入的，并且具有指向两个子节点的指针。这是 Node 结构的一个非常简略的版本：

因此，您可以放心地假设节点的 uninit 指针将为 NULL。

这是我的代码：

朋友拒绝此代码有两个原因：

1) 如果 next 没有子节点，则两者都将评估为零，并且我将过早退出循环（我永远不会检查搜索到的 val 与 next 的值）。

2）如果next有一个孩子，但是你要搜索的数据应该在树的空边，next将被设置为0，它会再次循环，比较next（即0）左右树之类while(0->left())的，导致未定义的行为。

有人告诉我，这两个问题的解决方案都在于循环条件，但我看不出我能做些什么来轻松解决这种情况。Stack Overflow 社区可以提供任何见解吗？

Im trying to put to an array the deepest path on a BST using a recursive algorithm, and im getting several difficulties... because the only thing that i get is the size of the longest path(equivalent to the height), and i cant put in the array the values regarding to the height of the BST...

Any help?

Sorry, I didn't expose the problem in the entire way. The only thing that I know to do this algorithm is this signature:

(I can use aux methods)

假设我的删除尝试重新平衡树的顺序（从左到右）。

我目前正在编写一个 BinarySearchTree 类，并且我的删除功能目前在大多数情况下都有效（我相信 - 我希望 <3）。我有几个边缘案例要处理：

• 删除根节点是行不通的，因为它没有父节点。
• 在 next 有两个孩子的最后一种情况下，如果它最左边的最右边的后代是右孩子本身，那么 newCurr 将指向 next，这将导致问题，因为 newCurr（又名 next）最终将与 New 交换。

根删除的建议解决方案：

1. 我的解决方案是删除根并使用我的 BST 类的成员函数将根设置为新（使该节点成为根），然后将新的位置设置为 0/NULL。

   A：这行得通，但我必须把案例工作放在各处。

2. 在 BST 类中有一个虚拟父节点，它将简单地将根节点作为它的右手对象（由 billyswong 建议）。

   A：这可能行得通，但我觉得我应该有特殊情况的工作来处理它。

删除两个孩子的建议解决方案：

1. 我的解决办法，就是临时存储New的位置，将New在其父节点中的位置设置为New的右孩子，然后删除临时指针。

   A：这会起作用，但它没有我想象的那么优雅。

2. “旋转节点”（不知道我会怎么做，由 Agor 建议）。

这是我的代码：

发帖者请告诉我此代码 1) 是否有效 2) 是否最佳。

编辑：很抱歉我在函数结束时对驼峰帽的使用不一致。对于我的变量名，我想不出更好的描述，但new它是 C++ 中定义的关键字。

Edit2：发布重构代码，但错误仍然存​​在。

我只需要问，有没有人有免费资源的链接，我可以控制使用 VB6 绘制二叉树。请注意，我并不是说 VB6 中的 TreeView 控件。

我需要一个控件来绘制二叉树

1

/\

2 3

/\ /\

4 5 6 7

我有一段地狱般的时间试图弄清楚这一点。在我所见的任何地方，我似乎都只是在解释如何以非递归方式实际遍历列表（我真正理解的部分）。那里的任何人都可以敲定我最初如何准确地浏览列表并找到实际的前任/后继节点，以便我可以在节点类中标记它们吗？我需要能够创建一个简单的二叉搜索树并浏览列表并将空链接重新路由到前任/继任者。我有一些类似于以下的解决方案的运气：

我正在编写二叉搜索树模板有两个原因 - 学习 C++ 和学习最常见的算法和数据结构。
所以，问题来了——只要我想实现迭代器，在我看来，对于树的结束位置没有严格的定义。你有什么建议？我该怎么做呢？