Binärer Suchbaum -> Anzahl der Blätter, Höhe

[planlos++ 0]

Hallo zusammen!

Muss übermorgen eine C++ Klausur schreiben und bin noch recht planlos!
Versuche eine Funktion zu schreiben, die die Anzahl der Blätter eines binären Suchbaums angibt.

Ausgehend von:

struct BinBaumKnoten {
int nutzinfo;
BinBaumKnoten *lSohn, *rSohn;

habe ich Folgendes:

int anzahlBlaetter (BinBaumKnoten *b){
if (b==NULL) return 0;
if (b-> rSohn != NULL && b-> lSohn != NULL) return O;
else return 1 + anzahlBlaetter(b->rSohn) + anzahlBlaetter(b->lSohn)
}

das macht aber irgendwie was Falsches^^
Ich hoffe jemand kann mir helfen!

Und zu guter Letzt: Ich versuche auch eine Funktion zu schreiben, die die Höhe eines binären Suchbaumes angibt! Da hab ich ma gar keine Ahnung.
Danke schon mal im vorraus!

[Gast]

Hi,

in deinem zweiten if ist etwas verkehrt Schau mal auf das if da drüber.
Btw: Im Magazin gibts nen Artikel über Bäume.

Edit: Du darfst auch nur in dein "Blatt" runtergehen, falls es existiert, unabhängig von dem Nachbar-Blatt.
Edit2: Ach wird ja abgefangen

[Bashar]

wahrscheinlich ist O != 1
Die Höhe kriegt man auch rekursiv: Ein leerer Baum hat die Höhe 0, alle anderen Bäume haben die Höhe 1 + Maximum(Höhe(links), Höhe(rechts))

[.filmor]

unsigned anzahlBlaetter (const BinBaumKnoten* b)
{
    if (b == 0)
        return 0;
    if (b->rSohn == 0 && b->lSohn == 0)
        return 1;
    return anzahlBlaetter(b->rSohn) + anzahlBlaetter(b->lSohn);
}

unsigned hoehe(const BinBaumKnoten* b)
{
    if (b == 0)
        return 0;
    return 1 + std::max(hoehe(b->lSohn), hoehe(b->rSohn));
}

Rekursiv denken

[planlos++ 0]

Ah cool, Leute das hilft schon mal!
Besten Dank! Bin jetz aber noch auf ein weiteres Problem gestossen^^ hehe
passt zwar nicht zu den Bäumen, aber ich schreibs trotzdem mal hier rein:

Ich versuche, ausgehend von dieser Struktur / verketteten Liste:

struct ListElem {
int inhalt;
ListElem* weiter;
};

eine Funktion zu schreiben, die ein beliebiges Element, bzw. eins was man sich dann aussuchen kann, löscht. Das hab ich bereits hingebracht:

loeschenAnPos (ListElem* liste, int pos){
if (liste == NULL)
return 0;
if (pos == 1){
ListElem * a = new ListElem;
a = liste -> weiter;
delete liste;
return a;
}
}
So also der Fall, falls es an erster Stelle ist, hätt ich dann^^ aber wie könnt es weiter gehen ?
Hoffe hier kann mir genauso gut geholfen werden.
Danke

[gast12342315]

Listenelement *Entferne (int i, Listenelement *L)
{
if (L == NULL)
return L;
else if (L ->Nutzinfo == i)
return L->weiter;
else {
L->weiter = Entferne (i, L->weiter);
return L;
}
}

[planlos++ 0]

Danke für die Anregung!