Algorithmus um zwei Bäume zu vegleichen

BitShift

Hallo,

ich habe die Aufgabe eine empfangene Datenstruktur (Baum A) gegen eine gespeicherte Definition (Baum zu prüfen und muss Fehler auszugeben.

Beide Datenstrukturen können als Bäume abgebildet werden.

Baum A soll sall also mit Baum B verglichen werden. Ich möchte alle Knoten von Baum A ausgeben die

[] in Baum A vorhanden sind, aber nicht in Baum B
[] in Baum A fehlen, aber in Baum B vorhanden sind
[*] deren Knotenwert sich zwischen Baum A von Baum B unterscheidet

Mein bisheriger Lösungansatz war es beiden Bäume rekursiv (in-order) zu traversieren und die Knoten zu vergleichen. Dabei komme ich aber immer beim Wechsel zwischen den Baumebenen durcheinander, wenn Knoten fehlen oder zusätzlich da sind.

Google ist zu dem Thema leider nicht sehr ergiebig. Dort habe ich bisher nur Antworten darauf gefunden wie man erkennt das zwei Bäume sich unterscheiden :-(.

Danke für jede Hilfe.

Gruß,
BitShift

Musst du nur sagen, ob Knoten fehlen oder auch ob sie an der gleichen Stelle sind? Für ersteres würden es ja auch schon zwei Listen tun. Oder musst du auch noch erkennen, ob ein gleicher Tailbaum an einer anderen Stelle hängt? Dann wirds deutlich aufwendiger.

BitShift

$ungenau$ schrieb:

Musst du nur sagen, ob Knoten fehlen oder auch ob sie an der gleichen Stelle sind? Für ersteres würden es ja auch schon zwei Listen tun. Oder musst du auch noch erkennen, ob ein gleicher Tailbaum an einer anderen Stelle hängt? Dann wirds deutlich aufwendiger.

Nö, ich muss nur sagen ob Knoten an einer bestimmten Stelle fehlen oder zuviel sind. Wenn ein Teilbaum an anderer Stelle hängt ist er an der einen Stekke zu wenig und an der anderen Stelle "zuviel". Er wird also zwei mal als Fehler erkannt. Im Grunde handelt es sich um eine reine Syntaxprüfung auf ein bestehendes Datenformat.

Hi, meine Idee wäre wenn du aus den beiden Bäumen zwei gepflanzte Bäume machst.
An deren Codes kannst du dann feststellen welche Teilbäume unterschiedlich aufgebaut sind.

Weitere Information zu gepflanzten Bäumen unter:
www.fernuni-hagen.de/mathematik/DMO/pubs/probe.pdf
Das Kapitel über isomorphe Bäume.

Gruß, Daniel_S

BitShift

Daniel_S schrieb:

Hi, meine Idee wäre wenn du aus den beiden Bäumen zwei gepflanzte Bäume machst.
An deren Codes kannst du dann feststellen welche Teilbäume unterschiedlich aufgebaut sind.

Weitere Information zu gepflanzten Bäumen unter:
www.fernuni-hagen.de/mathematik/DMO/pubs/probe.pdf
Das Kapitel über isomorphe Bäume.

Gruß, Daniel_S

Oh weh, das sieht aber ziemlich kompliziert aus . Ich schaue es mir mal an.

Tachyon

Sind die Bäume sortiert? Kannst Du sie iterierbar machen (im Sinne der Standardbibliothek)?
Wenn ja, dann bekommst Du mit std::set_difference von (A,B) und (B,A) die Differenzmengen Deiner Bäume. Die Vereinigung der Differenzmengen dürften Dann die Unterschiede sein.
Wenn das Kriterium der Sortiertheit gegeben ist, könntest Du die Datenstruktor evtl. mit einem Adapter iterierbarmachen, ohne sie ändern zu müssen. Wenn es die um den Algorithmus selbst geht, könntest Du mal in die Implementierung der STL-Funktionen std::set_difference und std::set_union gucken.

pumuckl

Gehts hier um binäre Bäume oder um allgemeine Bäume?
Bei allgemeinen Bäumen müsste man sich z.B überlegen, was es bedeutet, wenn der Knoten im A-Baum die Kinder 1,2,4 hat und der Knoten im B-Baum 1,2,3,4:

Möglichkeit 1: der Knoten "3" im A-Baum fehlt
Möglichkeit 2: der Knoten "4" im A-Baum heißt "3" im B-Baum, Knoten "4" im B-Baum fehlt im A-Baum

für Möglichkeit 1 müsste man die Knoten zuordnen, was recht komplex werden kann (je nach Daten in den Knoten), Möglichkeit 2 ist simpel.
Der Pseudocode für Möglichkeit 2 sähe z.B. so aus:

compare (AKnoten, BKnoten)
{
  if (Inhalt AKnoten != Inhalt BKnoten)
    melde Unterschied;

  countComp = min(Anzahl B-Kinder, Anzahl A-Kinder);
  diffKinder = Anzahl B-Kinder - Anzahl A-Kinder;
  if (diffKinder > 0)
    for (i = countComp..Anzahl B-Kinder)
      melde fehlendes A-Kind[i]
  else if (diffKinder < 0)
    for (i = countComp..Anzahl A-Kinder)
      melde fehlendes B-Kind[i]

  for (i = 0..countComp)
    compare(A-Kind[i], B-Kind[i])
}

}