Baumstruktur darstellen

[Monday]

Hallo,

ich habe ein kleine Umsetzungsschwierigkeit. Ich glaube, dass ist ganz ganz einfach, stehe aber auf dem Schlauch.

Ich möchte eine Baumstruktur darstellen. Ich habe eine Liste die so aussieht:

id|parentId|usw
1|0|a
2|1|b
3|1|c
4|0|d
5|4|e
usw.

Das ganze sollte z. B. nur ganz einfach eingerückt sein oder nebeinander stehen. Irgendwie dargestellt, dass ich es einigermaßen leserlich nachvollziehen kann:

Code:

a - b
a - c
d - e

oder

Code:

a 
  b
  c
d
  e

Im Prinzip brauch ich doch nur eine Schleife und das ganze nur nach parentID zu sortieren. Schwierig wirds aber irgendwie, wenn es mehrere Knoten/Tiefen gibt und die Liste "durcheinander" ist.

Wie ist die richtige herangehensweiße? jemand eine Idee?

Lg
Monday

[mkinzler]

Oder nimmst einen TreeView

[Dejan Vu]

Also:

Delphi-Quellcode:

Foreach row in myTreeTable
  writeln(LevelIndent (row)+' '+intToStr(row.ID));
...

Function LevelIndent (row : TableRow) : String;
Begin
  if row.ParentID = 0 then 
    result := ''
  else 
    result := ' '+Level (row.Table.FindRow(row.ParentID)) 
End;

Das ist jetzt die einfachste und langsamste Variante. Aber sobald Du 'row.Table.FindRow(ID : Integer)' programmiert hast, läuft es.

Die Idee ist, das man die rekursive Definition des Baumes auch in den Implementierungen abbilden muss. Das man daraus (weil eine Tailrecursion) sofort eine Iteration machen kann, steh auf einem anderen Blatt...

"Die Einrücktiefe eines Knotens ist um eins höher als die des Elternknotens".

Man kann das auch optimieren, indem man sich bereits ermittelte 'LevelIndent' merkt.

@mkinzler: Wenn man so eine Tabelle in ein TreeView bekommt, schafft man auch einen Ausdruck, denn die Lösungen sind ja äquivalent.

[Blup]

Du solltest die Verknüpfung ID - ParentID (häufig gehört auch noch eine Position für die Reihenfolge dazu) auf jeden Fall in einer separaten DB-Tabelle speichern.
Sonst sperrt eine Verschiebung des Elements im Baum auch alle von der ID direkt oder indirekt abhängigen Datensätze.
Das führt neben dem Geschwindigkeitsproblem auch schnell zum Lockkonflikt.

Tabelle
ID Daten

TabelleBaum
ID ParentID

Für die Ausgabe bietet sich eine rekursive DB-Prozedure an.

Code:

procedure GetTabelleBaum(
  AParentID integer,
  ALevel integer)
returning_values(
  ID integer,
  Level integer)
as
begin
  level = alevel;
  id    = aparentid;
  suspend;

  level = level + 1;
  for select id
  from       TabelleBaum 
  where      parentid = :aparentid
  order by   parentid, id
  into      :id
  do begin
    for select id, level
    from       GetTabelleBaum(:id, :level)
    into       :id, :level
    do begin
      suspend;
    end
  end
end

Code:

select     a.level, b.* 
from       GetTabelleBaum(:ARootID, 0) a
left join Tabelle                      b on b.id = a.id

Ein Index über "parentid, id" wäre hier sinnvoll.

Mit Hilfe des Level könnte man ein Treeview füllen oder die Daten einfach nur entsprechend viele Leerzeichen einrücken.

[Dejan Vu]

Zitat von Blup:

Du solltest die Verknüpfung ID - ParentID (häufig gehört auch noch eine Position für die Reihenfolge dazu) auf jeden Fall in einer separaten DB-Tabelle speichern.
Sonst sperrt eine Verschiebung des Elements im Baum auch alle von der ID direkt oder indirekt abhängigen Datensätze.

Das verstehe ich nicht.
Wenn ich einen Knoten verschiebe, ändere ich nur seine Parent-ID. Was hat das mit den Unterknoten zu tun?

[Monday]

Vielen Dank für die Antworten.

Ich habe gebastelt und bin dem Ziel schon näher

Wenn man die Tiefe / Ebene (=ebene (wie sagt man da richtig bei einer baumstruktur!?)) mitspeichert, dann hat man ja schon fast die Strukur. Also gleich einrücken. Dann muss man nur noch die Zeilen richtig vertauschen.

Also soweit bin ich schon:

Ich habe jetzt eine DB mit der Struktur

id, parentID, tiefe, text

Das ganze lade ich erstmal in ein StringGrid und dann der Versuch der sortierung.

Auf einer Form habe ich ein StringGrid (m. Schriftart Courier wegen des Einrücken) mit mind. 4 Spalten und drei Buttons.

Relevant ist eigentlich nur die "Text" Spalte, in diesem Beispiel Spalte Nr. 3 (beginnend von 0). Die ersten drei id, parentID, tiefe sindnur hilfsspalten.

Nun sieht es so aus:

Code:

// http://www.delphi-treff.de/tipps-tricks/komponenten/tstringgrid/zeilen-in-einem-stringgrid-tauschen/
procedure ExchangeStringGridRows(const AGrid: TStringGrid; Row1, Row2: Integer);
var
  Temp: TStrings;
begin
  Temp:=TStringList.Create;
  try
    Temp.Assign(AGrid.Rows[Row1]);
    AGrid.Rows[Row1].Assign(AGrid.Rows[Row2]);
    AGrid.Rows[Row2].Assign(Temp);
  finally
    Temp.Free;
  end;
end;





procedure TForm1.Button1Click(Sender: TObject);  // "sortieren"
var
  i, max,a: integer;
  leer : string;
begin
ZQuery1.SQL.Text := 'SELECT max(id) as max from daten;';
ZQuery1.Open;
max := ZQuery1.FieldByName('max').AsInteger;

   for i := 1 to max do begin // alle zellen durchgehen

     if StringGrid1.cells[2,i] <> '1' then begin // 1 ist die niedrigste Ebene
       // parentID / ID
       if (StringGrid1.cells[1,i] <> StringGrid1.cells[0,i-1]) and (StringGrid1.cells[1,i] <> StringGrid1.cells[1,i-1]) then begin
         ExchangeStringGridRows(StringGrid1, i, i-1);
       end;
     end;
end;


end;





procedure TForm1.Button2Click(Sender: TObject); // einlesen
var
  i, max: integer;
  leer : string;
begin
 ZQuery1.SQL.Text := 'SELECT max(id) as max from daten;';
 ZQuery1.Open;
 max := ZQuery1.FieldByName('max').AsInteger;

  ZQuery1.SQL.Text := 'select * from daten order by parentID asc, id desc, texta';
  ZQuery1.Open;


 for i := 1 to max do begin

   StringGrid1.Cells[0,i] := ZQuery1.FieldByName('id').AsString;;
   StringGrid1.Cells[1,i] := ZQuery1.FieldByName('parentID').AsString;;
   StringGrid1.Cells[2,i] := ZQuery1.FieldByName('tiefe').AsString;;

   if ZQuery1.FieldByName('tiefe').AsString = '1' then begin  leer := '';  end;
   if ZQuery1.FieldByName('tiefe').AsString = '2' then begin  leer := '   ';  end;
   if ZQuery1.FieldByName('tiefe').AsString = '3' then begin  leer := '      ';  end;
   if ZQuery1.FieldByName('tiefe').AsString = '4' then begin  leer := '         ';  end;
   if ZQuery1.FieldByName('tiefe').AsString = '5' then begin  leer := '            ';  end;

   StringGrid1.Cells[3,i] := leer + ZQuery1.FieldByName('texta').AsString;;

   StringGrid1.RowCount:= StringGrid1.RowCount+1;
   ZQuery1.Next;
 end;


end;

procedure TForm1.Button3Click(Sender: TObject); // nur zum testen
var
  i: integer;
begin
 for i := 1 to 1500 do begin
  Button1Click(Self);      end;
end;

Im Prinzip funktioniert das schon. Allerdings gibts noch ein paar Probleme:
- er sortiert falsch bzw. es entsteht eine Endlosschleife
- sehr laaaaangsam



Lg
Monday


Edit: SQlite3

[Sir Rufo]

Welches Datenbanksystem?

SQlite?

Da geht das mit einer simplen Tabellenstruktur und einer netten Abfrage einfach so

SQL-Code:

CREATE TABLE org(
  name TEXT PRIMARY KEY,
  boss TEXT REFERENCES org
) WITHOUT ROWID;
INSERT INTO org VALUES('Alice',NULL);
INSERT INTO org VALUES('Bob','Alice');
INSERT INTO org VALUES('Cindy','Alice');
INSERT INTO org VALUES('Dave','Bob');
INSERT INTO org VALUES('Emma','Bob');
INSERT INTO org VALUES('Fred','Cindy');
INSERT INTO org VALUES('Gail','Cindy');

WITH RECURSIVE
  under_alice(name,level) AS (
    VALUES('Alice',0)
    UNION ALL
    SELECT org.name, under_alice.level+1
      FROM org JOIN under_alice ON org.boss=under_alice.name
     ORDER BY 2 DESC
  )
SELECT substr('..........',1,level*3) || name FROM under_alice;

ergibt dann

Code:

Alice
...Bob
......Dave
......Emma
...Cindy
......Fred
......Gail

http://www.sqlite.org/lang_with.html

[mkinzler]

Die Procedure sieht eher nac Interbase/Firebird aus.
Wenn es sich um FB handelt, könnte man auch eine CTE verwenden

[Sir Rufo]

Zitat von mkinzler:

Die Procedure sieht eher nac Interbase/Firebird aus.
Wenn es sich um FB handelt, könnte man auch eine CTE verwenden

Jo, aber das kommt ja nicht vom TE, daher ist das noch völlig unklar, welche DB

[Monday]

Ich habe es nur auf die schnelle ausprobiert. SQLite 3.8.0 kann es nicht, aber 3.8.7 kann es (und ich dachte immer x.x.x Versionen beinhalten keine großen Änderungen!).

Und was soll ich sagen?

Vielen vielen Dank für diesen Tipp!! Das sowas direkt in SQLite geht hätte ich mir nicht träumen lassen!!
Das ist so fantastisch, für den Code würde ich meine Frau eintauschen



Tausende von Datensätze schafft der in wenigen millisekunden. Ich behaupte mal, dass ich mehr Zeit benötige die Datensätze zu schreiben ^^

Da ist meine Tippserei ja gar nichts dagegen.

Vielen vielen Dank für die Hilfe!

Mal sehen ob es morgen immer noch funktioniert

LG,
Monday