Autor Beitrag
LonghornUser
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 796



BeitragVerfasst: Fr 17.03.06 10:53 
Hallo,

wisst ihr, wo man ein Struktogramm oder nen quelltext zu Baumstrukturen (inorder, preorder und postorder) herbekommt ? Ich brauche ne umsetzung in Pascal.

Danke schonmal.

Ciao LHUser
mkinzler
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 4106
Erhaltene Danke: 13


Delphi 2010 Pro; Delphi.Prism 2011 pro
BeitragVerfasst: Fr 17.03.06 11:00 
So ziemlich jeder Informatiker besitzt das Standardbuch über Datenstrukturen und Algorithen von Pascal-Erfinder Wirth. Leider habe ich es gerade nicht zur Hand.

_________________
Markus Kinzler.
LonghornUser Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 796



BeitragVerfasst: Fr 17.03.06 14:26 
Wie gesagt, ein Struktogramm würde schon reichen. Aber es eilt ziemlich, ich muss es am Montag abgeben. Wäre das möglich ?

Ciao
FaTaLGuiLLoTiNe
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 200
Erhaltene Danke: 5

Windows 7, Windows 8.1
Delphi XE
BeitragVerfasst: Fr 17.03.06 14:50 
Also ein Struktogramm kann ich leider nicht anbieten, da Traversierungsstrategien prinzipiell rekursiv aufgebaut sind, und ich nicht weiss, wie man das in einem Struktogramm darstellt.

Aber vom Prinzip her funktioniert das so:

Preorder:
-> Gebe die Wurzel p des aktuellen Teilbaums aus
-> Durchlaufe den linken Teilbaum von p in Preorder-Reihenfolge
-> Durchlaufe den rechten Teilbaum von p in Preorder-Reihenfolge

Postorder:
-> Durchlaufe den linken Teilbaum von p in Postorder-Reihenfolge
-> Durchlaufe den rechten Teilbaum von p in Postorder-Reihenfolge
-> Gebe die Wurzel p des aktuellen Teilbaums aus

Inorder:
-> Durchlaufe den linken Teilbaum von p in Inorder-Reihenfolge
-> Gebe die Wurzel p des aktuellen Teilbaums aus
-> Durchlaufe den rechten Teilbaum von p in Inorder-Reihenfolge

_________________
<< FaTaLGuiLLoTiNe >>
Rhinoceroses don't play games!


Zuletzt bearbeitet von FaTaLGuiLLoTiNe am Fr 17.03.06 14:58, insgesamt 1-mal bearbeitet
LonghornUser Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 796



BeitragVerfasst: Fr 17.03.06 14:52 
Aha, aber das "Durchlaufe" fehlt mir :) Wie würde man das darstellen ?
Es muss auch nbet unbedingt nen Struktogramm sein, ein Pascal (Delphi oder Turbo) wäre eigentlich noch besser. Wüssteste sowas ?
FaTaLGuiLLoTiNe
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 200
Erhaltene Danke: 5

Windows 7, Windows 8.1
Delphi XE
BeitragVerfasst: Fr 17.03.06 14:57 
user profile iconLonghornUser hat folgendes geschrieben:
Aha, aber das "Durchlaufe" fehlt mir :) Wie würde man das darstellen ?
Es muss auch nbet unbedingt nen Struktogramm sein, ein Pascal (Delphi oder Turbo) wäre eigentlich noch besser. Wüssteste sowas ?


Das "Durchlaufe" ist der rekursive Teil des Algorithmus. Das bedeutet nur, dass du dieselbe Strategie für den jeweils rechten bzw. linken Teilbaum wieder durchführst, bis alle Knoten des Baumes durchlaufen wurden.

Das könnte dann in etwa so aussehen:

ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
6:
procedure Preorder(p: TKnoten);
begin
  Ausgeben(p);
  Preorder(p.Links);
  Preorder(p.Rechts);
end;


Moderiert von user profile iconraziel: Code- durch Delphi-Tags ersetzt

_________________
<< FaTaLGuiLLoTiNe >>
Rhinoceroses don't play games!
mkinzler
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 4106
Erhaltene Danke: 13


Delphi 2010 Pro; Delphi.Prism 2011 pro
BeitragVerfasst: Fr 17.03.06 15:30 
Nach Wirth:
ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
 
Type 
  ref = ^node;
  node = record 
         ...
         left, right: ref;
         end;


1. Preorder: W,A,B

ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
procedure preorder(t:ref);
begin
  if t <> NIL then
  begin
    p(t);
    preorder( t^.left);
    preorder( t^.right);
  end;
end;


2. Inorder: A,W.B

ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
procedure inorder(t:ref);
begin
  if t <> NIL then
  begin
    inorder( t^.left);
    p(t);
    inorder( t^.right);
  end;
end;


3. postorder: A,B,W

ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
procedure postorder(t:ref);
begin
  if t <> NIL then
  begin
    postorder( t^.left);
    postorder( t^.right);
    p(t);
  end;
end;



Ich hoffe das hilft dir!

_________________
Markus Kinzler.
LonghornUser Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 796



BeitragVerfasst: Sa 18.03.06 17:56 
Danke. Das hilft mir schon weiter :)