java - 检测循环引用

Question

所以在一次采访中，我实际上被问到一个像这样的简单问题，假设我有一个嵌套的 JSON 响应，[a, b, c ,d [a, [b, [d, e], g ]， H]。我被要求实现一个基本上可以处理存储此数据的类和一个打印方法来这样做，所以这就是我所拥有的:

public class JSONode
{
   private String str;
   private JSONode nodes;

   public JSONode (String a, ArrayList<String> n)
   {
        str = a;
        nodes = n;
   }
}

public class JSONResp
{
  private ArrayList<JSONode> arr;

  public JSONResp ()
  {
    arr = new ArrayList<JSONode>();
  }

  public boolean checkCircular(JSONode temp)
  {
    for (int i = 0; i < arr.size(); i++)
    {
        if (arr.get(i).nodes == temp)
            return true;
    }
    return false;
  }

  public void add (JSONode nd)
  {
    if (!checkCircular(nd))
    arr.add(nd);
  }

  public void recurseJSONode(JSONode)
  {
      if (!JSONode.node)
           System.out.print(JSONode.str);
      else {
          System.out.print(JSONode.str);
          recurseJSONode(JSONode.node);
      }
  }

  public void print()
  {
    for (int i = 0; i < arr.size(); i++)
       recurseJSONode(arr.get(i));
  }

  public static void main (String[] args) {
      JSONResp x = new JSONResp();
      x.add(new JSONode("a", null);
      x.add(new JSONode("b", null);
  }

}

现在他说我打印的时候会有循环引用的问题，也就是说我有list A = [a, b, c, D] and D = [q, t, y, A]。所以他说我必须使用上面的 checkCircular 来防止添加 D。我做了一个尝试。也只是一个节点，我知道我的 recurseJSONNode 不正确，打印也不正确，所以也在寻找解决该问题的建议。我只是对这个问题感到好奇。

Answer 1

您的循环检查不正确的原因是您只在您尝试将其添加到的一个节点下查找 JSONnode 的现有副本。但是 A 可能在 B 下，B 在 A 下，所以每个在其父级列表中都是唯一的。

回复:使用堆栈跟踪递归函数中的 Activity :

Set<SomeNodeType> stack = new HashSet<SomeNodeType>();
someRecursiveThing(rootNode, stack);

然后在 someRecursiveThing 中:

void someRecursiveThing(SomeNodeType under, Set<SomeNodeType> stack) {

    if (!stack.add(under)) {
        return;

    // continue happily, e.g. call self with child node,
    // passing down the stack

    SomeNodeType child = ...
    someRecursiveThing(child, stack)

    // finish by removing 'under' from the stack:
    stack.remove(under);
}

HashSet 的优点是add 和remove 通常在恒定时间内运行——树的大小无关紧要。

比较:

Markus Lausberg 的回答建议对整棵树进行完整的递归搜索，这将是 O(N)，其中 N 是树中的节点数，当您对每个节点进行检查时，它最终是 O (N^2)。一棵有 10 个节点的树将进行 100 次节点比较；一棵 1000 个节点的树将进行 1000,0000 次节点比较。

在 kan 的回答中，检查涉及搜索父链，这将取决于树的深度。对于一棵完全不平衡的树(最坏的情况)，深度将与节点数相同，再次给出 O(N^2)。对于平衡树，深度将是 ~log N，好不了多少(请记住，必须对每个节点进行检查)。

这些差异的影响取决于用于确定两个节点是否相同的比较操作。如果它只是一个指针比较(即您只关心它们是否是同一个对象)并且树永远不会很大，则 HashSet 的开销可能会产生负面影响。而如果您需要以更复杂的方式比较两个节点，那么每次比较的代价都很大，而且树很大，那么优化的 HashSet 查找将变得有益。