我已经实现了 algorithm by Zhang and Shasha计算两棵树之间的最小编辑距离。一切正常，我对当前的运行时间非常满意。
现在我还想生成一个 diff，突出显示更改/删除/插入的节点。根据他们的论文，根据 this presentation 的最后一张幻灯片，要求生成计算距离的映射是很自然的。似乎可以很容易地从最后的森林距离表和树距离表中提取映射。不幸的是，我还没有弄清楚确切的规则。
任何额外的描述将不胜感激。非常感谢!
最佳答案
好吧，我终于自己弄明白了。为了为两棵树的节点生成最优映射，分别有 m 和 n 个节点，您需要在林表中进行一些回溯。
对于 (m, n) 森林距离表中以 (m, n) 开头的每个字段 (x, y)，执行以下操作:如果最小值是通过对字段 (x', y') 求和得到的和编辑/删除/插入成本，然后记下映射并转到当前森林距离表的字段(x'，y')。另一方面，如果最小值是通过当前森林距离表中的字段 (x', y') 和树木距离表中的字段 (tx, ty) 求和得到的，则转到字段 (x' , y') 从当前森林距离表 AND 到森林表中与树 (tx, ty) 对应的字段 (tx, ty)。您现在需要分别在两个林表中继续回溯并从两个表中收集映射。
关于algorithm - 树编辑距离 : How can I get the optimal mapping?，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/17915172/