Binärer Suchbaum mit Zeichenketten

Anjitsch · Hält's aus hier Beiträge: 8

Halli Hallo,
ich habe ein Problem.
Wir haben im Unterricht ein Binären Suchbaum mit Zahlen vorgegeben bekommen und sollen ihn so umändern, dass Zeichenketten eingegeben, gespeichert und geladet werden können.
Die vorgegebene Unit:

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:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:
111:
112:
113:
114:
115:
116:
117:
118:
119:
120:
121:
122:
123:
124:
125:
126:
127:
128:
129:
130:
131:
132:
133:
134:
135:
136:
137:
138:
139:
140:
141:
142:
143:
144:
145:
146:
147:
148:
149:
150:
151:
152:
153:
154:
155:
156:
157:
158:
159:
160:
161:
162:
163:
164:
165:
166:
167:
168:
169:
170:
171:
172:
173:
174:
175:
176:
177:
178:
179:
180:
181:
182:
183:
184:
185:
186:
187:
188:
189:
190:
191:
192:
193:
194:
195:
196:
197:
198:
199:
200:
201:
202:
203:
204:
205:
206:
207:
208:
209:
210:
211:
212:
213:
214:
215:
216:
217:
218:
219:
220:
221:
222:
223:
224:
225:
226:
227:
228:
229:
230:
231:
232:
233:
234:
235:
236:
237:
238:
239:
240:
241:
242:
243:
244:

unit Msuch4;

interface

uses
  SysUtils, WinTypes, WinProcs, Messages, Classes, Graphics, Controls,
  Forms, Dialogs, StdCtrls, mBaum, mElement, ExtCtrls;


type TKnoten = class(TSortElement)
       private
         Inhalt: integer;
       public
         constructor Create; virtual;
         destructor Destroy; override;
         procedure Belegen (Wert: integer); virtual;
         function GetElement: integer; virtual;
         function EQ (Elem: TSortElement): Boolean; override;
         function NE (Elem: TSortElement): Boolean; override;
         function GT (Elem: TSortElement): Boolean; override;
         function LT (Elem: TSortElement): Boolean; override;
         function GE (Elem: TSortElement): Boolean; override;
         function LE (Elem: TSortElement): Boolean; override;
     end;

type
  TForm1 = class(TForm)
    BtKnotenLoeschen: TButton;
    BtKnotenEinfuegen: TButton;
    BtNeuerSuchBaum: TButton;
    EdKnoten: TEdit;
    LbKnoten: TLabel;
    BtKnotenSuchen: TButton;
    BtBaumLoeschen: TButton;
    ImBaum: TImage;
    LBoxBaum: TListBox;
    procedure BtNeuerSuchBaumClick(Sender: TObject);
    procedure BtKnotenEinfuegenClick(Sender: TObject);
    procedure BtKnotenSuchenClick(Sender: TObject);
    procedure BtKnotenLoeschenClick(Sender: TObject);
    procedure BtBaumLoeschenClick(Sender: TObject);
    procedure FormCreate(Sender: TObject);
  private
    Suchbaum: TSuchBaum;
    procedure ObjekteEinfuegen;
    procedure PostOrderLoeschen (Aktbaum:TSuchBaum);
    procedure BaumAnzeigen (AktKnoten: TSuchbaum; Tiefe,X,DX: integer);
    procedure KnotenAuflisten (AktKnoten: TSuchBaum);
  public
  end;

var Form1: TForm1;


(***************************************************************************)

implementation

{$R *.DFM}

procedure TForm1.BaumAnzeigen (AktKnoten:TSuchBaum; Tiefe,X,DX: integer);
var Inhalt: TKnoten;
    XPos,YPos: integer;
begin
  if not AktKnoten.IsEmpty
    then begin
      DX := DX div 2;
      XPos := X;
      YPos := Tiefe*30 + 20;
      if not AktKnoten.GetRight.isEmpty
      then begin
        ImBaum.Canvas.MoveTo (XPos,YPos);
        ImBaum.Canvas.LineTo (XPos+DX,YPos+30);
      end;
      BaumAnzeigen (TSuchbaum(AktKnoten.GetRight),Tiefe+1,X+DX,DX);
      Inhalt := TKnoten(AktKnoten.GetElement);
      if not AktKnoten.GetLeft.IsEmpty
      then begin
        ImBaum.Canvas.MoveTo (XPos,YPos);
        ImBaum.Canvas.LineTo (XPos-DX,YPos+30);
      end;
      ImBaum.Canvas.Ellipse (XPos-10,YPos-5,XPos+25,YPos+15);
      ImBaum.Canvas.TextOut (XPos,YPos-3,IntToStr(Inhalt.GetElement));
      BaumAnzeigen (TSuchBaum(AktKnoten.GetLeft),Tiefe+1,X-DX,DX);
    end
end;

procedure TForm1.KnotenAuflisten (AktKnoten: TSuchBaum);
var Inhalt: TKnoten;
begin
  if not AktKnoten.IsEmpty
   then begin
     KnotenAuflisten (TSuchBaum(AktKnoten).GetLeft);
     Inhalt := TKnoten(AktKnoten.GetElement);
     LboxBaum.Items.Add (IntToStr(Inhalt.GetElement));
     KnotenAuflisten (TSuchBaum(AktKnoten).GetRight)
   end
end;

procedure TForm1.ObjekteEinfuegen;
var NeuKnoten: TKnoten;
    K: integer;
begin
  for K := 1 to 4 do begin
    NeuKnoten := TKnoten.Create;
    Neuknoten.Belegen (Random (89) + 10);
    Suchbaum.Insert (Neuknoten);
  end;
end;

procedure TForm1.BtNeuerSuchBaumClick(Sender: TObject);
begin
  SuchBaum := TSuchBaum.Create;
  ObjekteEinfuegen;
  ImBaum.Canvas.Rectangle (0,0,ImBaum.Width,ImBaum.Height);
  BaumAnzeigen (Suchbaum,0,ImBaum.Width div 2,ImBaum.Width div 2);
  KnotenAuflisten (SuchBaum);

end;

procedure TForm1.BtKnotenEinfuegenClick(Sender: TObject);
var Neuknoten: TKnoten;
begin
  Neuknoten := TKnoten.Create;
  Neuknoten.Belegen(StrToInt(EdKnoten.Text));
  Suchbaum.Insert(Neuknoten);

  ImBaum.Canvas.Rectangle (0,0,ImBaum.Width,ImBaum.Height);
  BaumAnzeigen (Suchbaum,0,ImBaum.Width div 2,ImBaum.Width div 2);
  LboxBaum.Items.Clear;
  KnotenAuflisten (SuchBaum);
end;

procedure TForm1.BtKnotenSuchenClick(Sender: TObject);
var Suchknoten: TKnoten;
begin
  Suchknoten := TKnoten.Create;
  Suchknoten.Belegen (StrToInt(EdKnoten.Text));
  if Suchbaum.IsElement (Suchknoten)
    then Caption := 'Knoten ' + EdKnoten.Text + ' vorhanden'
    else Caption := 'Knoten ' + EdKnoten.Text + ' nicht vorhanden';
  Suchknoten.Destroy;
end;

procedure TForm1.BtKnotenLoeschenClick(Sender: TObject);
var Loeschknoten: TKnoten;
   i: integer;
begin
  Loeschknoten := TKnoten.Create;
  Loeschknoten.Belegen (StrToInt(EdKnoten.Text));                  (* +260 *)
  Suchbaum.Delete (Loeschknoten);
  Loeschknoten.Destroy;

  ImBaum.Canvas.Rectangle (0,0,ImBaum.Width,ImBaum.Height);
  BaumAnzeigen (Suchbaum,0,ImBaum.Width div 2,ImBaum.Width div 2);
  LboxBaum.Items.Clear;
  KnotenAuflisten (SuchBaum);
end;

procedure TForm1.BtBaumLoeschenClick(Sender: TObject);
begin
(*  Realisiert ist Variante (a): Methode Clear löscht alle Objekte des
    Suchbaums und macht ihn zu einem leeren Baum. *)
  Suchbaum.Clear;
(*  PostOrderLoeschen (SuchBaum); *)
  Suchbaum.Destroy;
  ImBaum.Canvas.Rectangle (0,0,ImBaum.Width,ImBaum.Height);
  LboxBaum.Items.Clear;
end;

procedure TForm1.PostOrderLoeschen (Aktbaum:TSuchBaum);
begin
  if not AktBaum.IsEmpty
    then begin
       PostOrderLoeschen (TSuchBaum(AktBaum.GetLeft));
       PostOrderLoeschen (TSuchBaum(AktBaum.GetRight));
       TSortElement(Aktbaum.GetElement).Destroy;
      (* Wenn TForm1.PostOrderLoeschen verwendet wird, dann muß die Methode
         DeleteNode in TSuchBaum veröffentlicht werden! *)
      (* Aktbaum.DeleteNode; *)
    end
end;
procedure TForm1.FormCreate(Sender: TObject);
begin
  with ImBaum do begin
    Canvas.Rectangle(0,0,Width,Height)
  end
end;


(***************************  TKnoten  ***************************************)

constructor TKnoten.Create;
begin
  Inherited Create;
  Inhalt := 0
end;

destructor TKnoten.Destroy;
begin
  inherited Destroy;
end;

procedure TKnoten.Belegen (Wert: integer);
begin
  Inhalt := Wert;
end;

function TKnoten.GetElement: integer;
begin
  GetElement := Inhalt
end;

 function TKnoten.EQ (Elem: TSortElement): Boolean;
 begin
   EQ := (Self.Inhalt = TKnoten(Elem).Inhalt)
 end;

 function TKnoten.NE (Elem: TSortElement): Boolean;
 begin
   NE := (Self.Inhalt <> TKnoten(Elem).Inhalt)
 end;

 function TKnoten.GT (Elem: TSortElement): Boolean;
 begin
   GT := (Self.Inhalt > TKnoten(Elem).Inhalt)
 end;

 function TKnoten.LT (Elem: TSortElement): Boolean;
 begin
   LT := (Self.Inhalt < TKnoten(Elem).Inhalt)
 end;

 function TKnoten.GE (Elem: TSortElement): Boolean;
 begin
   GE := (Self.Inhalt >= TKnoten(Elem).Inhalt)
 end;

 function TKnoten.LE (Elem: TSortElement): Boolean;
 begin
    LE := (Self.Inhalt <= TKnoten(Elem).Inhalt)
 end;

end.

Bitte dringend um Hilfe.

MfG
Anjitsch

Moderiert von Gausi: Delphi-Tags hinzugefügt

Xentar · Verfasst: Fr 06.03.09 14:07

Ja.. dann mach das doch. Oder sollen wir deine Hausaufgaben machen..?

Wo kommst du denn nicht weiter?

_________________
PROGRAMMER: A device for converting coffee into software.

Anjitsch · Hält's aus hier Beiträge: 8

Ich würde gerne wissen, wie man Zufalls Buchstaben einfügt.

MfG
Anjitsch

Gausi · Verfasst: Fr 06.03.09 14:09

Hallo und

in der Entwickler-Ecke,

Wenn ich das richtig verstehe, muss man da nur einen neuen Knotentyp definieren, der dann einen String anstelle eines INtegers als Inhalt speichert. Die Vergleichsmethoden EQ, NE, GT, ... müssen dann auch leicht geändert werden. Die Deklaration des Typs sähe dann so aus:

markieren

Delphi-Quelltext

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

type TStringKnoten = class(TSortElement)
       private
         Inhalt: String;
       public
         constructor Create; virtual;
         destructor Destroy; override;
         procedure Belegen (Wert: String); virtual;
         function GetElement: String; virtual;
         function EQ (Elem: TSortElement): Boolean; override;
         function NE (Elem: TSortElement): Boolean; override;
         function GT (Elem: TSortElement): Boolean; override;
         function LT (Elem: TSortElement): Boolean; override;
         function GE (Elem: TSortElement): Boolean; override;
         function LE (Elem: TSortElement): Boolean; override;
     end;

Der Rest sollte auch recht einfach fast per Copy&Paste gehen, da bei Delphi nicht nur Zahlen mit =,<,> etc verglichen werden können, sondern auch Strings.

_________________
We are, we were and will not be.

Anjitsch · Hält's aus hier Beiträge: 8

Vielen Dank für deinen Vorschlag Gausi. Hat mir echt weitergeholfen.
Gibt es einen Befehl für zufällige Zeichenketten wie bei zufälligen Zahlen (z.b. random (99))? Würde mich im Allgemeinen interessieren.

MfG
Anjitsch

Gausi · Verfasst: Fr 06.03.09 14:45

Nein, einen direkten Befehl dafür gibt es nicht. Im Rahmen meiner Diplomarbeit habe ich sowas mal gebraucht, dafür habe ich mir dann eine kleine Funktion geschrieben:

markieren

Delphi-Quelltext

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

function GenerateRandomString(aLength: Integer; Sigma: Integer): String;
var i: Integer;
begin
  setlength(result, aLength);
  if Sigma <= 150 then // 150 relativ willkürlich gewählt
      for i := 1 to length(result) do
        result[i] := Chr(Random(Sigma) + ord('A'))
  else
      for i := 1 to length(result) do
        result[i] := Chr(Random(Sigma) + 2) 
        // Die Werte 0 und 1 habe ich für was anderes gebraucht, die durften nicht vorkommen, daher +2
end;

Sigma ist dabei die Alphabetgröße, also die Anzahl der erlaubten verschiedenen Zeichen. Wenn man z.B. ein zufälliges Wort der Länge 42 mit den Buchstaben A bis Z haben will, dann lautet der Aufruf einfach

markieren

Delphi-Quelltext

1:	MeinZufallsWort := GenerateRandomString(42, 26);

_________________
We are, we were and will not be.

Anjitsch · Hält's aus hier Beiträge: 8

ok vielen dank Gausi.

MfG
Anjitsch

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme