algorithm - 如何区分两棵树以确定 parent 的变化？

Question

我有一个树结构，我需要重新排列(拖放)然后提交更改。

捕捉变化的最佳方式是什么？在我看来，有两种方法:

1. 存储每个更改命令，提交更改列表然后执行每个命令
2. 序列化树，然后将新树与旧树进行比较，找出发生了什么变化，然后执行变化

1 似乎最容易实现，尽管如果发生许多重复操作(即多次拖动节点，但又将它们放回原处)可能会非常浪费

2 避免了上述问题，但我如何“区分”树来计算出要执行的 parent 更改命令？大概有这方面的算法？

编辑 澄清一下，每个节点都有一个“id”和一个“parentId”。我需要允许用户重新排列树(从而更改某些节点的 parentId)。

对于选项 2，如果简单地序列化更改的树就足够直接了，然后计算出差异，则按预定顺序遍历原始树，在新树中找到相同的节点，如果父节点是，则记录更改不同的？这是一种不会陷入循环的稳健方法吗？

编辑 其实不行，那行不通。我需要按顺序遍历新树并在旧树中找到相应的节点，然后比较父 ID 等。

Answer 1

除非树很大，否则删除旧树然后添加新树可能是最简单的。

当允许的操作包括移动、删除、添加时，区分两棵树将变得更加复杂，因此除非可以获得显着的好处，否则最好避免这种复杂性并使用简单的删除然后添加选项.