我已经实现了Zhang和Shasha的算法来计算两棵树之间的最小编辑距离。一切都很好，我对目前的运行时间感到非常满意。
现在我还想生成一个diff，突出显示更改/删除/插入的节点。根据他们的论文，要求获得计算出的距离的映射是非常自然的，根据本演示的最后几张幻灯片，似乎可以很容易地从最后一张森林距离表和树木距离表中提取映射。不幸的是，我还没能弄清楚确切的规则。
任何额外的描述都将不胜感激。非常感谢！
好吧，我终于自己解决了。为了为两棵树的节点生成最优映射，分别有m个和n个节点，您需要在林表中进行一些回溯。
对于（m，n）林距离表中以（m，n）开头的每个字段（x，y），请执行以下操作：如果最小值是通过将字段（x'，y'）和编辑/删除/插入成本相加获得的，则记下映射并转到当前林距离表的字段（x''，y''）。另一方面，如果最小值是通过将当前林距离表中的字段（x'，y'）和树距离表中字段（tx，ty）相加而获得的，则转到当前林距离表格中的字段"与"到与树（tx、ty）相对应的林表中的场域（tx）。现在，您需要分别在两个林表中继续回溯，并从这两个表中收集映射。