Non-Binary Tree-Klasse TreeNodes Mergen (zusammenführen)

IsNull · Beiträge: 97 Erhaltene Danke: 11 VS 2010, C#, AHK

Hallo,

Basierend auf folgender generischer Tree-Implementierung dvanderboom.wordpres...on-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=a.imageshack.us/img7...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 :/

markieren

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

Kha · Verfasst: Mi 14.07.10 20:53

Hm. Geht es nur darum, den Root des ersten Baums im zweiten Baum wiederzufinden und dann die Schnittmenge der Kinder zu bilden? Wenn nein, mehr Input bitte

. Ich kann mir noch nicht vorstellen, wo und wie mehrere Merge-Schritte ablaufen sollen.

_________________
>λ=

IsNull · Beiträge: 97 Erhaltene Danke: 11 VS 2010, C#, AHK

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 · Verfasst: 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:

markieren

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 · Beiträge: 97 Erhaltene Danke: 11 VS 2010, C#, AHK

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

Danke dir

markieren

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

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme