怎么判断一棵树有没有环路

比如一棵树的a节点和b节点同时指向了c节点，或者他们的某个子节点同时指向c节点，这种情况要怎么判断出来？给个思路或者代码

11 个解决方案

#1

树能够有环吗？

#2

就是要判断它不是树，比如本来他是一棵树，然后经过操作出现了环，这种情况要怎么判断

#3

如果在节点里可以设置一个标志位，就很简单了，遍历一遍，节点被访问过之后mark，如果访问到一个节点，标志位已mark，则该节点已被访问过，有环

#4

你的树是用什么表示法的~~

#5

树不可能有环的。

如果想判断是否存在环，可以在节点中增加一个变量，用来标记此节点是否已经遍历过。
遍历时，判断节点的此变量是否为true,就可以判断是否存在环。

#6

树是用链表表示的，增加节点判断这个办法不错，还能找到是哪个点重复了。
在不增加节点的情况下，还有什么方法不？

#7

从任意根节点开始，搜索与他连接的子节点，放进一个目录中，再从此目录中搜索与他们连接的点，并加入到此目录中，如果发现某个加入的点已经出现过了，这时候就是有环了，时间复杂度为节点数量o(n)。因为树中一点到达其他人任意点的路径只有一条。

#8

发现增加变量，每次判断前都需要清空一下这个变量，这样判断一次就要遍历2次，开销有点大。能不能有高效点的方法

#9

那你就只能每个节点判断。
标记一个节点，递归实现是否判断过程中是否回到了该标记，这样的时间复杂度是n的平方了

#10

链表存储的话，初始化时需要遍历一次。暂时没有好的方法，期待高手！~

#11

引用 5 楼 yuwei2589 的回复:

树不可能有环的。

如果想判断是否存在环，可以在节点中增加一个变量，用来标记此节点是否已经遍历过。
遍历时，判断节点的此变量是否为true,就可以判断是否存在环。

Up
lz可以参看图的搜索算法