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.....