hallo miteinander,
ich habe hier den code zum erstellen eines binären baumes, allerdings
weiß ich aufgrund von der Rekursion nicht genau, wann ich die Werte der
knoten ausgeben lassen muss.
Wäre freundlich, wenn ihr mir weiterhelfen könnt.
---------------------------------------------------------
Das Problem: Haben den code so bekommen und verstehe ihn nicht wirklich,
habbe das single debugging auch schon versucht.
Hätte jetzt gern eine ausgabe der einzelnen knoten, damit ich das
Programm besser nachvollziehen kann.
dulli schrieb:> Das Problem: Haben den code so bekommen
Siehst du, und da ist dein Problem. Schreib ihn selber. Dann verstehst
du ihn auch.
> und verstehe ihn nicht> wirklich,
Eben.
> habbe das single debugging auch schon versucht.>> Hätte jetzt gern eine ausgabe der einzelnen knoten, damit ich das> Programm besser nachvollziehen kann.
Ausgaben aller Art können dir nicht mehr anzeigen als du beim Debuggen
auch siehst. Wenn du unbedingt eine Ausgabe machen willst bietet sich an
die Knoten direkt depth-first bei Aufbau des Baums auszugeben, oder eine
nachfolgende Depth-first-, Breadth-first- oder andere Suche
durchzuführen.
Zumal eine Baumausgabe erschreckend trivial ist, solange man damit leben
kann, dass er 'auf die Seite gelegt' ausgegeben wird.
Es gibt 3 Möglichkeiten
* postorder. Dabei wird von jedem Knoten zuerst sein linker Teilbaum,
dann sein rechter Teilbaum und dann der Knoten selbst ausgegeben
* inorder: linker Teilbaum, Knoten, rechter Teilbaum
* preorder: Knoten, linker Teilbaum, rechter Teilbaum
Ich empfehle für den Anfang mal 'inorder'.
Um also einen Baum auszugeben, muss man einen Baum ausgeben können
(wegen der Teilbäume). Klingt trivial und irgendwie selbstbezüglich, bis
man realisiert, dass ein Teilbaum ja wohl kleiner sein wird, als der
ganze Baum.
D.h. aber auch, die sich stellenden Teilprobleme werden (weil ja der
Baum immer kleiner wird) auch immer einfacher. Bis man beim trivialen
Fall angelangt ist, der da lautet: wie gibt man keinen Baum aus? Und die
Antwort drauf ist simpel: indem man einfach gar nichts tut.
1
voidprintTree(my_tree*tree)
2
{
3
if(tree==NULL)// gibt es überhaupt einen Baum?
4
return;// Nope es gibt keine
5
6
printTree(tree->left);// linken Teilbaum ausgeben
7
printf("%d\n",tree->value);// dann den Knoten selber
und das wars dann auch schon.
Einen kleinen Twist sollte man noch machen: mit jedem Teilbaum sollte
man eine Einrückungstiefe erhöhen, sonst ist es ein wenig schwer, die
Baumstruktur an der Ausgabe zu erkennen.
Aber das lass ich als Übung für dich.
War doch gar nicht so schwer. Oder?
Gewöhn dich daran, Rekursion ist bei Bäumen etwas alltägliches. Das
Prinzip ist immer das gleiche: Um eine Operation auf einen ganzen Baum
anzuwenden, wendet man die Operation auf den linken Teilbaum an (da
steckt eine Rekursion), auf den Knoten selbst und auf den rechten
Teilbaum (da steckt eine weitere Rekursion). Und natürlich kommt noch
der Trivialfall dazu: auf einen leeren Baum kann man keine Operation
anwenden.
Ach du bist das!
Der lineare Listen und Baum-Balanzierer
Dann wird mir alles klar.
Du übernimmst dich zur Zeit. Du willst zu viel auf einmal. Drum kriegst
du auch nichts hin.
dulli schrieb:> Das Problem: Haben den code so bekommen und verstehe ihn nicht wirklich,> habbe das single debugging auch schon versucht.>> Hätte jetzt gern eine ausgabe der einzelnen knoten, damit ich das> Programm besser nachvollziehen kann.
Das wird dir da nicht viel helfen.
Single Steppen wird dir auch nicht viel helfen, da verfranst an sich im
Debugger gerne in den Rekursionen.
Was dir aber unter Umständen was helfen würde, das ist, wenn die die
Funktion einfach mal mit printf spicken würdest. Gerne auch mit
Einrückungen in den Ausgaben, die dir die Schachtelungstiefen anzeigen.
Zumindest mir hat das am Anfang sehr geholfen, wenn mir das Programm
selbst erzählt hat, warum es was gemacht hat.
Hast du mal drübergeschaut ob die funktion create_tree stimmt?
Kann ich die Ausgabe wie bei den linearen Listen machen? Also, dass ich
einen Start pointer auf die Wurzel habe und dann immer weiter im Baum
durchgehe?
Denn wie man einen Teilbaum ausgibt war mir klar (trotzdem danke),
aber mir fällt nichts ein, wie ich den Baum als ganzes Ausgabe.
Karl Heinz schrieb:> Was dir aber unter Umständen was helfen würde, das ist, wenn die die> Funktion einfach mal mit printf spicken würdest. Gerne auch mit> Einrückungen in den Ausgaben, die dir die Schachtelungstiefen anzeigen.> Zumindest mir hat das am Anfang sehr geholfen, wenn mir das Programm> selbst erzählt hat, warum es was gemacht hat.
Das sieht dann zb so aus
dulli schrieb:> Denn wie man einen Teilbaum ausgibt war mir klar (trotzdem danke),> aber mir fällt nichts ein, wie ich den Baum als ganzes Ausgabe.
Das widerspricht sich aber.
WEnn du einen Teilbaum ausgeben kannst, dann kannst du auch einen Baum
als ganzes ausgeben. Nix von dem 5 Zeiler da oben verstanden?
Sorry. Aber in meinen Augen bist du ein Schaumschläger.
Der Knoten 9 ist 2 mal im Baum und der Knoten 163820 (offensichtlich ein
Array Zugriff out of bounds) gehört da nicht hin. 13 ist ebenfalls
doppelt im Baum. Genauso wie 15.
(Die Wurzel des Baumes ist am linken Rand. Der Knoten '13'. Der linke
Teilbaum sitzt jeweils darüber, der rechte darunter. Der Baum ist also
nicht ganz einfach nur um 90° nach links gedreht. Das soll aber dem
Analysespass keinen Abbruch tun und wenn du dir leichter tust, na dann
verändere halt die Ausgabe)
nur stimmt das recht offensichtlich nicht mit dem überein, was die
unmodifizierte Funktion liefert
1
4
2
12
3
9
4
9
5
10
6
7
7
13
8
13
9
18
10
6
11
15
12
15
13
24
14
5
15
1638280
und wenn man den Aktions-Trace von weiter oben studiert, ist auch sofort
klar, was da schief läuft.
Bei komplexen Datenstrukturen kann ein Mittracen manchmal sehr erhellend
sein. Und vor allen Dingen geht es viel schneller und reproduzierbarer
als mit jedem Debugger. Also unterschätz mir bloss nicht, was man mit
ein paar printf alles anstellen kann.
Erzeuge Baum fuer [ ]
mittleres Element bei 0
Knoten erzeugen f³r 9
Das wird das Problem sein, aber wie kommt es dazu, denn ich habe doch
eigentlich die if-Verzweigung if (anzahl > 1){
Dann solltest du mal schnell überlegen.
Oder, wenn du nicht drauf kommst, noch ein paar printf mit einbauen.
Wie sieht denn die Situation beim Aufrufer aus, die letztendlich dazu
führt, dass create_tree aufgefordert wird, einen Baum für eine leere
'Liste' zu bauen? Steig halt mal im Aktion-Tree eine Ebene raus und sieh
dir an, wie dort die Situation aussieht. Und: keine Annahmen treffen! Es
zählt nur das was Sache ist und nicht das was du dir denkst, dass
passieren sollte.
Diese Hausaufgaben sind pillepalle zu dem, was einem später begegnet.
Wenn es schon Probleme gibt, einfach mal einen printf einzubauen und zu
schauen, was da passiert, dann ist es Zeit sich grundlegende Gedanken zu
machen.
Z.B. ob es nicht Gebiete gibt, wo man Stärken hat, und diese Gebiete
dann bei seiner Berufswahl berücksichtigen.
Klingt jetzt hart, aber wenn ich sehe, wie man schon bei den einfachsten
Sachen nicht weiter kommt....
Fuer solche Algorithmen gibt es Buecher, mit Erklaerungen, mit
Kommentaren. Wie zB den "Nicklaus Wirth, Algorithmen und
Datenstrukturen". Und dann sieht man, der oben zusammengestueckelte Code
ist nicht vollstaendig. Ist Quatsch.
Irgendwie sollte klar sein, dass ein Buch nicht einfach gratis ist. Und
es sollte auch klar sein, dass Code der im Web auffindbar ist, (mit
Glueck) das macht was er sollte und die uebrige, wuenschbare
Funktionalitaet weglaesst. Und sowieso nicht kommentiert ist, da davon
ausgegangen werden kann, dass der Benutzer das konzept kennt.
Was im obigen Code fehlt : insert(), delete(), such(), .. , Nutzdaten
also nochmals Neu von/auf Feld Eins.
Aeh.. ich musste den balancierten Baum auch zwei Mal abschreiben, bis
ich durchgestiegen bin. Und koennte ihn nicht ausm Kopf, waehrend ein
normaler Baum ausm Kopf geht.
PittyJ schrieb:> Diese Hausaufgaben sind pillepalle zu dem, was einem später begegnet.
Mich würde ja interessieren, was da dahinter steckt. Denn das passt
alles hinten und vorne nicht zusammen.
Er will/soll/muss Aufgaben lösen, die in einem 300 Seiten Lehrbuch
irgendwo bei Seite 250 angesiedelt sind, scheitert aber an
Detailproblemen, die bereits bei Seite 40 hätten beherrscht werden
sollen.
Wenn ich sowas schon sehe
1
intmain()
2
{
3
intmynumbers[]={4,12,9,10,7,13,18,6,15,24,5};
4
int*feld=NULL;
5
intanzahl=11;
6
7
feld=mynumbers;
8
create_tree(feld,anzahl);
wird mir schlecht. Alleine in diesen 5 Zeilen ist so dermassen viel
Unwissen und nicht Verstandenes erkennbar, dass mir Angst und Bang wird.
Für einen Neuling wäre das ok. Neulinge schreiben gerne mal unnötig
komplexen und unflexiblen Code, der dann auch noch um einiges länger
ist, als die simple flexible Lösung und bauen dumme Fehler ein die sie
nicht bemerken, obwohl er förmlich "bitte hier!" schreit. Aber ein
Neuling versucht sich nicht an dynamischen Datenstrukturen.
Hmm. Wenn ich mirs recht überlege: Nein, ich wills gar nicht wissen.
Thread beobachten
Seitenaufteilung abschalten