algorithm - 如何同时遍历两个任意复杂的树结构并创建一个超集？

Question

我有两个树结构，表示目录结构在两个不同时间点的快照。目录可能已在快照之间添加、删除或修改。我需要同时遍历两棵树，并用两者之间的差异标记较新的树——即将节点标记为新的、修改的、删除的、未更改的，添加任何已删除的节点，以便最终结果是两个快照的完整超集。

通常，树可能深约 10 层但非常宽，包含数十万甚至数百万个节点。我想通过比较每个节点的哈希码并仅在代码不匹配的地方继续递归来跳过大块树。

有没有算法可以成为我的 friend ？还有其他建议吗？

Answer 1

想象一下，将每棵树展开成一个已排序的文件和目录列表。一种方法可以从每棵展开的树中为那棵树获取下一个输入。然后我可以比较哈希码并在一棵树或另一棵树上向前跳转，注释删除和注释修改。