Binärbaum identisch < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | Gegeben sei ein binärbaum ganzen zahlen als einträge. SChreiben sie eine boolsche FUnktion equal( binaerbaum bb1, binaerbaum bb2), die 1 zurückgibt wenn bb1 und bb2 gleiche struktur haben und in entsprechenden knoten die gleichen elemente gespeichert sind und sonst 0. Die jeweiligen aktuellen knoten brauchen sich nicht zu entsprechen.
|
Neue Frage neues glück. Ich hab mir gedacht, um einen binärbaum eindeutig zu bestimmen muss ich ihn in zwei arten traversieren.z.B preorder und inorder. Wenn bb1 und bb2 bei beiden sachen das selbe liefern sind sie gleich wenn nicht nicht dann stimmt zumindest die struktur nicht. nun ist unser preorder(inorder auch) so aufgebaut das es jedes element einzeln ausgibt. Wie kann ich die ergebnisse der traversierungen vergleichen. ich hatte überlegt die einzelnen werte in eine liste zu schreiben und am ende die listen zu vergleichen. Hab ich nur nicht hinbekommen. Über hilfe wäre ich dankbar
Schöne Grüße
Blascowitz
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 16:17 Mi 01.08.2007 | | Autor: | Mumrel |
Hi blascowitz,
Eine weitere Idee wäre es, beide Bäume gleichzeitig zu durchlaufen.
Also z.B. Pre-/In./ oder Postordertraversierung und dabei vergleichen.
Die rekursive Variante der Traversierung müsste glaube ich nur minimal verändert werden.
Zur Aufgabestellung:
Die Bäume müssen die gleiche Struktur und den gleichen Inhalt haben?
Den letzten Satz versteh ich dann nämlich nicht:
> Die jeweiligen aktuellen knoten brauchen sich nicht zu entsprechen.
Grüße Mumrel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:44 Do 02.08.2007 | | Autor: | Mumrel |
Also ich möchte dann mal folgenden Vorschlag in den Raum stellen:
| 1: |
| | 2: | function equal (T1: Tree; T2 : Tree) return Boolean
| | 3: | {
| | 4: |
| | 5: | if T1 = null and T2 = null then
| | 6: | return True;
| | 7: |
| | 8: | elseif T1 /= null and T2 = null or
| | 9: | T1 = null and T2 /= null then
| | 10: | return False;
| | 11: |
| | 12: | elsif T1.Content /= T2.Content then
| | 13: | return False;
| | 14: |
| | 15: | else
| | 16: | return equal (T1.Left, T2.Left) AND
| | 17: | equal (T1.Right, T2.Right);
| | 18: |
| | 19: | end if;
| | 20: |
| | 21: | }
|
P.S. Tabs hab ich getippt, werden aber anscheinend nicht angezeigt..:(
|
|
|
|
