0

我有一棵树，其中节点包含对两个父节点的引用；由于事物的工作方式，它们可以在某些时候指向相同的节点。

Example:

Parent1: Node234234 -> Node233645 -> Node2323429 -> Node2939230
Parent2: Node112938 -> Node2323429 -> Node2939230

如果我只是试图解析每个节点一次，而且只解析一次，无论它可能出现多少次，你会怎么做？

我考虑过使用 List.Contains，如果它是真的就停止，但它看起来有点乱；我考虑过使用 HashTable（我只是让添加节点），但我认为这在较大的树上可能效率很低。您认为什么是高效、快速的解决方案？

4

1 回答 1

0

** 编辑：** 再次阅读您的问题后，我有充分的理由相信我误解了它。在我看来，您实际上是在解析文本输入并从中创建一棵树。如果是这样，请忽略选项号。2.

我现在可以想到两种可行的方法：
1.使用布隆过滤器。如果您的树很大，那么在空间方面绝对值得，如果节点不重复太频繁，并且您可以容忍某些节点根本不被解析，它可能会满足您的需求。某些节点可能不会被解析，因为此结构可能会为属于运算符返回误报（从这个意义上说，它是一种概率数据结构）。查看其在维基百科上的页面以获取更多信息。

2.创建一个包含当前节点类的类的树，并添加一个布尔值，一旦访问该节点就设置为 true。例如： 

class NodeAndVisitationInfo {
    public bool Visited;
    public NodeType Node;

    public NodeAndVisitationInfo() {
        Visited = false;
    }
}

如果您需要多次执行此操作，则第二种解决方案可能并不理想，因为在这种情况下，您应该在再次运行访问算法之前为两棵树中的所有节点设置为Visited。false另外，请注意这个算法完全不是线程安全的。

最重要的是，不要List.Contains对每个新解析的节点进行简单的调用，对于最坏的情况，这将是 O(n^2)。如果您将节点存储在搜索结构中，请选择一个摊销插入和搜索复杂性都更好的结构。有序列表甚至哈希集可能会更好。

于 2013-01-07T03:16:03.603 回答