c# - 将原始树合并到结果树的步骤

Question

具有原始 和“最终”/结果 树。我想比较这些树并“重现”这些步骤，这些步骤将得到相同的结果。

现实生活中的例子: 在数据库中有原始树。工作人员已经准备好更改(在 App 中生成新的结果树)，现在我们需要更新数据库。我们无法删除数据库并重新上传，因为可能有尚未生成的数据。

类/表定义:

class TreeNode
{
    public string Text { get; set; }
    public TreeNode Parent { get; set; }

    /* some other properties */
}

示例树:

Origin                         Result
|A                              |A
| -1                            | -2
| -2                            |C
|B                              | -3
| -5                            |D
|  --£                          | -1
|C                              |  --£
|F                              | -5
| -7                            |E
|H                              | -6
                                |G
                                | -4
                                |H

我希望有一个算法，当对象被添加、删除或移动时，我将被允许处理.

IMPORTANT: The objects that have other parent should not be removed and added back, instead they should be only moved under other parent! Remove would cause data loss.

例子:

Mark B as removed
Mark F as removed
Add D
Add E
Add G
Move 1 under D
Move 5 under D
Mark 7 as removed
Add 3 under C
Add 6 under E
Add 4 under G
Move £ under 1
Removed 7
Removed F
Removed B

---

自己的解决方案

我使用 Win-Forms 和 TreeView 创建了示例。我的算法仅适用于每个级别的基础(例如，将 1 从 A 移动到 D)，但不能跨越。元素是先行删除，最后删除。

代码:

//Recursive loop to find all nodes in Nth level
private IEnumerable<TreeNode> getNodesOnLevel(TreeNodeCollection aCollection, int aLevel)
{
    var lResultTreeNodeCol = new List<TreeNode>();

    if (aLevel == 1)
        return aCollection.Cast<TreeNode>();

    foreach(TreeNode nNode in aCollection)
    {
        lResultTreeNodeCol.AddRange(getNodesOnLevel(nNode.Nodes, aLevel - 1));
    }

    return lResultTreeNodeCol;
}

//Called once
public void UpdateTrees(TreeNodeCollection aCollectionA, TreeNodeCollection aCollectionB)
{
    List<TreeNode> lRemoved = new List<TreeNode>();
    for (int i = 1; UpdateWithLevel(aCollectionA, aCollectionB, i, ref lRemoved) > 0; i++)
    {
    }
    var lRem = lRemoved.LastOrDefault();
    do
    {
        W($"Removed {lRem.Text}");
        lRemoved.Remove(lRem);
    } while ((lRem = lRemoved.LastOrDefault()) != null);

}

//Called per level
private int UpdateWithLevel(TreeNodeCollection aCollectionA, TreeNodeCollection aCollectionB, int level, ref List<TreeNode> aRemoved)
{
    int lNumOfUpdates = 0;
    var colA = getNodesOnLevel(aCollectionA, level);
    var colB = getNodesOnLevel(aCollectionB, level);

    //Search Original collection, compare to Result collection
    foreach (TreeNode nodeA in colA)
    {
        //Find nodeA in Result collection
        var lNodeAinColB = colB.FirstOrDefault((a) => a.Text == nodeA.Text);

        if(lNodeAinColB == null) //NodeA not found in result collection - delete
        {
            aRemoved.Add(nodeA);
            W($"Mark {nodeA.Text} as removed");
            lNumOfUpdates++;
        }
        else if((lNodeAinColB.Parent?.Text ?? "") != (nodeA.Parent?.Text ?? "")) //NodeA exists in Result collection, different parrent -> must be moved
        {
            W($"Move {nodeA.Text} under {lNodeAinColB.Parent.Text}");
            lNumOfUpdates++;
        }
    }

    //Search Result collection, if Original collection does not have nodeB, we must create it (add)
    foreach (TreeNode nodeB in colB)
    {
        if (!colA.Contains(nodeB, new TestNodeEquality()))
        {
            W($"Add {nodeB.Text}" + ((nodeB.Parent != null)?$" under {nodeB.Parent.Text}":""));
            lNumOfUpdates++;
        }
    }

    return lNumOfUpdates;
}

我没有找到任何适合我的问题的主题，也没有找到有值(value)的资源，我真的很想避免重新发明轮子。

问题:

• 是否有现有的和有效的算法(名称/引用)？这种算法/ Action 叫什么(Tree Diff/Merge/Lookup/..)？

• 我能以任何方式优化算法吗？

Answer 1

我不认为你在这里需要一些复杂的递归算法。只需将结果节点放入 name-parent 字典并检查:

• 原始节点是否在字典中
• 原节点的父节点是否改变
• 结果中是否有原始节点中不存在的节点

Dictionary 也提供了 O(1) 来搜索节点，所以这也是一种优化。同样涉及Except操作，即快速设置操作。

代码:

var originalNodes = new List<TreeNode>(); // TreeNodeCollection 
var nodes = new List<TreeNode>();         // TreeNodeCollection 
var parentByName = nodes.ToDictionary(n => n.Text, n => n.Parent);

foreach(var originalNode in originalNodes)
{
    TreeNode parent;
    if (!parentByName.TryGetValue(originalNode.Text, out parent))
    {
        // removed - there is no key for original node name
        continue;
    }

    if (originalNode.Parent?.Text != parent?.Text)
    {
        // moved from originalNode.Parent to parent
        continue;
    }
}

// these guys are added
var added = parentByName.Keys.Except(originalNodes.Select(n => n.Text))