Forum
 
Fragen
 
Suchen
 
Über Uns
 
 

Rekursiv Verzweigungen zählen in einem Baum
Neue Frage »

11.01.2016, 12:44 Auf diesen Beitrag antworten »
Chirs Rekursiv Verzweigungen zählen in einem Baum

Meine Frage:
Hallo zusammen,

ich hätte eine Frage zur Vertiefung der Bäume. Und zwar habe ich bereits einige Aufgabe in meinem Studium zu den Bäumen gelöst ich möchte aber gerne dieses Wissen erweitern und hab mir nun selbst eine Aufgabe ausgedacht und zwar:

Wenn es möglich ist rekursiv Texte in einem Baum zu zählen bzw. den längsten Text zu ermitteln, dann müsste es auch möglich sein rekursiv die Verzeigungen in einem Baum zu zählen.


Doch leider stecke ich zur Zeit in der Überlegung fest wie ich die Anzahl der Verzweigungen in einem Textbaum feststelle.


Vielleicht kann mir hier jemand weiterhelfen.



Ich bedanke mich schon mal im Voraus



VG,


Chris

Meine Ideen:
Meine Idee ist nun eine Rekursive C-Funktion zu schreiben die die Verzweigungen in einem Textbaum zählt.
 
 
11.01.2016, 13:13 Auf diesen Beitrag antworten »
eulerscheZahl

Setze das Ergebnis auf 0.
Wenn das rechte (bzw. linke) Kind vorhanden ist, gibt es da schonmal eine Verzweigung, also muss diese zum Ergebnis addiert werden.
Hinzu kommen dann noch die Verzweigungen der Kinder selbst.

Das Ergebnis sollte um 1 kleiner sein, als die Anzahl der Knoten.
13.01.2016, 14:48 Auf diesen Beitrag antworten »
Chirs

Danke für den Tipp smile
Für den Vergleich mit den Knoten müsste ich aber jedoch eine zweite Rekursive Funktion schreiben, die die Anzahl der Konten zurück gibt.

ich hab jetzt fürs Erste diesen Ansatz erarbeitet:
code: 
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:

 int verzweigungen(textbaum *b)
{ if (b==NULL)
return;

else return 
{
1+(verzweigung(b->left)+verzweigung(b->right));

}


Ich vermute allerdings, dass ich noch eine Variable n definieren soll und diese dann nach jedem Durchlauf zyklisch nach oben zählen sollte.
13.01.2016, 16:59 Auf diesen Beitrag antworten »
eulerscheZahl

Ich würde zwei Funktionen schreiben. Eine, die rekursiv die Anzahl der Knoten zählt (da muss man nichts abziehen) und eine zweite, die die erste aufruft und deren Ergebnis-1 zurückgibt.
Und deine 3. Zeile ist falsch, da du einen Rückgabewert brauchst.
 Anzeige
 
14.01.2016, 14:03 Auf diesen Beitrag antworten »
Chirs

Danke für den Hinweiß hab die Null vergessen Augenzwinkern

Ja ich galube du hast recht so ist es eindeutig einfacher und besser


Grüße
15.01.2016, 16:12 Auf diesen Beitrag antworten »
Chirs

Sry dass ich nochmal nachfrage aber was wäre denn z.B. wenn ich irgendwann mal so eine Prüfungsaufgabe bekommen würde. In der ich eine Funktion schreiben soll die die Verzweigungen in einem Baum zählt.

Könnte ich dann meine Funktion verwenden ?
15.01.2016, 16:34 Auf diesen Beitrag antworten »
eulerscheZahl

Wenn dein Baum aus einem einzigen Knoten besteht, gibst du eine 1 zurück. Mit wem ist der Knoten denn verbunden?
So sollte es klappen:
code: 
1:
2:
3:

result = (verzweigung(b->left)+verzweigung(b->right)); //Verzweigungen der Kinder zählen
if (b->left != NULL) result++; //Verzweigung zum linken Kind addieren
if (b->right != NULL) result++; //und zum rechten
15.01.2016, 17:04 Auf diesen Beitrag antworten »
Chirs

Danke für den Denkanstoß smile
Leider darf ich es in der Prüfung nicht so wie du es programmiert hast machen.
Weißt du zufällig ob mein Code auch funktionieren würde ?
code: 
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:

int verzweigungen(textbaum *b)
{
if (b==NULL)
return 0;

else if (b->left == NULL) && (b->right == NULL) 
return 1;

else return 1+(verzweigung(b->left)+verzweigung(b->right)); 

};
15.01.2016, 17:11 Auf diesen Beitrag antworten »
eulerscheZahl

Stelle dir mal einen Baum mit 3 Knoten vor:
code: 
1:
2:
3:

   a
  / \
 b   c

Für b und c wirst du jeweils 1 zurückgeben (Zeile 7).
Für a hast du also durch die rekursiven Aufrufe schon 2. Darauf addierst du noch 1, hast also 3. Ich zähle aber nur 2 Verbindungen.
15.01.2016, 17:45 Auf diesen Beitrag antworten »
Chirs

Stimmt du hast recht also muss ich die 1+.... weglassen dann müsste es funktionieren smile

Danke dir du hast mir sehr geholfen Daumen hoch
16.01.2016, 06:30 Auf diesen Beitrag antworten »
eulerscheZahl

Habe nochmal drüber nachgedacht: jetzt scheiterst du nur noch, wenn der Baum ausschließlich aus dem Wurzelknoten besteht.
16.01.2016, 10:06 Auf diesen Beitrag antworten »
Chirs

Ich habe auch nochmal darüber nachgedacht in der Zeile 10 muss eine ODER und kein UND stehen weil wenn es ein UND ist dann existiert in einem Baum nur die Wurzel und dann hat der Baum keinerlei Verzweigungen.

Ich habe jetzt den Terminierungsfall,wenn der Baum nur aus Wurzel besteht auch abgedeckt (Zeile 7). Da hier ja keine Verzeigungen auftreten.

Grüße.
code: 
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:


int verzweigungen(textbaum *b)
{
if (b==NULL)
return 0;

else if (b->left == NULL) && (b->right == NULL) 
return 0;

else if (b->left == NULL) || (b->right == NULL) 
return 1;

else return (verzweigung(b->left)+verzweigung(b->right));
16.01.2016, 11:09 Auf diesen Beitrag antworten »
eulerscheZahl

Jetzt hat der Baum mit den 3 Knoten von oben ja gar keine Verzweigungen mehr geschockt
Ich komme mir langsam vor wie Captain Hindsight.
17.01.2016, 17:41 Auf diesen Beitrag antworten »
Chirs

Meine Terminierungsfälle sind doch:

Wenn b leer return 0
Wenn b->left oder b->right == NULL return 1

Aber wo ich noch nicht ganz durchgeblickt habe ist dass ich doch eigtl noch zwei weitere Terminierungsfälle habe und zwar wenn b->left und b->right !=0 sind es ja zwei Verzweigungen und wenn b->left und b->right = 0 habe ich keine Verzweigung.

Wie sollte ich es dann deiner Meinung nach aufbauen ?


Sry für die Anfängerfrage. Würde mich freuen wenn du mir weiterhelfen könntest.


Grüße
17.01.2016, 17:48 Auf diesen Beitrag antworten »
eulerscheZahl

Es gibt 2 Terminierungsfälle:
Der Knoten selbst ist NULL oder BEIDE Kinder sind NULL (eins reicht nicht, damit kannst du immer noch eine Liste bauen). Wenn wir im 2. Fall trotzdem weitermachen, schadet das aber nicht: dann wird die Funktion mit NULL aufgerufen und wir sind wieder bei Fall 1 (der muss sowieso abgedeckt werden).

Was gibt es denn daran auszusetzen, dass du das nicht nehmen darfst?
code: 
1:
2:
3:
4:
5:

if (b == NULL) return 0;
return verzweigung(b->left) + 
    verzweigung(b->right) + 
    (b->left == NULL)?0:1 + 
    (b->right == NULL)?0:1;
17.01.2016, 17:58 Auf diesen Beitrag antworten »
Chirs

Danke für die Antwort, weil ich es in diesem Stil programmieren sollte:
code: 
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:

int verzweigungen(textbaum *b)
{
if (b==NULL)
return 0;

else if (b->left == NULL) && (b->right == NULL) 
return 1;

else return (verzweigung(b->left)+verzweigung(b->right)); 

};


Dann würde doch dieser Code funktionieren oder ? Da ich beide Terminierungsfälle abgedeckt habe.


Grüße
17.01.2016, 18:00 Auf diesen Beitrag antworten »
eulerscheZahl

Hatten wir das nicht schon?
Damit kriegst du bei einem Baum aus einem einzigen Knoten 1 raus.
17.01.2016, 18:03 Auf diesen Beitrag antworten »
Chirs

Ja genau soweit waren wir aber wie soll ich das dann einbauen, dass es bei einem Knoten keine Verzweigung gibt ?

Weil daran verzweifle ich gerade ein wenig. verwirrt

Grüße
17.01.2016, 18:05 Auf diesen Beitrag antworten »
eulerscheZahl

Mir fällt auch nichts besseres ein als der Code, den ich eben geschrieben habe, oder das Zählen aller Knoten und anschließende Subtrahieren von 1.
17.01.2016, 18:09 Auf diesen Beitrag antworten »
Chirs

Ok danke trotzdem. smile

Kann man deinen Code auch ohne ? schreiben also in solcher Form wie ich den meinen geschrieben habe ? Weil ich leider diesen Operator nicht benutzen darf.


Grüße
17.01.2016, 18:11 Auf diesen Beitrag antworten »
eulerscheZahl

Ja, aber dann musst du das Ergebnis zwischenspeichern.
17.01.2016, 18:15 Auf diesen Beitrag antworten »
Chirs

Ok danke dir

Ich glaub es ist wirklich einfacher es in zwei Funktionen zu packen und erst die Knoten zu zählen.


Vielen Dank für deine Hilfe.
 
Neue Frage »
Antworten »


Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »


Informatiker Board » Themengebiete » Praktische Informatik » Algorithmen » Rekursiv Verzweigungen zählen in einem Baum

 
© 2005-2019 bei Informatikerboard.de | Archiv, alt, neueste | Kontakt | Jugendschutz | Nutzungsbedingungen