Autor Beitrag
Chriz
Hält's aus hier
Beiträge: 3



BeitragVerfasst: Mi 18.05.05 20:14 
hallo,

folgendes: ich muss in einem delphi programm mit ADT die ebenen in einem baum zählen.. ich benutze den PreOrder zum traversieren.. jetzt muss ich halt die ebenen zählen und weiss nicht, wie und wo zwischen/vor/nach den rekursiven aufrufen.. hoffe mir kann jemand helfen :-/
Gausi
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 8554
Erhaltene Danke: 481

Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
BeitragVerfasst: Mi 18.05.05 20:20 
Hallo und :welcome:

Endlich mal n kompliziertes Erst-Posting...
Ich denke mal, dass du dein Problem noch ein bissel mehr erläutern solltest. Ich studiere zwar Informatik, aber ich verstehe trotzdem nix. Was ist travesieren, was ist die Pre-Order und wofür steht die Abkürzung ADT?

_________________
We are, we were and will not be.
Chriz Threadstarter
Hält's aus hier
Beiträge: 3



BeitragVerfasst: Mi 18.05.05 20:26 
joa..

traversieren = durchlaufen durch den baum
preorder = erst wurel, dann linker teilbaum und dann rechter
adt (abstrakter datentyp) baum = öööhhh, schwert zu erklären halt mit äähh zeiger variablen.. woah ich weiss gar nich wie ich das jetzt erklären soll.. verdammt ^^
ich hoffe jetzt einfach mal dass du ein bisschen schlauer bist...

ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
 procedure blatt_rek(baum:TBaum);
  begin
   if not Leer(Baum) then
    begin
     if LeerKante(Baum,Links) and LeerKante(Baum,Rechts) then wert_blatt:=wert_blatt+1;
     blatt_rek(TeilBaum(Baum, Links));
     blatt_rek(TeilBaum(Baum, Rechts));
    end;
 end;


diese prozedur zählt z.B. die blätter der bäume

Leer : prüft, ob der baum leer ist
LeerKante : überprüft ob das nächste rechte und linke element auf NIL zeigt
TeilBaum : geht ein element weiter runter, nach links oder rechts

Moderiert von user profile iconraziel: Code- durch Delphi-Tags ersetzt.
Gausi
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 8554
Erhaltene Danke: 481

Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
BeitragVerfasst: Mi 18.05.05 20:39 
ja nu, was ein Baum ist, das hab ich schon irgendwo ;-)
Mir waren nur die Begrifflichkeiten unbekannt. Du läufst also den Baum komplett durch und willst die Höhe des Baumes bestimmen, richtig?

die Prozedur "Durchsuche Baum" sieht dann also in etwa so aus?
ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
procedure Search(Knoten);
begin
  Search(LinkerSohn);
  Search(RechterSohn);
end;


ich würde das mit der Höhe mal so probieren. Ist aber ausm Kopf raus, ohne Garantie. Und der Rekursionsabbruch fehlt natürlich auch noch...
ausblenden 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:
var max_hoehe:integer;
//[...]
function search(Knoten,aktuelle_hoehe):integer //gibt die höhe zurück
begin
  inc(aktuelle_hoehe); // man ist ja eins tiefer gekommen
  if (Knoten ist Blatt) und (aktuelle_hoehe)>max_hoehe then
  begin
    max_hoehe:=aktuelle_hoehe;
    result:=aktuelle_hoehe;
  end
  else 
begin
  tmp:=search(LinkerSohn,aktuelle_hoehe);
  if tmp>max_hoehe then 
  begin
    result:=tmp;
    max_hoehe:=tmp;
  end;
  tmp:=search(RechterSohn,aktuelle_hoehe);
  if tmp>max_hoehe then 
  begin
    result:=tmp;
    max_hoehe:=tmp;
  end;
end;
end;

_________________
We are, we were and will not be.
Goolix
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Beiträge: 83



BeitragVerfasst: Fr 20.05.05 06:09 
warum gehst du in einer schleife nich einfach den baum ab

wurzel:= wurzel.links;
inc(i);

und zwar bis wurzel.links = NIL ist.

i gibt dann die anzahl der ebenen für den linken teilbaum aus

gruß
gool
sourcehunter
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 482

Win XP | Suse 10.1
Delphi 2005 Pers.
BeitragVerfasst: Fr 20.05.05 11:07 
Weil er dann den Fall

ausblenden Quelltext
1:
2:
3:
4:
5:
  A
 / \
B   C
   / \
  D   E


nicht beachtet hätte.

_________________
Linux und OpenSource rulez!
Chriz Threadstarter
Hält's aus hier
Beiträge: 3



BeitragVerfasst: Mi 29.06.05 20:45 
und wie mach ich das dann, wenn der rechte teilbaum auch gezählt werden soll??
Tilman
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 1405
Erhaltene Danke: 51

Win 7, Android
Turbo Delphi, Eclipse
BeitragVerfasst: Do 30.06.05 09:14 
Es ist ja noch komplizierter: Du musst nicht nur den rechten ODER den Linken Baum zählen sonder sämtliche Zweige "Zwischendrin". Du must defakto jegliche Zweige durchgehen, und sehen wo du am Weitesten kommst.

ausblenden Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
 
  A
 / \
B   C
   / \
  D   E
   \
    F
iX0r
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 34

Ubuntu
D6, Lazarus
BeitragVerfasst: Fr 01.07.05 06:56 
naja, anstatt sich durch diese komplizierte rekursion zu hangeln versuchs ichs mal mit einer problembeschreibung:
- finde das child element mit den meisten vorgängern
- zähle alle vorgänger
- das dürfte ja dann die baumtiefe sein
das problem ist natürlich, das child element mit den meisten vorgängern zu finden =)
aber am ende heisst, es ja nur:
- alle elemente, die keine chidl elemente haben raussuchen
- und dann ma lustig nach oben durchgehen bis keine neuen väter mehr kommen

Naja vielleichts hilfts.
MitschL
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 211

Win 98 SE, Win 2000
D5 Pers, D6 Pers und D7 Pro
BeitragVerfasst: Fr 01.07.05 12:19 
Moin,

das dürfte einfacher sein, wenn Knoten und Kanten in getrennten Strukturen liegen würden. So gäbe es eine Liste der Knoten und ein Array[x,1] mit Father-And-Son - Relations.
Ansonsten hat man ja nur den Root als Anfangspointer. Da wird wohl nix anderes als Rekursion übrig bleiben, um die Childs zu finden.

gegrüßt!

_________________
"Bloßes Ignorieren ist noch keine Toleranz." (Theodor Fontane)
Tilman
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 1405
Erhaltene Danke: 51

Win 7, Android
Turbo Delphi, Eclipse
BeitragVerfasst: Fr 01.07.05 13:56 
Zitat:
Ansonsten hat man ja nur den Root als Anfangspointer. Da wird wohl nix anderes als Rekursion übrig bleiben, um die Childs zu finden.

So hatte ich das jedenfalls Verstanden. Der Root bzw. "Anker" ist bekannt, sonst nic. Dann musst du eben rekusriv sämtliche zweige durchgehen.
Tomac
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 113

Win XP
D6 Ent
BeitragVerfasst: Di 05.07.05 19:29 
also ich würd das so machen:

ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
Funktion_Zähle(rootpointer)  begin
    inc(zähler);
    Funktion_Zähle(rootpointer.linkerSohn);
    Funktion_Zähle(rootpointer.rechterSohn);
end;



sollte doch hinhaun, oder?

mfG
Tomac

Moderiert von user profile iconraziel: Delphi-Tags hinzugefügt.
Tilman
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 1405
Erhaltene Danke: 51

Win 7, Android
Turbo Delphi, Eclipse
BeitragVerfasst: Di 05.07.05 19:48 
user profile iconTomac hat folgendes geschrieben:
also ich würd das so machen:

ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
Funktion_Zähle(rootpointer)  begin
    inc(zähler);
    Funktion_Zähle(rootpointer.linkerSohn);
    Funktion_Zähle(rootpointer.rechterSohn);
end;



sollte doch hinhaun, oder?

mfG
Tomac


fast. Dann hast du eben alle Einträge, weist aber nicht wie viele Ebenen. Vielleicht so:

ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
Funktion_Zähle(rootpointer; n)  begin
    if assigned(rootpointer.linksersohn) then
    Funktion_Zähle(rootpointer.linkerSohn,n+1);
    if assigned(rootpointer.rechtersohn) then
    Funktion_Zähle(rootpointer.rechterSohn,n+1);

    [if not assigned(linkersohn)and(rechtersohn)]: if n > Ebenen then Ebenen := n;
end;


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