Binäre Bäume - Ausgabe von Elementen

[DelphiGirl]

Habe grad ein neues Thema in Info angefangen und es ist echt interessant.
doch habe ich bei 2 fragen auf meinem AB hackt es bei mir, vielleicht könnt ihr mir da etwas helfen.
wir sollen befehle für folgendes schreiben:
1. Ausgabe des kleinsten Elements vom binären Baum
2. Ausgabe der Tiefe eines vom binären Baums

bin jeden Tipp , hilfe dankbar. gruß

[mumu]

soweit ich noch weis:

1) immer von den zwei nachfolge knoten den kleineren wählen. bis keine nachfolge knoten mehr da, dann hast du das kleinste element
2) die ebene bekommt man glaub ich, wenn du immer den linken knoten wählst und pro knoten die ebenen nummer um eins erhöhst

[Der_Unwissende]

Hi,
es gibt an sich sehr viele Arten von Bäumen, soweit ich das noch richtig in Erinnerung habe, sagt Binärbaum nur aus, dass du pro Knoten max. 2 Kinder haben darfst.
Erst wenn du weitere Eigenschaften annimmst, stimmt das was mumu sagt.

So müsstest du eine Sortierung annehmen (in der Regel immer der Fall), nur dann muss jedes Element nach größe links oder rechts eingefügt werden.
Um die Höhe zu ermitteln, darfst du wiederum nur dann die linke Seite bis zum Ende runterlaufen, wenn der Baum ausgeglichen ist. Bei dieser Eigenschaft bin ich mir sogar sehr sicher, dass sie nicht für jeden Binärenbaum gilt.

Wenn du z.B. in einen Leeren Baum die Knoten 0, 1, 2, 3, ..., n einfügst, wächst dieser (mit angenommener Sortierung) nur nach rechts und entartet (du hast eine List). Die Höhe wäre hier n, wenn du aber die linken Elemente zählst, nun ja, gibt von der Wurzel aus kein einziges -> Höhe = 1 (Nur Wurzel).

Aber überleg dir ganz einfach mal was alles passieren kann. Es kann ja schließlich sein, dass so ein Baum nur links wächst, nur rechts oder ganz zufällig, erst gut links, dann irgendwo im linken rechts...
Denk dir einfach mal kurz aus, wie du nun die maximale Länge herausbekommst.

Kleiner Tipp noch, schau nicht irgendwo bei Google oder ähnlichem nach, die Idee wie du über einen Baum traversierst begegnet dir mehr als Häufig (auch gerne in Prüfungen, aber auch später immer wieder). Zu dem ist sie einfach, aber man muss sie einmal sehen (also selbst erkennen).
Was Bäume angeht, so ist es (und hier steht damit fast die Lösung) immer sehr Hilfreich Divide-and-Conquer zu benutzen. Schau dir an was für einen minimalen Baum gilt. Dann schau dir an, was für einen etwas größeren Baum gilt, ... Wie du feststellen wirst, besteht ein großer Baum eigentlich nur aus Teilbäumen, die schon kleiner sind und damit einfacher zu betrachten, irgendwann ist der Teilbaum so klein...

Gruß Der Unwissende

[alzaimar]

Noch ein Tipp: Rekursive Datenstrukturen (wie ein Binärbaum) kann man am einfachsten mit rekursiven Prozeduren verarbeiten.

Wir helfen Dir gerne, aber wie der Unwissende schon meinte, das muss man einfach 1x selbst hergeleitet haben.

Frage ruhig oder zeig mal Code (auch wenn er gar nicht funktioniert).

[DelphiGirl]

Zitat von Der_Unwissende:

Hi,
es gibt an sich sehr viele Arten von Bäumen, soweit ich das noch richtig in Erinnerung habe, sagt Binärbaum nur aus, dass du pro Knoten max. 2 Kinder haben darfst.
Erst wenn du weitere Eigenschaften annimmst, stimmt das was mumu sagt.

So müsstest du eine Sortierung annehmen (in der Regel immer der Fall), nur dann muss jedes Element nach größe links oder rechts eingefügt werden.
Um die Höhe zu ermitteln, darfst du wiederum nur dann die linke Seite bis zum Ende runterlaufen, wenn der Baum ausgeglichen ist. Bei dieser Eigenschaft bin ich mir sogar sehr sicher, dass sie nicht für jeden Binärenbaum gilt.

Wenn du z.B. in einen Leeren Baum die Knoten 0, 1, 2, 3, ..., n einfügst, wächst dieser (mit angenommener Sortierung) nur nach rechts und entartet (du hast eine List). Die Höhe wäre hier n, wenn du aber die linken Elemente zählst, nun ja, gibt von der Wurzel aus kein einziges -> Höhe = 1 (Nur Wurzel).

Aber überleg dir ganz einfach mal was alles passieren kann. Es kann ja schließlich sein, dass so ein Baum nur links wächst, nur rechts oder ganz zufällig, erst gut links, dann irgendwo im linken rechts...
Denk dir einfach mal kurz aus, wie du nun die maximale Länge herausbekommst.

Kleiner Tipp noch, schau nicht irgendwo bei Google oder ähnlichem nach, die Idee wie du über einen Baum traversierst begegnet dir mehr als Häufig (auch gerne in Prüfungen, aber auch später immer wieder). Zu dem ist sie einfach, aber man muss sie einmal sehen (also selbst erkennen).
Was Bäume angeht, so ist es (und hier steht damit fast die Lösung) immer sehr Hilfreich Divide-and-Conquer zu benutzen. Schau dir an was für einen minimalen Baum gilt. Dann schau dir an, was für einen etwas größeren Baum gilt, ... Wie du feststellen wirst, besteht ein großer Baum eigentlich nur aus Teilbäumen, die schon kleiner sind und damit einfacher zu betrachten, irgendwann ist der Teilbaum so klein...

Gruß Der Unwissende

Erstmal danke für die ganzen Tipps, nun komme ich auf auf das Angebot zurück mein "Code" anzugeben.

wenn ich nach dem D-C verfahren gehen würde dann würde ich meine Wurzel in 2 gleichgroße Bäume zerteilen , dies wiederrum in 2 Teilbäume zerlegen und am ende meine Teilbäume wieder zusammenfügen??
aber moment. ich kann meine wurzel doch nicht in 2 teiLEN?! wenn sagen wir mal meine wurzel der name : KURT ist und von ihm aus links Heinz und rechts UTE ausgeht, wie soll ich den dann die Wurzel in 2 teilen? bin was verwirrt....


aber wie kann ich dies als ein befehl aufschreiben? so z.B:
Wurzel in zwei Bäume unterteilen
dann.....