c++ - 使用树的序列化和为每个子树生成唯一 id 的树匹配

Question

序列化给定二叉树并反过来评估每个序列化二叉树的唯一 ID 的最佳方法是什么？

例如，我需要序列化子树 (2,7,(5,6,11)) 并生成代表该子树的唯一 id ' x '，这样每当我遇到类似的子树 (2 ,7,(5,6,11)) 它将序列化为相同的值“ x ”，因此我可以推断出我找到了匹配项。

在这里，我们假设每个节点都具有唯一的属性。在上面的示例中，它将是分配给每个节点的数字，因此它们总是会为相似的子树生成相同的 id。我正在尝试在 C++ 中执行此操作。

是否已经存在执行这种序列化树匹配的算法？

score 2 · Accepted Answer

您是否希望能够匹配树的任意部分或运行到某个叶节点的子树？IIUC，您正在查看后缀匹配。

您还可以查看 Compact Directed Acyclic Word Graph 的想法。

score 2 · Accepted Answer

我会根据节点的 ID 和树中的位置创建一个哈希值（以某种 Rabin-Karp 方式），即：

long h = 0
for each node in sub tree:
    h ^= node.id << (node.depth % 30)

在伪代码中。缺点是不同的子树可能产生相同的哈希值。但优点是比较哈希值很快，当找到匹配时，您可以进一步调查实际的子树是否相等。

score 1 · Accepted Answer

如果您不追求高效率，您可能需要使用非常简单的深度优先搜索算法。

"2,7,2,U,6,5,U,11,U,U,U,5,9,4"

如您所见，我添加了 U 命令（“up”）以显示下一个孩子将在哪里创建。当然，您可以提高效率，但我相信这是一个开始。

此外，您可能想看看Boost.Graph (BGL) 的实现。

score 1 · Accepted Answer

1

像您在问题中使用的括号符号有什么问题？

于 2009-03-29T10:05:45.313 回答

4 回答 4