binary-tree - 在二叉树中查找循环

Question

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

Answer 1

假设您有一棵二叉树，但您不信任它并且您认为它可能是一个图，一般情况下将要求记住访问过的节点。从图中构造最小生成树在某种程度上是相同的算法，这意味着空间和时间复杂度将是一个问题。

另一种方法是考虑您保存在树中的数据。考虑您有许多哈希值，以便进行比较。

伪代码将测试这种情况：

1. 每个节点最多必须有 2 个子节点和 1 个父节点（最多 3 个连接）。超过 3 个连接 => 不是二叉树。
2. 父母不能是孩子。

3. 如果一个节点有两个子节点，则左子节点的值小于父节点，右子节点的值更大。因此，考虑到这一点，如果叶节点或内部节点具有更高级别的某个节点（如父节点的父节点）作为子节点，则您可以根据这些值确定循环。如果一个子节点是右节点，那么它的值必须大于它的父节点，但如果该子节点形成一个循环，则意味着他来自父节点的左侧或右侧。

   3.a. 因此，如果它来自左侧，那么它的值小于它的兄弟。所以 => 不是二叉树。另一部分的想法有些相同。

抛开测试不谈，您要测试的树是什么形式的？请记住，每个节点都有一个指向其父节点的指针。一个 this 指针指向一个单亲。因此，根据您树的格式，您可以从中受益。

Answer 2

如前所述：树（根据定义）不包含循环（循环）。

要测试您的有向图是否包含循环（对已添加到树中的节点的引用），您可以遍历树并将每个节点添加到访问列表（或者如果您更喜欢它的哈希）并检查每个新节点，如果它在列表中。大量用于图中循环检测的算法只需 google 搜索即可。