合并树节点

Question

有没有人知道一种算法，可以按以下方式合并树节点？

treeA
   \ child a
          \node(abc)
   \ child b
          \node(xyz)                   

         + 

treeB
   \ child a              
          \node(qrs)
   \ child b
          \node(xyz)
               \node(pdq)
   \ child c
          \node(pdq)

         = // do merge

treeMerged     
   \ child a
          \node(abc) 
          \node(qrs)
   \ child b
          \node(xyz)
               \node(pdq)
   \ child c
          \node(pdq)

非常感谢您的帮助。

- sbeskur

---

我知道这个问题很久远了，但是你是否为每个节点使用唯一的名称？如果是的话，这个问题有一个非常简单的解决方案...但我不确定是否应该发布它，因为它需要每个节点都有唯一的名称...无论深度如何，它都是无限的... - MaxOvrdrv

Answer 1

好的，一旦我真正花时间思考它，解决方案比我预期的要简单得多。(我在下面发布了代码的关键部分)

   private TreeNode DoMerge(TreeNode source, TreeNode target) {
        if (source == null || target == null) return null;

        foreach (TreeNode n in source.Nodes) {
            // see if there is a match in target
            var match = FindNode(n, target.Nodes); // match paths
            if (match == null) { // no match was found so add n to the target
                target.Nodes.Add(n);
            } else { 
                // a match was found so add the children of match 
                DoMerge(n, match);
            }

        }
        return target;

    }

还想知道是否有更好的解决方案吗？

- sbeskur

---

我希望你发布完整的解决方案。 - Edward Olamisan

无法用言语形容你没有添加剩余代码的烦恼。 - Frozenthia

Answer 2

我想到了一个递归的例子，适用于C#（我自己一直在使用），请注意，您需要找到一种方法将TreeNode.Nodes转换为数组：

public static TreeNode[] mergeTrees(TreeNode[] target, TreeNode[] source)
        {
            if (source == null || source.Length == 0)
            {
                return target;
            }
            if (target == null || target.Length == 0)
            {
                return source;
            }
            bool found;
            foreach (TreeNode s in source)
            {
                found = false;
                foreach (TreeNode t in target)
                {
                    if (s.Text.CompareTo(t.Text) == 0)
                    {
                        found = true;
                        TreeNode[] updatedNodes = mergeTrees(Util.treeView2Array(t.Nodes), Util.treeView2Array(s.Nodes));
                        t.Nodes.Clear();
                        t.Nodes.AddRange(updatedNodes);
                        break;
                    }
                }
                if (!found)
                {
                    TreeNode[] newNodes = new TreeNode[target.Length + 1];
                    Array.Copy(target, newNodes, target.Length);
                    newNodes[target.Length] = s;
                    target = newNodes;
                }
            }
            return target;
        }

- codemann8

Answer 3

好的，我承认，当我第一次开始尝试这个时，我并不认为它会太难，所以我决定尝试使用LINQ来完成它。虽然有点疯狂，但它确实有效。我相信还有更优雅和高效的算法，但这就是它！

首先，我在TreeNodeCollection类上有一个ToEnumerable扩展方法：

    public static class TreeNodeCollectionExtensions
    {
        public static IEnumerable<TreeNode> ToEnumerable(this TreeNodeCollection nodes)
        {
            foreach (TreeNode node in nodes)
            {
                yield return node;
            }
        }
    }

然后，我实现了一个自定义比较器：

公共类 TreeNodeComparer：IEqualityComparer { }

public bool Equals(TreeNode x, TreeNode y)
{
    return x.Text == y.Text;
}

public int GetHashCode(TreeNode obj)
{
    return obj.Text.GetHashCode();
}

最后，让我们来谈一谈疯狂的事情：

private TreeView MergeTreeViews(TreeView tv1, TreeView tv2)
{
    var result = new TreeView();
    foreach (TreeNode node in tv2.Nodes)
    {
        result.Nodes.Add(node.Clone() as TreeNode);
    }

    foreach (TreeNode node in tv1.Nodes)
    {
        var nodeOnOtherSide = result.Nodes.ToEnumerable()
            .SingleOrDefault(tr => tr.Text == node.Text);
        if (nodeOnOtherSide == null)
        {
            TreeNode clone = node.Clone() as TreeNode;
            result.Nodes.Add(clone);

        }
        else
        {

            var n = node.Nodes.ToEnumerable()
                     .Where(t => !(nodeOnOtherSide.Nodes.ToEnumerable()
                     .Contains(t, new TreeNodeComparer())));

            foreach (TreeNode subNode in n)
            {
                TreeNode clone = subNode.Clone() as TreeNode;
                nodeOnOtherSide.Nodes.Add(clone);
            }
        }
    }

    return result;
}

我的编码方式是返回第三个“合并”的treeView。您可以更改代码，使其以第三个treeView作为参数，以便您可以传递可能已经存在的treeView。

再次强调，我确信有更好的方法来做到这一点，但它应该能够工作。

还有一件事我想指出的是，这只适用于两层深度的TreeView。

- BFree

---

我非常赞赏你的努力。然而，我应该给出一个不同的例子，因为树可能有N层深度。你的代码给了我一些想法，我会看看能否想出什么东西。 - sbeskur

一个只支持两层深度的算法绝对是不可接受的。 - Edward Olamisan

Answer 4

如果您正在使用Node.Name属性来设置项目的实际路径，则合并相对简单。

首先，创建一个TreeNodeCollection扩展，如下所示（这是必需的，以便具有区分大小写的Find()方法用于TreeNodeCollection，从而确保唯一路径也可以通过大小写区分）：

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Windows.Forms;

namespace TreeViewApp
{
    public static class TreeNodeCollectionExtensions
    {
        public static TreeNode[] FindExact(this TreeNodeCollection coll, string keytofind)
        {
            TreeNode[] retval;

            if (String.IsNullOrWhiteSpace(keytofind) || coll == null)
            {
                retval = new TreeNode[0];
            }
            else
            {
                TreeNode[] badfinds = coll.Find(keytofind, true);

                List<TreeNode> goodfinds = new List<TreeNode>();
                foreach (TreeNode bad in badfinds)
                {
                    if (bad.Name == keytofind)
                        goodfinds.Add(bad);
                }
                retval = goodfinds.ToArray();

            }
            return retval;
        }
    }
}

第二步，使用您的源节点填充树视图...
第三步，使用您的目标节点填充树视图...
第四步，创建一个空的树视图。

然后，就像这样简单：

    private void btn_Merge_Click(object sender, EventArgs e)
    {
        //first merge
        foreach (TreeNode sourceNode in this.treeview_Source.Nodes)
        {
            FindOrAdd(sourceNode, ref this.treeview_Merged);
        }

        //second merge
        foreach (TreeNode targetNode in this.treeview_Target.Nodes)
        {
            FindOrAdd(targetNode, ref this.treeview_Merged);
        }
    }

    private void FindOrAdd(TreeNode FindMe, ref TreeView InHere)
    {
        TreeNode[] found = InHere.Nodes.FindExact(FindMe.Name);
        //if the node is not found, add it at the proper location.
        if (found.Length == 0)
        {
            if (FindMe.Parent != null)
            {
                TreeNode[] foundParent = InHere.Nodes.FindExact(FindMe.Parent.Name);
                if (foundParent.Length == 0)
                    InHere.Nodes.Add((TreeNode)FindMe.Clone());
                else
                    foundParent[0].Nodes.Add((TreeNode)FindMe.Clone());
            }
            else
                InHere.Nodes.Add((TreeNode)FindMe.Clone());
        }
        else
        {
            //if the item was found, check all children.
            foreach (TreeNode child in FindMe.Nodes)
                FindOrAdd(child, ref InHere);
        }
    }

再次强调，此解决方案仅适用于具有唯一路径的情况...使用扩展名时，还考虑了大小写的唯一性。

我在这里发布这篇文章，希望能帮助像我一样需要花费数天时间搜索解决方案却没有成功并不得不自己构建的人。

- MaxOvrdrv