在二叉树中查找循环

如何在二叉树中查找循环？我正在寻找一种解决方案，而不是将访问节点标记为已访问或进行地址散列。有任何想法吗？在二叉树中查找循环

2012-07-05 novice

二叉树不包含循环。如果他们这样做，他们首先不是树木。

2012-07-05 21:01:11 amb

如果最后一个节点指向根节点，那该怎么办......多数民众赞成循环权...如果它已被错误地执行......那么你将如何检测它？ – novice 2012-07-05 21:03:05

最后一个节点被称为叶子，它们不指向其他节点。你在说什么，是图形而不是树。如果你有一棵树（无论是二进制，红黑，AVL等），它将不包含循环。树的构建禁止循环。 – amb 2012-07-05 21:06:33

正如我所说的，它是由于一些错误而发生的......为你的便利让我们放下d字树n假设它是一些像结构一样的树有一个循环......现在你会怎么做？ – novice 2012-07-05 21:08:19

正如前面提到的那样：树不包含循环（循环）。

要测试您向图包含（已加入到树节点引用）的循环，你可以遍历槽树并添加每个节点的访问列表（或它的哈希值，如果你比较喜欢），并检查每个新节点是否在列表中。大量用于图表中循环检测的算法只是谷歌搜索而已。

2012-07-05 21:29:22 mariusnn

假设你有一棵二叉树，但你不信任它，你认为它可能是一个图，一般情况下会记录下被访问的节点。从图中构建最小生成树的方法有点相同，这意味着空间和时间的复杂性将成为一个问题。

另一种方法是考虑保存在树中的数据。考虑你有一些哈希值，所以你可以比较。

甲伪代码将测试该条件：

每个节点必须具有最大2个孩子和1个父（最多3个连接）的。多于3个连接=>不是二叉树。
父母不能是孩子。
如果一个节点有两个子节点，那么左边的子节点的值比父节点的值小，右边的子节点有更大的值。因此，考虑到这一点，如果叶子或内部节点具有较高级别上的某个节点（如父母的父节点），则可以根据这些值确定一个循环。如果一个孩子是一个正确的节点，那么它的值必须大于父母的值，但是如果该孩子形成一个循环，这意味着他来自父母的左边部分或右边部分。

3.a.所以，如果它是从左边的部分，那么它的价值比它的兄弟姐妹小。所以=>不是二叉树。这个想法对另一部分来说也是一样的。

测试之外，在什么样的形式是，你要测试的树？记住每个节点都有一个指向它的父节点的指针。这个指针指向单亲。因此，根据树的格式，您可以从中获益。

2012-07-05 21:45:00 amb

如果可能存在循环，那么它只是平常的图形。有很多种方法可以找到循环： Finding all cycles in a directed graph

2012-08-08 08:51:51 mvnukov

虽然这可能在理论上回答这个问题，但[这将是更可取的]（// meta.stackoverflow.com/q/8259）在这里包括答案的基本部分，并提供了供参考的链接。 – 2016-08-30 17:09:06

回答