Entwickler-Ecke :: Thema anzeigen - Binärbaum in Listbox ausgeben

Eike89 - Mo 18.02.08 21:16
Titel: Binärbaum in Listbox ausgeben

Hallo,

ich habe die Aufgabe einen Binärbaum durch eine rekursive Prozedur ausgeben zu lassen. Ich weiß zwar, wie das ungefähr geht, aber ich bekomme nichma den Anfang hin....Es geht um Objekte von Typ TOjekt und die Nachfolger heißen LinkerNachfolger und RechterNachfolger.

Hoffe ihr könnt mir helfen

Eike

Edit:
hab ich ganz vergessen: es soll so ausgegeben werden:
Baum:

20
15 35
12 17 32 40

memo:
12
15
17
20
32
35
40

Eike89 - Mo 18.02.08 21:26

joar das is uA auch nen Problem. Wir haben uns zuletzt mit Listen beschäftigt und sollen den Quellcode jetzt umbauen. Da wir hauptsächlich mit UMLed arbeiten sind die wichtigen Prozeduren sind ausgelagert. Wir haben bisher weder eine Hinzufügen-Prozedur noch eine Lösche-Prozedur geschrieben....das kommt nächste Stunde -.-.

Ansonsten sieht der Quellcode so aus:

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:

var
  Form1: TForm1;
  Baum: TBaum;

implementation

{$R *.DFM}

procedure TForm1.FormCreate(Sender: TObject);
begin
  Baum := TBaum.Initialisiere;
end;

procedure TForm1.Button3Click(Sender: TObject);
begin
  Close;
end;

procedure TForm1.Listbox_ausgeben;
Var Element : TObjekt;
Begin
// ???
End;

end.

Das is so der wichtige Teil denke ich.

Moderiert von Narses: Code- durch Delphi-Tags ersetzt

---Moderiert von Narses: Beiträge zusammengefasst---

ach sehe gerade es soll eine Listbox sein...aber denke das dürfte keinen Unterschied machen.

Jann1k - Mo 18.02.08 22:32

okay dann schreib ich euch mal den grobalgorithmus, den in delphi zu übersetzen sollte leicht sein (das ist eine prozedur der klasse Tbaum, die muss dafür die listbox kennen):

prozedur tbaum.ausgeben:

1. gucken ob ein linker teilbaum existiert, wenn ja die prozedur ausgeben vom linken Teilbaum aufrufen.

2. den wert des knotens in die listbox schreiben.

3. gucken ob ein rechter Teilbaum existiert, wenn ja die prozedur ausgeben vom rechten teilbaum aufrufen.

Eike89 - Mo 18.02.08 22:53

also ich hab was geschrieben:

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:

procedure TForm1.Listbox_ausgeben;
Var Element : TObjekt;
Begin
Element := Baum.Aktuell;
if Element.LinkerNachfolger <> nil
 then
  Listbox_ausgeben;
  Listbox1.lines.add(Element.Inhalt);
 if Element.RechterNachfolger <> nil
  then
   listbox_ausgeben;
   listbox1.lines.add(Element.Inhalt);
End;

ich glaube aber, so kommt die rekursion nich zustande....leider kann ichs nicht ausprobieren, wo er hängenbleibt, weil das restlichte programm nicht feritg is...

unser lehrer hat uns auch mal die prozedur gezeigt...irgenwie so sah sie auch aus...aber ich kann mich nichmer richtig dran erinner. wies gehen soll ist mir eigentlich klar, aber ich weiß nicht, wie ichs umsetzten kann.

Danke für deine Hilfe!!

Eike89 - Mo 18.02.08 23:06

nich NUR falsch hört sich ja schonma positiv an^^

hab das geändert, wie dus geschrieben hast, glaube zumindest, dass du es so meinst. und nü?^^

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:

procedure TBaum.Listbox_ausgeben;
Var Element : TObjekt;
Begin
Element := Baum.Aktuell;
if Element.LinkerNachfolger <> nil
 then
  TBaum.Listbox_ausgeben;
  Listbox1.lines.add(Element.Inhalt);
 if Element.RechterNachfolger <> nil
  then
   TBaum.listbox_ausgeben;
End;

Eike89 - Mo 18.02.08 23:14

ja hab das grade auch noch gesehen, dass ichs oben noch als prozedur von tform1 deklariert hatte. aber ich glaube, dass es so sein soll. es geht hauptsächlich um diese rekursive sache. dazu is es doch egen, woher die prozedur kommt oder?

[url=http://img402.imageshack.us/my.php?image=baumlw4.jpg] user defined image

[/URL]

ach ich vergesse immer was dazu zu schreiben. also das prog heißt UMLed und man kann damit klassen und darin enthaltene funktionen/prozeduren usw recht einfach erzeugen. so haben wir die klasse TBaum erstellt, aber die enthaltenen Prozeduren/Funktionen sind zum Teil nicht belegt.

Eike89 - Mo 18.02.08 23:31

also wenn ich mich nicht komplett irre, sieht es so aus:

jedes element des baumes ist von der klasse TObjekt.

wie es mit der Klasse TBaum aussieht verstehe ich gerade beim überlegen selber nicht richtig. Also mit den Prozeduren dieser Klasse wollen wir auf den Baum zugreifen. also ist glaube ich die klasse TObjekt an die Klasse TBaum vererbt worden....vor allem, weil die Pointer in TBaum TObjekte enthalten.

ich hänge dir mal alles an, was ich habe. das Prog is frei erhältlich:

UMLed 1.8.4:
http://www.kubitz-online.de/UMLed/index.html#Downloads

Xong - Di 19.02.08 09:30

Du hast einen simplen Binäerbaum.

Du durchläufst in dem Algorithmus alle Knoten des Baumes. Dabei können mehrere unterschiedliche Ereignisse auftreten:

Der Knoten hat einen linken Teilbaum.
Der Knoten hat einen Rechten Teilbaum.

Der Algorithmus:
Zunächst musst du dir überlegen, in welcher Reihenfolge die Elemente ausgegeben werden sollen.
Beispiel:

Quelltext

1:
2:
3:
4:
5:

Möglich sind u.a.:

Alle Werte von Links nach Rechts.
4 2 5 1 3 6
Alle Werte von Rechts nach Links.
6 3 1 5 2 4
Alle Werte von der Mitte ausgesehen.
1 2 3 4 5 6

Algorithmus für [3]:

Wenn der linke Teilbaum nicht leer ist: Übergebe linken Teilbaum an die Funktion.
Gebe den Wert des Knotens aus bzw. schreibe ihn in die Listbox.
Wenn der rechte Teilbaum nicht leer ist: Übergebe rechten Teilbaum an die Funktion.

Das wars schon.

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:

procedure TBaum.Baum2List(Knoten: TObjekt)
begin
  // Linker Teilbaum wird untersucht
  if Knoten.Links <> nil
    Baum2List(Baum.Links);
  // Wert des Knotens wird ausgegeben
  Listbox.Items.Add(Knoten.Inhalt.Text); // Ich weiß nicht, was TInhalt für ein Typ ist.
  // Rechter Teilbaum wird untersucht
  if Baum.Rechts <> nil
    Baum2List(Knoten.Rechts);
end;

LG,
Xong

Eike89 - Di 19.02.08 10:30

Danke euch!!
Mein Code sieht nun so aus:

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:

procedure TForm1.Listbox_ausgeben(Element:TObjekt);
Begin
if Element.LinkerNachfolger <> nil
 then
  Listbox_ausgeben(Element.LinkerNachfolger);
  Listbox1.Items.Add(Element.Inhalt);
 if Element.RechterNachfolger <> nil
  then
   listbox_ausgeben(Element.RechterNachfolger);
End;

Die Prozedur ist immernoch eine Prozedur in TForm1.
Ich hab keine Ahnung obs funktioniert, aber denke es müsste richtig sein.

Xong - Di 19.02.08 10:36

Wenn du es noch richtig formatierst, wird der Code sogar lesbar!

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:

procedure TForm1.Listbox_ausgeben(Element:TObjekt);
begin
  if Element.LinkerNachfolger <> nil then
    Listbox_ausgeben(Element.LinkerNachfolger);
  
  Listbox1.Items.Add(Element.Inhalt);

  if Element.RechterNachfolger <> nil then
    listbox_ausgeben(Element.RechterNachfolger);
end;

Ist Element.Inhalt denn ein String?

Eike89 - Di 19.02.08 11:08

naja im moment eher garnicht, aber ansonsten immer nur über:

Code in der Klasse TListe:

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:

procedure TList.FuegeEinNach (Inhalt: TInhalt);
Var neues_Element : TObjekt;
begin
 neues_Element := TObjekt.Create;
 neues_Element.Inhalt := Inhalt;
 If leer = false then
  begin
   neues_Element.Nachfolger := Aktuell.Nachfolger;
   Aktuell.Nachfolger := neues_Element;
  end
  else begin
   neues_Element.Nachfolger := Nil;
   Wurzel := neues_Element;
  end;
 Aktuell := neues_Element;
end;

Code in TForm1

Delphi-Quelltext

1:
2:
3:
4:
5:
6:

  With Liste Do
    Begin
      FindeLetztes;
      FuegeEinNach(Edit1.Text);
    End;
  Listbox_ausgeben;

also wir füren es als String ein...wenn das deine Frage beantworet :gruebel: ...Die Codes sind aus dem Vorgängerprogramm, in dem wir mit Listen gearbeitet haben.

Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!