问题标签 [binary-tree]

我正在递归加载马家谱数据。对于一些错误的数据集，我的递归永远不会停止......那是因为数据中有循环。

如何检测这些周期以停止重复？

我想到在重复维护一个包含所有“访问”马的哈希表时。但这会发现一些误报，因为一匹马可以在一棵树上出现两次。

不可能发生的是，一匹马以自己的父亲或祖父或曾祖父的身份出现。

我正在做一个名为数据结构和算法的单元。我们刚刚开始，我的教授刚刚教给我们什么是代数语义以及什么是公理等基础知识。到目前为止，我只是以数组的形式使用树。不使用预排序树的签名作为树（值，树，树），其中值是节点中的值，左节点是第一棵树，右节点是第二棵树。

现在我将我的树定义为树（值，树，树）或 Nil，我不知道如何去定义 addNode（值，树）的代数。

每个级别都变得越来越复杂，另外，我无论如何都想不到一次扫描一个级别，现在已经尝试了一个小时。当我们沿着树向下走时，代数只是分支成越来越多的 if-else。我做对了吗？你能为我指出正确的方向吗？或者树不能实现为树（值，树，树）？

这是我教程的一部分（在附加问题中不值得任何标记），但我不是在寻找即时答案，我喜欢这个主题，并想了解更多。

编辑1：我查看了维基百科，我不想使用教科书来获得明确的答案，我只是在寻找正确方向的提示，无论我的方法是正确的还是完全不可能将树定义为树（值，树，树）。我知道您可以以列表的形式表示树 ADT。但我真的想好好想想。希望这是有道理的。非常感谢你们！

编辑2：嗯，很难通过互联网解释。假设我正在定义一个名为“树”的新数据结构。我可以以任何我想要的方式定义它，它必须表现得像一个平衡的二叉树（虽然，父母和孩子的值无关紧要）所以我将它定义为树：树（值，树，树）或无它不是编程代码，这就是我的定义。Tree 是一个值 + 2 棵其他树，或者 Tree 是 nil。现在 addNode(value, tree) 向树添加一个节点，同时仍然保持平衡。它不是编程代码，它只是代数语义。不知道能不能解释清楚。但是我找到了一个可以使用队列或堆栈实现的解决方案，但这是我必须定义的另一个 ADT，它是无效的。

编辑3：似乎我已经假设了许多使问题变得比实际应该更难的事情。首先，从我给出的一点解释来看，Gamecat 的回答是完美的。但我同意这些评论，包括其他 ADT 是完全有效的。事实上，当我们构建任何使用 Int 的东西时，我们正在为该结构使用 ADT。我认为每个 ADT 都必须是独一无二的。无论如何，非常感谢您的回答！

我知道性能永远不是黑白的，通常一种实现在 X 情况下更快，在 Y 情况下更慢，等等，但总的来说 - B-trees 是否比 AVL 或 RedBlack-Trees 更快？它们的实现比 AVL 树（甚至可能是红黑树？）要复杂得多，但是它们更快吗（它们的复杂性是否得到回报）？

编辑：我还想补充一点，如果它们比等效的 AVL/RedBlack 树（就节点/内容而言）更快 -为什么它们更快？

考虑一个二叉树：

1. n是一个节点，如果n是一个整数
2. (+ a b ) 是一个节点，如果a和b是节点。

我们有以下三个操作：

1. (+ a b ) -> (+ b a )
2. (+ (+ a b ) c ) -> (+ a (+ b c ))
3. (+ a (+ b c )) -> (+ (+ a b ) c ) -- (2. 反向)

我需要一种算法来使用这些操作给出给定树的所有可能排列。任何操作都可以应用于任何子树。对于排列，我的意思是任何具有完全相同的叶子的树。这可能不是很困难，但我似乎无法弄清楚。

[编辑]叶子也可以是名称（即变量），因此不能选择将它们的属性作为整数。树确实代表了总和。

[Edit2] 本练习的重点是通过查找A和-A形式的项来减少总和，将树调成子树 (+ A -A ) 以消除它们。上面这三个操作是我系统中的公理，需要一直用到，否则无法证明归约树与原树相等。由于我使用的是十二逻辑编程语言，如果我能找出一个算法来完成我最初提出的要求，其余的就很容易了，但当然欢迎替代解决方案。

假设我有一个区间（或范围）列表（例如 10-15、5-7、9-12 ..）。问题是找到重叠的范围子集。当然，我可以为此使用区间树。

我遇到的实际问题是有多个范围。最好用一个例子来解释：

1. 10-15、5-7、9-12
2. 1-2、3-6、14-15
3. 3-5、9-15、10-15

在上述情况下，（1）和（2）在第二范围内有重叠，在（3）和（1）、（2）之间在第三范围内有重叠。

基本上，我需要找到项目列表之间的所有重叠。

也许我可以使用 3 个单独的区间树来找出答案。有一个更好的方法吗？

我有点不得不搁置我以前的 C 问题，因为这个问题现在更重要......

我已经在我的二叉搜索树上编写了插入和删除函数，但删除函数不完整。有几件事我需要帮助...

1）我的插入功能好还是可以以某种方式改进？

2）我的删除功能缺少删除左右子节点的节点。在过去的几个小时里，我进行了很多搜索，但找不到合适的方法。

2.a)我应该如何删除一个有 2 个子节点的节点？

2.b）和第一个问题一样，删除功能好还是可以改进？这个我知道它可以，因为我在那些 if 中重复了很多代码，但我不知道如何改进它，我也需要帮助。

你可能会注意到，但让我说两句：

• 该树使用字符串而不是普通的 int 表示。这就是我一直使用 strcmp() 的原因，我认为我使用它是正确的。
• 我没有使用递归，我宁愿传递指针（在这种情况下是结构指针）并使用它。不知何故，它看起来更干净，将来如果节点被删除，我想返回一个成功值。

更新如下：
我已经完成了删除功能的迭代版本，但我不喜欢它的一些东西，也许它们可以改进（或不改进），但我看不出如何。我还尝试对丢失的情况进行编码，删除一个有 2 个孩子的节点，但它没有按应有的方式工作......

我已经评论了整个代码，我认为代码可以改进以及问题出在哪里。我还将这些问题命名为 A、B（不再有 B）、C 和 D，因此我们可以轻松地引用它们。

我知道一个节点的程度是它拥有的孩子的数量。

但是，我们如何定义树的度数？

我需要找到一种算法来生成二叉树的所有可能排列，并且需要在不使用列表的情况下这样做（这是因为树本身带有无法转换为列表的语义和约束）。我找到了一种适用于高度为 3 或以下的树的算法，但是每当我达到更高的高度时，我会在每个添加的高度中丢失一组可能的排列。

每个节点都携带有关其原始状态的信息，以便一个节点可以确定是否已针对该节点尝试了所有可能的排列。此外，该节点携带有关天气的信息，它是否已被“交换”，即它是否已经看到它的子树的所有可能排列。树是左居中的，这意味着右节点应该总是（除了在某些情况下我不需要为这个算法介绍）是叶节点，而左节点总是叶节点或分支。

我现在使用的算法可以这样描述：

算法的期望行为是这样的：

等等...

二叉树 http://img9.imageshack.us/img9/9981/binarytree.jpg

序列化给定二叉树并反过来评估每个序列化二叉树的唯一 ID 的最佳方法是什么？

例如，我需要序列化子树 (2,7,(5,6,11)) 并生成代表该子树的唯一 id ' x '，这样每当我遇到类似的子树 (2 ,7,(5,6,11)) 它将序列化为相同的值“ x ”，因此我可以推断出我找到了匹配项。

在这里，我们假设每个节点都具有唯一的属性。在上面的示例中，它将是分配给每个节点的数字，因此它们总是会为相似的子树生成相同的 id。我正在尝试在 C++ 中执行此操作。

是否已经存在执行这种序列化树匹配的算法？

给定一棵具有整数、左右指针的二叉树，如何在 O(n) 时间和 O(1) 额外内存（无堆栈/队列/递归）内遍历树？

这个人给出了一个不是 O(n) 总时间的解决方案，它将当前路径编码为一个整数（因此适用于深度有限的树）。

我正在寻找经典的解决方案

（剧透）

对子节点中每个节点的父节点进行编码。