在二叉树中找到一个循环

Question

如何在二叉树中找到循环？我正在寻找一种不需要标记已访问节点或进行地址哈希的解决方案。有什么想法吗？

- novice

---

如果存在循环，那么这只是一个普通的图。有许多方法可以找到循环：https://dev59.com/PXRB5IYBdhLWcg3wtJGF - mvnukov

Answer 1

假设您有一棵二叉树，但您不信任它，并认为它可能是一个图形，一般情况下会要求记住已访问的节点。构建最小生成树的算法与此类似，这意味着空间和时间复杂度将成为问题。

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

伪代码将测试以下条件：

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

2.父节点不能是子节点。

3.如果一个节点有两个孩子，则左孩子的值小于父节点，右孩子的值大于父节点。因此，如果叶子节点或内部节点的某个孩子是在更高层次上的某个节点（如父节点的父节点），则可以基于值确定循环。如果一个孩子是右节点，则它的值必须大于其父节点，但如果该孩子形成循环，则意味着它来自父节点的左侧或右侧。

3.a.因此，如果它来自左侧，则它的值小于其兄弟。因此=>不是二叉树。对于另一部分，思路也相同。

除了测试之外，您要测试的树是什么形式？请记住，每个节点都有指向其父节点的指针。该指针指向单个父节点。因此，根据您的树的格式，您可以利用这一点。

- amb

Answer 2

如前所述：树（按定义）不包含循环（循环引用）。

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

- mariusnn