c:tree:binarysearch

[Kerli]

Lässt sich compilieren liefert aber bei der Ausführung nen Segmentation fault.

Ich hab genau das gleiche Problem. Ich hab mir das jetzt einmal im Debugger angeschaut und der Grund dafür war das 'root' nicht initialisiert wird und der Zeiger auf das RootElement deshalb auf eine zufällige Stelle zeigt. Man muss also nur in Zeile 157 root mit Null initialisieren:

Code: Alles auswählen

struct BinaryTreeRoot root = { NULL };

[stampuhh]

Weiterhin vergisst Du root wieder freizugeben.

Beschreibe mir mal Deine Entwicklungsumgebung, damit ich das nachvollziehen kann.

Ja habe bisher auch nur versucht es überhaupt zum laufen zu bekommen

Entwicklungsumgebung ist Codeblocks auf Ubuntu 9.04 mit gcc.

Komischerweise habe ich VOR dem Aufruf der insert()-Funktion noch eine Test-Ausgabe gemacht um zu gucken wo der Fehler auftritt. Sie wurde nie ausgegeben sondern der Fehler kam immer zuvor...deswegen hab ich auch nur durch Zufall den Fehlerort gefunden weil ich dachte der muss vor der Ausgabe liegen
Kann mir das wer erklären?

edit @Kerli:Ja so etwas hatte ich gesucht. Wusste nur leider nicht dass das mit den Klammern geht. Einfach nur "= NULL" lies sich nicht compilieren

gruß stampuhh

[Kerli]

Komischerweise habe ich VOR dem Aufruf der insert()-Funktion noch eine Test-Ausgabe gemacht um zu gucken wo der Fehler auftritt. Sie wurde nie ausgegeben sondern der Fehler kam immer zuvor...deswegen hab ich auch nur durch Zufall den Fehlerort gefunden weil ich dachte der muss vor der Ausgabe liegen
Kann mir das wer erklären?

War denn in deiner Fehlermeldung auch ein Newline drinnen? Wenn nicht dann wird der Ausgabestream einfach noch nicht geflusht worden sein...

[stampuhh]

In der Fehlermeldung nicht aber davor halt die beiden Newlines von der Zeile

Code: Alles auswählen

 printf( "\n--- Initialisierung--------------------------\n\n" )

naja dann denke ich mal wird es das sein

Haben den Fehler ja gefunden.

gruß stampuhh

[Xin]

naja dann denke ich mal wird es das sein

Haben den Fehler ja gefunden.

Bitte die Lösung von Kerli bevorzugen ^^
Ich bin schon zu sehr Klassen gewohnt - wozu gibt es schließlich Konstruktoren!? ^^
Hier wird das Problem gelöst, malloc alleine mag die Symptome zu beseitigen, aber das Problem bleibt weiterhin bestehen.

[stampuhh]

Ja finde die Lösung auch besser. Komme ja aus dem Javabereich und hätte es da ähnlich gelöst. Mir war nur nicht klar wie genau man das löst

Aber so lernt man dazu.

Edit: Ich habe mir gerade noch mal diese Zeilen angeschaut:

Code: Alles auswählen

void DeleteElement( struct BinaryTreeRoot * root, struct BinaryTree * element, int recursive )
{
    if ( recursive )
    {
        if ( element->Left  ) DeleteElement( root, element->Left,  1 );
        if ( element->Right ) DeleteElement( root, element->Right, 1 );
    }
    else
    {
        if ( element->Superiour == root->RootElement )
            root->RootElement = NULL;
        else if ( element->Superiour->Left == element )
            element->Superiour->Left = NULL;
        else
            element->Superiour->Right = NULL;

        if ( element->Left  ) insert( root, element->Left );
        if ( element->Right ) insert( root, element->Right );

        free( element );
    }
}

Den "normalen" Teil verstehe ich ja, aber den rekursiven irgendwie nicht. Da wird doch nichts gemacht? Immer wieder rekursiv aufgerufen wenn es noch Kinder gibt...mehr aber auch nicht oder bin ich einfach zu müde gerade?

gruß stampuhh

[Xin]

Ja finde die Lösung auch besser. Komme ja aus dem Javabereich und hätte es da ähnlich gelöst. Mir war nur nicht klar wie genau man das löst

Den "normalen" Teil verstehe ich ja, aber den rekursiven irgendwie nicht. Da wird doch nichts gemacht? Immer wieder rekursiv aufgerufen wenn es noch Kinder gibt...mehr aber auch nicht oder bin ich einfach zu müde gerade?

Du lieferst mir gerade ein Argument gegen Java und C#...

In C++ gibt es keinen GarbageCollector. Wenn Du einen ganzen Zweig abklemmst, dann musst Du erst die Unterzweige auch löschen. Hier werden erst die Unterzweige gelöscht, damit wird das zu löschende Element zu einem Blatt, was schlussendlich gelöscht werden kann.

[stampuhh]

Ich verstehe es nicht. Aus meiner Sicht passiert da nichts. Wenn ich ein

Code: Alles auswählen

Delete( &root, 6, 1 );

aufrufe ist Element 6 nachher immer noch da. Also wenn ich das richtig sehe wird auch immer wieder rekursiv die Funktion DeleteElement aufgerufen, geguckt ob ein Kind vorhanden ist, wenn ja dann wird sie wieder aufgerufen, wenn nicht passiert nichts. Bei dem Aufruf oben hab ich dann insgesamt 3 Aufrufe der Funktion aber mehr auch nicht. Es wird nie ein free(element) ausgeführt.

In C++ gibt es keinen GarbageCollector. Wenn Du einen ganzen Zweig abklemmst, dann musst Du erst die Unterzweige auch löschen.

Ist dieses Löschen der Unterzweige hier in diesem Beispiel auch nötig? Oder warum verstehe ich den Sinn dahinter gerade nicht. Bei einem Aufruf von

Code: Alles auswählen

Delete( &root, 4, 0 );

wird das doch auch gar nicht gemacht.

Also entweder da stimmt was am Code nicht oder ich checks einfach gerade nicht, weiß aber nicht wo mein Denkfehler ist

Du lieferst mir gerade ein Argument gegen Java und C#...

Warum? Mir war schlicht die Schreibweise für C nicht bekannt

gruß stampuhh

[Xin]

Ich verstehe es nicht. Aus meiner Sicht passiert da nichts. Wenn ich ein

Code: Alles auswählen

Delete( &root, 6, 1 );

aufrufe ist Element 6 nachher immer noch da. Also wenn ich das richtig sehe wird auch immer wieder rekursiv die Funktion DeleteElement aufgerufen, geguckt ob ein Kind vorhanden ist, wenn ja dann wird sie wieder aufgerufen, wenn nicht passiert nichts. Bei dem Aufruf oben hab ich dann insgesamt 3 Aufrufe der Funktion aber mehr auch nicht. Es wird nie ein free(element) ausgeführt.

Gna...
Das else gehört da gar nicht rein.
Wie schon gesagt... nicht wirklich getester Code. ^^

Code: Alles auswählen

void DeleteElement( struct BinaryTreeRoot * root, struct BinaryTree * element, int recursive )
{
    if ( recursive )
    {
        if ( element->Left  ) DeleteElement( root, element->Left,  1 );
        if ( element->Right ) DeleteElement( root, element->Right, 1 );
    }

    if ( element == root->RootElement )             // <- Zeile wurde geändert, vorher element->Superiour...
        root->RootElement = NULL;
    else if ( element->Superiour->Left == element )
        element->Superiour->Left = NULL;
    else
        element->Superiour->Right = NULL;

    if( !recursive )                  // <- hier wäre das else gefragt gewesen
    {
        if ( element->Left  ) insert( root, element->Left );
        if ( element->Right ) insert( root, element->Right );
    }

    free( element );
}

Ich muss auch sagen, dass ich das so nicht wirklich gerne implementieren würde, sondern lieber mit Referenzen auf Zeigern arbeiten würde.

[stampuhh]

Also das Löschen funktioniert. Allerdings ist ja jetzt der ganze Baum weg wenn ich z.B. nur die Wurzel löschen will...

also steht das Rekursive für "Lösche Teilbaum" und wenn ich die ganze Funktion mit nicht rekursiv (0) aufrufe lösche ich ein einzelnes Element.

Dann ergibt auch das rekursive einen Sinn

gruß stampuhh