Merging Treenodes

Question

Does anyone know of an algorithm that will merge treenodes in the following way?

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)

Any help would be greatly appreciated.

Answer 1

Ok, I'll admit, when I first started messing with this, I didn't think it would be too hard, so I figured I'll try to do it using LINQ. It came out to be nuts, but it works. I'm SURE there are more elegant and efficient algorithms, but here it is!

First, I have a ToEnumerable extension method on the TreeNodeCollection class:

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

Then, I implement a custom comparer:

public class TreeNodeComparer : IEqualityComparer {

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

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

}

And finally, the crazyness:

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;
}

The way I coded it was that it returns a third "merged" treeView. You can change the code, so that it takes a third treeview as a parameter, so that you can pass in a treeView you may already have.

Again, I'm SURE there are better way to do this, but it SHOULD work.

One more thing I'd like to point out, this will only work for a TreeView that is two layers deep.

Answer 2

Well, once I actually took the time to think about it, the solution turns out to be far more simple than I anticipated. (I've posted the critical part of the code below)

   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;

    }

Still interested to know if someone has a better solution?