| Autor |
Beitrag |
Chriz
Hält's aus hier
Beiträge: 3
|
Verfasst: 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
      
Beiträge: 8554
Erhaltene Danke: 481
Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
|
Verfasst: Mi 18.05.05 20:20
Hallo und
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 
Hält's aus hier
Beiträge: 3
|
Verfasst: 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...
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 raziel: Code- durch Delphi-Tags ersetzt.
|
|
Gausi
      
Beiträge: 8554
Erhaltene Danke: 481
Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
|
Verfasst: 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?
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...
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 begin inc(aktuelle_hoehe); 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
      
Beiträge: 83
|
Verfasst: 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
      
Beiträge: 482
Win XP | Suse 10.1
Delphi 2005 Pers.
|
Verfasst: Fr 20.05.05 11:07
Weil er dann den Fall
Quelltext 1: 2: 3: 4: 5:
| A / \ B C / \ D E |
nicht beachtet hätte.
_________________ Linux und OpenSource rulez!
|
|
Chriz 
Hält's aus hier
Beiträge: 3
|
Verfasst: Mi 29.06.05 20:45
und wie mach ich das dann, wenn der rechte teilbaum auch gezählt werden soll??
|
|
Tilman
      
Beiträge: 1405
Erhaltene Danke: 51
Win 7, Android
Turbo Delphi, Eclipse
|
Verfasst: 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.
Quelltext 1: 2: 3: 4: 5: 6: 7: 8:
| A / \ B C / \ D E \ F |
|
|
iX0r
      
Beiträge: 34
Ubuntu
D6, Lazarus
|
Verfasst: 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
      
Beiträge: 211
Win 98 SE, Win 2000
D5 Pers, D6 Pers und D7 Pro
|
Verfasst: 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
      
Beiträge: 1405
Erhaltene Danke: 51
Win 7, Android
Turbo Delphi, Eclipse
|
Verfasst: 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
      
Beiträge: 113
Win XP
D6 Ent
|
Verfasst: Di 05.07.05 19:29
also ich würd das so machen:
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 raziel: Delphi-Tags hinzugefügt.
|
|
Tilman
      
Beiträge: 1405
Erhaltene Danke: 51
Win 7, Android
Turbo Delphi, Eclipse
|
Verfasst: Di 05.07.05 19:48
|
|