如何区分两棵树以确定父母的变化? [英] How to diff two trees to determine parental changes?

问题描述

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

I've got a tree structure that I need to rearrange (drag and drop) and then submit the changes.

捕获更改的最佳方法是什么?在我看来，有两种方法:

What's going to be the best way to capture the changes? As I see it there are two ways:

1. 存储每个更改命令，提交更改列表，然后执行每个更改
2. 序列化树，然后将新树与旧树进行比较以找出更改的内容，然后执行更改

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

1 seems easiest to implement, although it could be very wasteful if many repetitive actions have occurred (i.e. dragging nodes around many times, but putting them back where they started)

2避免了上述问题，但是我怎么能差异"?找出要执行哪些父母变更命令的树?大概有算法吗?

2 avoids the above problem, but how can I "diff" the trees to work out what parental change commands to execute? Presumably there are algorithms for this?

编辑为了明确起见，每个节点都有一个"id"和"parentId".我需要允许用户重新排列树(从而更改某些节点的parentId).

Edit To clarify, every node has an "id" and a "parentId". I need to allow users to rearrange the tree (thereby changing the parentId of some nodes).

对于选项2，是否应该足够简单明了地简单地序列化更改后的树，然后按顺序计算出对原始树的迭代，在新树中找到相同的节点并记录更改(如果父级为不同的?是一种不会陷入困境的可靠方法吗?

For option 2, should it be straightforward enough to simply serialize the changed tree, then to work out the differences iterate over the the original tree in preorder, find the same node in the new tree and record a change if the parents are different? is that a robust approach that won't get stuck in a cycle?

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

Edit actually no, that won't work. I need to iterate over the NEW tree in preorder and find the corresponding node in the old tree, then diff parent ids etc..

推荐答案

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

Unless the trees are huge it might be easiest simply to delete the old tree and then add the new tree.

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

Differencing two trees when the allowed operations include moves, deletes, adds is going to be much more complex so unless there is a significant benefit to be gained it's probably best to avoid that complexity and use a simple remove-then-add option.

这篇关于如何区分两棵树以确定父母的变化?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！