在二叉树中查找循环 [英] Find a loop in a binary tree
问题描述
如何在二叉树中找到循环?我正在寻找一种解决方案，除了将已访问的节点标记为已访问的节点或进行地址哈希处理之外.有什么想法吗?
How to find a loop in a binary tree? I am looking for a solution other than marking the visited nodes as visited or doing a address hashing. Any ideas?
推荐答案
假设您有一个二叉树，但您不信任它，并且您认为它可能是一个图，那么一般情况下将要求记住被访问的节点.从图上构造最小生成树是一种相同的算法，这意味着空间和时间复杂度将是一个问题.
Suppose you have a binary tree but you don't trust it and you think it might be a graph, the general case will dictate to remember the visited nodes. It is, somewhat, the same algorithm to construct a minimum spanning tree from a graph and this means the space and time complexity will be an issue.
另一种方法是考虑保存在树中的数据.考虑到您有许多哈希值，因此可以进行比较.
Another approach would be to consider the data you save in the tree. Consider you have numbers of hashes so you can compare.
伪代码将测试以下情况:
A pseudocode would test for this conditions:
- 每个节点最多必须具有2个子节点和1个父节点(最多3个连接).超过3个连接=>不是二叉树.
- 父母不得为孩子.
-
如果节点有两个子节点，则左子节点的值小于父节点，右子节点的值较大.因此，考虑到这一点，如果叶子或内部节点在子级上具有某个较高级别的节点(例如父级的父级)作为子级，则可以根据这些值确定一个循环.如果子节点是右节点，则其值必须大于父节点，但如果该子节点形成循环，则表示他来自父节点的左部分或右部分.
- Every node would have to have a maximum of 2 children and 1 parent (max 3 connections). More then 3 connections => not a binary tree.
- The parent must not be a child.
If a node has two children, then the left child has a smaller value than the parent and the right child has a bigger value. So considering this, if a leaf, or inner node has as a child some node on a higher level (like parent's parent) you can determine a loop based on the values. If a child is a right node then it's value must be bigger then it's parent but if that child forms a loop, it means he is from the left part or the right part of the parent.
3.a.因此，如果它是从左侧开始的，则其值小于其同级.所以=>不是二叉树.其余部分的想法基本相同.
3.a. So if it is from the left part then it's value is smaller than it's sibling. So => not a binary tree. The idea is somewhat the same for the other part.
除了测试之外，您要测试的树的形式是什么?请记住，每个节点都有一个指向其父节点的指针. this指针指向单亲.因此，根据树的格式，您可以从中受益.
Testing aside, in what form is the tree that you want to test? Remeber that every node has a pointer to it's parent. An this pointer points to a single parent. So depending of the format you tree is in, you can take advantage from this.
这篇关于在二叉树中查找循环的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
