algorithm - 确定 Treeview 中的最小变化

Question

我有一个 TreeView ，用户可以在其中移动、删除子树、节点和创建节点。

我不想一次坚持每一个 Action ，但用户可以说“应用我的更改”。因此，我需要将新树与旧树进行比较——最重要的是——确定构建新树的最小操作集。解决这个问题的方法是什么？

我使用的是 ASP.NET/C#，但问题与该技术并不紧密。

谢谢

Answer 1

有两种方法可以解决您的问题。您可以只缓存所有用户的编辑操作，然后在批量更新中应用它们。这解决了您目标的“不是一次”部分。

如果您想用一组产生相同结果的最佳操作替换用户操作(对于“最佳”的某些定义)，这通常是一个非常难以解决的问题。我认为，最著名的算法是基于一种叫做“树之间的编辑距离”的东西，并在 technical report by Zhang and Shasha 中进行了描述。 .请注意，这是非常密集的阅读。有一篇更具可读性的文章 here寻找最佳编辑脚本将一个 XML 文档更改为另一个 XML 文档。它基于首先将 XML 转换为树并对其进行处理，因此核心算法可能直接适用于您的问题。它甚至带有伪代码。