Baum eerzeugen mit delphi

malibu85 · Beiträge: 51

Hallo liebe Freunde,

nachdem ich mich mit Listen beschäftigt habe möchte ich nun gern ein Suchbaum programmieren. Der Baum soll nach der Komponente Name geordnet sein. Das kleinste Element steht links. Ich habe die Baumstruktur schon erzeugt. Nun soll eine Procedure einen neuen Knoten einfügen. Dabei sollen der Baum wie oben schon erwähnt nach der Namen-Komponente angeordnet sein. Ich weiß nicht wie das gehen soll! Soll ich vergleichen welcher name der Kürzere ist oder nach dem Alphabet anordnen? Ich verstehe die aufgabenstellung nicht. Es ist eine Klausur aufgabe für die man 10min zeit hat. Ich würde gern wissen, wie man einen neuen knoten in den Baum einfügt sodass dieser an der richtigen stelle steht. Für Hinweise bin ich sehr dankbar.

Hier der Datentyp baum

markieren

Delphi-Quelltext

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

type t_zeiger = ^t_knoten;

     t_inhalt = record
        name: string[30];
        nummer:integer;
        masse: real;
     end;

     t_knoten = record
       inhalt: t_inhalt;
       links:  t_zeiger;
       rechts: t_zeiger;
     end;


var
  Form1: TForm1;
  z_aktuell: t_zeiger;
  z_wurzel : t_zeiger;

implementation

Moderiert von Gausi: Quote- durch Delphi-Tags ersetzt

Gausi · Verfasst: Di 23.09.08 12:03

Naja, mit kleiner dürfte das normale string-kleiner gemeint sein, also eine alphabetische Sortierung. Ob mit oder ohne Berücksichtigung der Groß-/Kleinschreibung ist da erstmal egal. ;-)

Das Einfügen geht einfach so: Starte bei der Wurzel. Wenn das neue Element größer ist als das Element in der Wurzel, dann überprüfe den rechten Nachfolger der Wurzel, sonst den linken. Fahre damit fort, bis man an einem Blatt angelangt ist - und da kommt dann das neue Element hin.

_________________
We are, we were and will not be.

malibu85 · Beiträge: 51

okay danke das sollte ich hinbekommen aber wie mache ich das mit dem vergleich der beiden strings. Man kann zwar strings mit einander vergleichen aber so wie ich das sehe funktioniert das nur mit dem ersten Zeichen eines Strings. Muss ich dazu ne extra procedure schreiben oder gibts da was von ratiopharm

Ehemaliges Mitglied Erhaltene Danke: 1

in welchem forum willst du jetzt die antworten? :eyecrazy:

Gausi · Verfasst: Di 23.09.08 12:11

Nö, soweit ich weiß, geht einfach if string1 < string2 then .... Alternativ kann man auch Funktionen wie (Ansi)CompareText oder (Ansi)CompareString nehmen. Ist zwar nicht in der Unit ratiopharm drin, sondern in StrUtils oder SysUtils (die Delphihilfe weiß das aber), aber das sollte auch helfen. ;-)

_________________
We are, we were and will not be.

malibu85 · Beiträge: 51

okay dann mach ich mich mal ran!! danke für den Hinweis!

malibu85 · Beiträge: 51

Hallo Freunde,
ich poste noch die Teilösung zu diesem Thema. Damit möchte ich anderen Programmieranfängern eine Hilfestellung geben. Es darf gern kritisiert werden. die Folgene Typendeklaration legt den Datentyp eines Baums fest. Die anschließenden Prozeduren fügen neue Knoten hinzu und ordnet diese. Demnächt werde ich noch baumoperationen ergänzen. Wer dazu was beizutragen hat...immer her damit.

markieren

Delphi-Quelltext

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

type p_zeiger= ^node;

     t_inhalt= record
       name: string[30];
       nummer: integer;
       masse:integer;
     end;

     node = record
       inhalt:t_inhalt;
       links:p_zeiger;
       rechts:p_zeiger;
     end;


var
  Form1: TForm1;
  root:p_zeiger;
  v_satz:t_inhalt;

implementation

Prozeduren zum einlesen und zum anhängen von Knoten bzw blätter

markieren

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:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:

procedure einlesen;
begin
  with form1 do
  begin
    with v_satz do
    begin
    name:=edit1.text;
    nummer:=StrToInt(edit2.text);
    masse:=StrToInt(edit3.text);
    end;
  end;
end;

procedure create_root_element(v_satz:t_inhalt);
begin
New(root);
root^.inhalt:=v_satz;
root^.links:=NIL;
root^.rechts:=NIL;
end;

procedure anhaengen(p_vergleichselement:p_zeiger; v_satz:t_inhalt);
var neues_element:p_zeiger;
begin
  if (p_vergleichselement = NIL) then
  begin
  create_root_element(v_satz);
  end
  else
  begin
    if (p_vergleichselement^.inhalt.name >= v_satz.name) then
    begin
      if (p_vergleichselement^.links = NIL)then
      begin
      NEW(p_vergleichselement^.links);
      neues_element:=p_vergleichselement^.links;
      neues_element^.inhalt:=v_satz;
      neues_element^.links:=NIL;
      neues_element^.rechts:=NIL;
      end
      else
      begin
      anhaengen(p_vergleichselement^.links,v_satz);
      end;
    end
    else
    begin
      if (p_vergleichselement^.rechts = NIL)then
      begin
      NEW(p_vergleichselement^.rechts);
      neues_element:=p_vergleichselement^.rechts;
      neues_element^.inhalt:=v_satz;
      neues_element^.links:=NIL;
      neues_element^.rechts:=NIL;
      end
      else
      begin
      anhaengen(p_vergleichselement^.rechts,v_satz);
      end;
    end;
  end;
end;

Moderiert von Narses: Code- durch Delphi-Tags ersetzt

DaVinciFF7 · Beiträge: 32 Win XP Delphi 2007

Also wenn es dir etwas helfen sollte, hier mal ein Suchbaum aus der Schule ^^

markieren

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:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:

unit Unit1;
interface
uses
  Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,
  StdCtrls, Buttons;
const leerBaum=nil;
type
TStrBaum= class(TObject)
          eintrag   :string;
          anzahl    :integer;
          links     :TStrBaum;
          rechts    :TStrBaum;
          constructor pflanzen(wort: string);
          procedure einfuegen(var wo: TStrBaum; wort: string);
          procedure ausgeben;
        end;

 TForm1 = class(TForm)
    Ausgabe: TListBox;
    Eingabe: TEdit;
    EingabeLabel: TLabel;
    EingabeBtn: TBitBtn;
    AusgabeBtn: TBitBtn;
    Memo1: TMemo;
    Button1: TButton;
    procedure FormCreate(Sender: TObject);
    procedure EingabeBtnClick(Sender: TObject);
    procedure AusgabeBtnClick(Sender: TObject);
    procedure EingabeKeyPress(Sender: TObject; var Key: Char);
    procedure Button1Click(Sender: TObject);
  private { Private-Deklarationen } public { Public-Deklarationen }
  end;

var
  Form1: TForm1;
  Baum: TStrBaum;

implementation  {$R *.DFM}

constructor TStrBaum.pflanzen(wort: string);
begin
   TObject.create;
   anzahl:=1; links:=leerBaum; rechts:=leerBaum; eintrag:=wort;
end;

procedure TStrBaum.einfuegen(var wo: TStrBaum; wort: string);
     {der Zeiger auf den Baum muss offerbar (zusätzlich)´als var-Parameter}
     {übergeben werden, da self strikt lokal ist. (Ob das elegenter geht??)}
begin
 if wo=leerBaum then wo:=TStrBaum.pflanzen(wort) {erstelle neues Blatt}
 else with wo do if wort<eintrag then
 links.einfuegen(links, wort)
      else if wort>eintrag then rechts.einfuegen(rechts, wort)
           else inc(anzahl);
end; {einfuegen}

procedure TStrBaum.ausgeben;
var zeile: string;
begin
  if assigned(self) then   {gleichwertig mit self<>leerBaum}
      begin
         links.AUSGEBEN;
         zeile:=IntToStr(anzahl);
         zeile:=copy('      '+zeile,6-length(zeile),6)+'  '+eintrag;
         Form1.Ausgabe.items.add(zeile);

         rechts.AUSGEBEN;
      end;
end;  { ausgeben }


procedure TForm1.FormCreate(Sender: TObject);
begin
   baum:=nil;    {Wichtig, da es sonst nicht möglich ist, vor dem Zugriff}
end;             {auf baum.eintrag zu prüfen, ob er nicht ins Leere geht.}

procedure TForm1.EingabeBtnClick(Sender: TObject);
begin
   if Eingabe.text<>'' then Baum.einfuegen(Baum, Eingabe.text);
   Eingabe.clear;  ActiveControl:=Eingabe;
end;

procedure TForm1.AusgabeBtnClick(Sender: TObject);
begin
  Ausgabe.clear;  Baum.ausgeben;  ActiveControl:=Eingabe;
end;

procedure TForm1.EingabeKeyPress(Sender: TObject; var Key: Char);
begin
  if key in[#13{RETURN},#32{Sapce}] then EingabeBtnClick(sender);
end;

end.

Moderiert von Gausi: Delphi-Tags hinzugefügt

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme