Haben als HÜ, damit wir die Rekursionen besser lernen die Aufgabe gestellt bekommen mit einem Baum 2 Zahlen zu addieren. Klingt zwar irgendwie leicht, ich kenne mich damit leider wenig aus.
Vielleicht kann mir jemand helfen?
mfg Sabine
[…] mit einem Baum 2 Zahlen zu addieren.
Ist das etwa die vollständige Aufgabenbeschreibung?
Servus
Tom
Ja, mehr nicht, aber ich weiß leider trotzdem nicht wie es geht. Kannst du mir weiterhelfen?
Ja, mehr nicht, aber ich weiß leider trotzdem nicht wie es
geht. Kannst du mir weiterhelfen?
Tut mir leid, ohne genauere Informationen darüber, was der Aufgabensteller erwartet, könnte ich nur wild spekulieren.
Lediglich ein paar Denkanstöße zum Thema „Baum und Rekursion“ kann ich liefern…
Beschränken wir uns mal auf Binärbäume, also Bäume, in denen jeder Knoten maximal zwei Kinder hat.
Die rekursive Definition so eines Baumes lautet: „Ein Baum besteht aus einem Knoten und null bis zwei (Teil-)Bäumen“.
Wenn wir jetzt noch festlegen dass ein Baum bzw. sein Knoten einen (Zahlen-)Wert hat, können wir mit Bäumen rechnen. Man könnte zum Beispiel festlegen, dass der Wert eines Baumes die Summe seiner Teilbäume ist.
Die Rekursion terminiert jeweils in den „Blättern“, das sind Knoten ohne Teilbäume. Wenn wir alle Blätter mit Zahlen vorbelegen, hat der Wurzelknoten als Wert die Summe aller Blatt-Werte.
Servus
Tom
Vermutlich …
Hallo,
… ist ein Baum gemeint, bei dem die Blätter Werte annehmen und Knoten Operationen repräsentieren - der Baum stellt dann den gesamten arithmetischen Ausdruck dar. Wäre zumindest eine typische Aufgabenstellung, bei der Rekursion elegant ist.
Gruss
Enno
Tja, ich kann leider auch nur den bestehenden Code anbieten. Vielleicht kann man damit was anfangen?
#include
struct knoten {
int info;
knoten *li;
knoten *re;
};
knoten* einfuegen(knoten *baum,int info)
{
if (baum==0)
{
baum=new knoten;
baum->info=info;
baum->li=NULL;
baum->re=NULL;
return baum;
}
else
{
if (baum->info>info)
baum->li=einfuegen(baum->li,info);
else
baum->re=einfuegen(baum->re, info);
return baum;
}
}
void darstellen(knoten *baum)
{
if (baum !=NULL)
{
printf("%i ->", baum->info);
darstellen(baum->li);
darstellen(baum->re);
}
}
void loeschen(knoten *baum)
{
if (baum!=NULL)
{
loeschen(baum->li);
loeschen(baum->re);
delete baum;
}
}
void main()
{
knoten *baum;
baum=NULL;
baum=einfuegen(baum, 3);
baum=einfuegen(baum, 4);
baum=einfuegen(baum, 1);
darstellen(baum);
loeschen(baum);
}
[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]
hi sabine,
also, mir ist das was du da an code geliefert hast völlig suspekt
#include
// das hier sollte glaube ich deine classe sein oder?
// ansonsten sehr merkwuerdig, denn unten willst du doch doch eine instanz der klasse
// anlegen.
// siehe unten…
struct knoten {
int info;
knoten *li;
knoten *re;
};knoten* einfuegen(knoten *baum,int info)
{
if (baum==0)
{
// so hier ist jetzt das was ich nicht verstehe…hier sagst du
baum=new knoten;
// was bedeuten wuerde das du eine instanz deiner klasse bildest…
// aber egal…ich kann dir lediglich aus zeitgruenden jetzt den algorithmuzs angeben,
// denn ich muesste mich jetzt sonst ersteinmal wieder in c++ einarbeiten,
// und dann deinen code bei mir zu laufen kriegen. aber ich werde dir weiter
// unten den algorithmus aufschreiben…
baum->info=info;
baum->li=NULL;
baum->re=NULL;
return baum;
}
else
{
if (baum->info>info)
baum->li=einfuegen(baum->li,info);
else
baum->re=einfuegen(baum->re, info);
return baum;
}
}void darstellen(knoten *baum)
{
if (baum !=NULL)
{
printf("%i ->", baum->info);
darstellen(baum->li);
darstellen(baum->re);
}}
void loeschen(knoten *baum)
{
if (baum!=NULL)
{
loeschen(baum->li);
loeschen(baum->re);
delete baum;
}
}void main()
{
knoten *baum;
baum=NULL;
baum=einfuegen(baum, 3);
baum=einfuegen(baum, 4);
baum=einfuegen(baum, 1);
darstellen(baum);
loeschen(baum);
}
so. folgendes muss jetzt dein algorithmus machen. er muss solange die knoten abgehen, bis er ein blatt gefunden hat, blaetter sind gekennzeichnet durch ein NULL daran.
das ganze ist kein ausgeglichener baum, ist aber hier auch egal.
int berechne (knoten)
{
// gibt es keinen linken nachbar mehr
if (knoten->li==NULL)
{
// dann, wenn es aber einen rechten nachbar gibt,
// addiere mit der rekursion der berechnung des rechten knoten
if (knoten->re!=NULL)
return knoten->info+berechne(knoten->re);
// ansonsten haben wir ein blatt gefunden, und geben nur den wert des blattes zurueck
else return knoten->info;
}
// wenn es einen linken nachbar gibt
// und auch einen rechten dann addiere mit rechter und linker rekursion
else if (knoten->re!=NULL)
return knoten->info+berechne(knoten->li)+berechne(knoten->re);
//ansonsten addiere mit der rekursion mit dem linken nachbarn
else return knoten->info+berechne(knoten->li);
}
// damit sollten dann alle 4 faelle behandelt worden sein,
// 1. fall 2 nachbarknoten
// 2. fall linker nachbarknoten
// 3. fall rechter nachbarknoten
// 4. falls kein nachbarknoten
// ich hab leider oben die reihenfolge nicht beachtet…
// schick an der rekursion ist das man ohne grossen programmieraufwand
// viel erreichen kann. eine loesung mit einer while schleife kaeme
// hier zwar auch in frage, wuerde aber den code aufblaehen, und sehr unuebersichtlich sein
// jetzt gehst du also stueck fuer stueck deinen baum ab, spaeter bist du dann irgenwann bei // deinem blatt angelangt, und beendest dann fuer diesen zweig die rekursion.
// alles was hier geschrieben ist, ist pseudocode und muss noch richtig umgesetzt werden.
// falls du noch fragen hast dann mail mir einfach
grützi
josh
so. folgendes muss jetzt dein algorithmus machen.
[…]
Woher weißt du das? Das eigentliche Problem ist doch, dass keine exakte Aufgabenstellung bekannt ist.
Servus
Tom
hi thomas,
naja, wenn du dir den source code von ihr anschaust, dann liegt die loesung doch eigentlich auf der hand. mein prog ist rekursiv, wie gewuenscht, und loest das in der aufgabenstellung gestellte problem. die funktionen die sie vorgegeben hat, lassen eigentlich vom logischen her keine andere rekursive loesung meoglich oder?
Woher weißt du das? Das eigentliche Problem ist doch, dass
keine exakte Aufgabenstellung bekannt ist.Servus
Tom
cu josh
mein prog ist rekursiv, wie gewuenscht, und loest das in der
aufgabenstellung gestellte problem. die funktionen die sie
vorgegeben hat, lassen eigentlich vom logischen her keine
andere rekursive loesung meoglich oder?
Ich bestreite nicht, dass dein Lösungsvorschlag wahrscheinlich ins Schwarze trifft. Vielmehr wollte ich nochmal darauf herumreiten, dass (und jetzt wiederhole ich mich) keine exakte Aufgabenstellung bekannt ist. Ich persönlich würde mich unter solchen Umständen weigern, ohne Rückfrage drauflos zu programmieren. 
Servus
Tom
OT: RE: Thomas. ok 
OT: RE: Thomas. ok