AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Zurück Delphi-PRAXiS Programmierung allgemein Programmieren allgemein Binäre Bäume - Ausgabe von Elementen

Binäre Bäume - Ausgabe von Elementen

Ein Thema von DelphiGirl · begonnen am 20. Dez 2005 · letzter Beitrag vom 21. Dez 2005
Antwort Antwort
DelphiGirl

Registriert seit: 7. Nov 2005
4 Beiträge
 
#1

Binäre Bäume - Ausgabe von Elementen

  Alt 20. Dez 2005, 17:18
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ß
  Mit Zitat antworten Zitat
mumu

Registriert seit: 28. Okt 2003
Ort: Bamberg
519 Beiträge
 
#2

Re: Binäre Bäume - Ausgabe von Elementen

  Alt 20. Dez 2005, 17:43
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
  Mit Zitat antworten Zitat
Der_Unwissende

Registriert seit: 13. Dez 2003
Ort: Berlin
1.756 Beiträge
 
#3

Re: Binäre Bäume - Ausgabe von Elementen

  Alt 20. Dez 2005, 18:26
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
  Mit Zitat antworten Zitat
alzaimar
(Moderator)

Registriert seit: 6. Mai 2005
Ort: Berlin
4.956 Beiträge
 
Delphi 2007 Enterprise
 
#4

Re: Binäre Bäume - Ausgabe von Elementen

  Alt 20. Dez 2005, 19:06
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).
"Wenn ist das Nunstruck git und Slotermeyer? Ja! Beiherhund das Oder die Flipperwaldt gersput!"
(Monty Python "Joke Warefare")
  Mit Zitat antworten Zitat
DelphiGirl

Registriert seit: 7. Nov 2005
4 Beiträge
 
#5

Re: Binäre Bäume - Ausgabe von Elementen

  Alt 21. Dez 2005, 19:21
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.....
  Mit Zitat antworten Zitat
Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 21:58 Uhr.
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz