Entwickler-Ecke :: Thema anzeigen - Non-Binary Tree-Klasse TreeNodes Mergen (zusammenführen)

IsNull - Mi 14.07.10 13:36
Titel: Non-Binary Tree-Klasse TreeNodes Mergen (zusammenführen)

Hallo,

Basierend auf folgender generischer Tree-Implementierung http://dvanderboom.wordpress.com/2008/03/15/treet-implementing-a-non-binary-tree-in-c/ habe ich meine Komplexe Treeklasse erweitert/bin daran sie zu erweitern.

Und eine der benötigten Erweiterungen ist, ein TreeNode in einen anderen Node zu mergen. Was ich damit meine habe ich in folgender Grafik visualisiert:
[url=http://a.imageshack.us/img718/9644/mergenodes.png] user defined image

[/URL]
Gleiche Elemente [der Vergleich zweier Nodes ist bereits implementiert durch Compare] (im gleichen SubTree) sollen also nicht verändert werden, jedoch müssen dann die ChildNodes wieder in den bestehenden gemerged werden -> rekursion, weil das unendlich tief sein kann.

Dazu habe ich folgende generische Methode zu schreiben begonnen, der Bereich in # eingeschlossen sind Versuche, aber an sich völlig funktionsunfähiger Code. Ich bringe die Rekursion nicht hin :/

C#-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:

/// <summary>Merges Node2Merge into the DestinationNode's childern.
        /// 
        /// </summary>
        /// <param name="Node2Merge"></param>
        /// <param name="DestinationNode"></param>
        public T MergeNode(T Node2Merge, T DestinationNode) {

            T MergedNode = (DestinationNode.Clone() as T);
            T MergedExistingNode;

            //step througt every existing node
            foreach (T ExistingNode in DestinationNode.Children) {
                if (Compare(ExistingNode, Node2Merge)) {
                    //if a existing node equals the Node2Merge-Root, we check if we have to merge childs of it.

                   //#############################################################################
                   //Does our Note2Merge have any childs which may has to be merged?
                   if(Node2Merge.Children.Count != 0){

                       //Take the active child (childoffset), and merge it with the [ExistingNode]
                       MergedExistingNode = MergeNode((Node2Merge.Children[childoffset] as T), ExistingNode);
                   }else{
                    return MergedNode; //remove the Node untouched.
                   }
                    /*
                    foreach (T NewNodeChild in Node2Merge.Children) {
                        return MergeNode(NewNodeChild, MergedNode);
                    }
                    */
                    //#############################################################################
                }
            }
            //the node is non existent - so we simply can add the full node tree here:
            MergedNode.Children.Add(Node2Merge);
            return MergedNode;
        }

Die Frage also ganz konkret: Wie geht man beim Mergen von zwei Non-Binary Trees vor, ein node hat die Eigenschaften:
Parent[parentnode | null]
Childern [list<node>]

Weiter habe ich der node-Klasse auch eine Deep-Copy Methode alias Clone() implementiert. Ich komme nur irgendwie nicht auf den richtigen Weg.

Ich bin dankbar für jeden Hinweis ;)
Grüsse

IsNull - Mi 14.07.10 22:05

Zitat:

Wenn nein, mehr Input bitte

Gerne doch :)

Jein. Es geht um foldendes:

Ich habe jede Menge von Trees. Einige von ihnen haben den gleichen "Beginn" wie andere Trees, spalten sich dann aber vom vorherigen Tree an einem Punkt (Node) ab. Ich brauche nun einen Haupt-Such Tree, in den alle meine Trees gemerged werden.

Zitat:

Geht es nur darum, den Root des ersten Baums im zweiten Baum wiederzufinden und dann die Schnittmenge der Kinder zu bilden?

Im zweiten Baum muss der Root des ersten nicht explizit gesucht werden(es müssen nicht alle childs rekurisv durchwandert werden), vielmehr muss nur in der ersten Child-Ebene nach dem root gesucht werden, aber wenn der neue root dort als child noch nicht exisitiert, dann kann der neue root mitsamt seiner Childs dem Hauptbaum angefügt werden. Das Mergen-Problem beginnt für mich aber, wenn das Root-Element (und evtl. eine teilmenge seiner childs) schon im Haupt-Tree vorhanden sind. Dann dürfen natürlich nur diese Childs des neuen geadded werden, welche auch wirklich noch nicht existieren.

Wenn du weitere Hinweise/Visualisierungen brauchst nur sagen, an dem soll es nicht scheitern.

ps: Hinweis zur Grafik: die Childs X,Y und auch deren childs a,b,c können natürlich selber beliebig viele eigene childs haben, und immer muss gleich vorgegangen werden -> daher die rekursion.

Kha - Mi 14.07.10 22:48

IsNull hat folgendes geschrieben :

vielmehr muss nur in der ersten Child-Ebene nach dem root gesucht werden

Ah, das war der entscheidende Hinweis. Dann sollte doch folgendes funktionieren:

C#-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:

def mergeNodeIntoChildren(source, dest):
  if source in dest.children:
    mergeNodes(source, dest.children[source])
  else:
    dest.children.add(source)

def mergeNodes(source, dest):
  for c in source.children:
    if c in dest.children:
      mergeNodes(c, dest.children[c])
    else:
      dest.addChild(c)

Ich hoffe, der Pseudocode ist verständlich - die Variante habe ich noch nie ausprobiert :mrgreen: .

...wenn die eigentlichen Bäume aber wirklich die "gleichen Anfänge" haben, also bloß gleiche Knoten in gleicher Tiefe gemergt werden müssen, stellt die erste Funktion natürlich nur einen Umweg dar, die zweite würde genügen.

IsNull - Do 15.07.10 07:55

Dein "dest.children[source]" war genau der Knackpunkt, jetzt hab ich es mit einer weiteren IsNodeInChildern(...) Methode einigermassen verständlich hinbekommen.

Danke dir :)

C#-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:

        public void mergeNodeIntoChildren(T source,T  dest){
            int childindex = 0;
            if ((childindex = IsNodeInChildern(source, dest)) != -1) {
                MergeNodes(source, (dest.Children[childindex] as T));
            } else {
                dest.Children.Add(source);
            }
        }


        public void MergeNodes(T source, T dest) {

            int childindex = 0;
            foreach (T sourcechild in source.Children) {

                if ((childindex = IsNodeInChildern(sourcechild, dest)) != -1) {
                    MergeNodes(sourcechild, (dest.Children[childindex] as T));
                } else {
                    dest.Children.Add((sourcechild.Clone() as T));
                }
            }
        }

        public int IsNodeInChildern(T node, T scannode) {
            int i = 0;
            foreach(T scannodechild in scannode.Children) {
                if(Compare(node, scannodechild)){
                    return i;
                }
                ++i;
            }
            return -1;
        }

Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2026 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!