C - Bäume

[stampuhh]

Hey,

ich habe es mal wieder geschafft etwas weiter zu machen mit dem Tutorial. Beziehungsweise versucht
Ich bin im Moment bei den Bäumen. Da dort aber nicht mehr gegeben ist als ein Ansatz fehlt mir der Rest. Also hab ich einfach mal ein bisschen rum probiert.

Der Code funktioniert unter Linux ohne Probleme. Jetzt hab ich das ganze einfach mal auf Windows gestartet: "baeume.exe hat ein Problem festgestellt [...]"
Also brauch ich wohl mal wieder eure Hilfe. Habe mich bei der main etwas nach dem Abschnitt Listen orientiert.

Code: Alles auswählen

#include <stdio.h>
#include <stdlib.h>

struct Address
{
    int  Number;
};

struct AddressTreeElement
{
    struct AddressTreeElement * Superior;       // übergeordnetes Element  (optional)

    struct AddressTreeElement * Left, * Right;  // Nachfolgende Elemente

    struct Address              Data;
};

struct AddressTreeRoot
{
    struct AddressTreeElement * Root;

    int                         Elements;
};

struct AddressTreeRoot * newAddressTree();

struct AddressTreeElement * newTreeElement(struct AddressTreeRoot * root, struct Address data);

void insertTreeNode(struct AddressTreeRoot * root, struct AddressTreeElement * newTreeElem);
int BaumAusgabe(struct AddressTreeElement * root);

struct AddressTreeElement * searchKey(struct AddressTreeElement * root, struct Address key);

int main()
{
    struct AddressTreeRoot * tree;
    struct AddressTreeElement * element;
    struct Address addy;
    tree = newAddressTree();

    addy.Number = 1;
    element = newTreeElement(tree, addy);

    addy.Number = 7;
    element = newTreeElement(tree, addy);

    addy.Number = 4;
    element = newTreeElement(tree, addy);

    BaumAusgabe(tree->Root);
    return 0;
}

struct AddressTreeElement * newTreeElement(struct AddressTreeRoot * root, struct Address data)
{
    struct AddressTreeElement * newNode = (struct AddressTreeElement *) malloc( sizeof( struct AddressTreeElement ) );

    //Muss ja nach irgendetwas sortiert werden
    newNode->Data = data;
    insertTreeNode(root, newNode);

    return newNode;
}
struct AddressTreeRoot * newAddressTree()
{
    struct AddressTreeRoot * newTree = (struct AddressTreeRoot *) malloc( sizeof( struct AddressTreeRoot ) );

    newTree->Root = NULL;
    return newTree;
}

void insertTreeNode(struct AddressTreeRoot * root, struct AddressTreeElement * newTreeElem)
{
    struct AddressTreeElement * y = NULL;
    struct AddressTreeElement * x = root->Root;

    while (x != NULL)
    {
        y = x;
        if (newTreeElem->Data.Number < x->Data.Number)
        {
            x = x->Left;
        }
        else
        {
            x = x->Right;
        }
    }

    newTreeElem->Superior = y;
    if (y == NULL)
    {
        root->Root = newTreeElem;
    }
    else
    {
        if (newTreeElem->Data.Number < y->Data.Number)
        {
            y->Left = newTreeElem;
        }
        else
        {
            y->Right = newTreeElem;
        }
    }

}

int BaumAusgabe(struct AddressTreeElement * root)
{
    if (!root) return 0;

    BaumAusgabe(root->Left);
    printf("key von X: %d\n", root->Data.Number);
    BaumAusgabe(root->Right);

    return 1;

}

struct AddressTreeElement * searchKey(struct AddressTreeElement * root, struct Address key)
{
    //kommt noch..
    return root;
}

gruß stampuhh

[cloidnerux]

Naja, köntest du sagen was Windows noch zusätzlich ausgibt zu der Fehlermeldung, denn ich kann keinen Fehler im Code finden.
Ich sehe aber, das du jedem Knoten im Baum, das selbe Baumelemnt zuweist(addy), da du immer nur die Referenz auf das selbe Objekt festlegst, und dann etwas veränderst, müsste Theoretisch jedes Datenfeld eines jeden Baumknoten den Wert 4 haben, was evt zu Komplikationen bei deinem Suchalgorithmus führen könnte.

[Xin]

Du initialisierst Links und Rechts nicht.
Also sind da zufällige Werte drin.

Visual C++ initialisiert die Werte automatisch: Und zwar absichtlich mit Müll, damit es möglichst immer kracht, statt nur willkürlich.

[stampuhh]

@cloidnerux: also unter Linux funktioniert das so prima
Auch die Ausgabe nachher klappt ja einwandfrei...werds aber trotzdem mal ausprobieren mit einem Wert für jeden Knoten

@Xin: Benutze zwar kein VC++ sondern MinGW aber das könnte auch ein Problem sein. Teste das grade ebend.

edit:

Code: Alles auswählen

#include <stdio.h>
#include <stdlib.h>

struct Address
{
    int  Number;
};

struct AddressTreeElement
{
    struct AddressTreeElement * Superior;       // übergeordnetes Element  (optional)

    struct AddressTreeElement * Left, * Right;  // Nachfolgende Elemente

    struct Address              Data;
};

struct AddressTreeRoot
{
    struct AddressTreeElement * Root;

    int                         Elements;
};

struct AddressTreeRoot * newAddressTree();

struct AddressTreeElement * newTreeElement(struct AddressTreeRoot * root, struct Address data);

void insertTreeNode(struct AddressTreeRoot * root, struct AddressTreeElement * newTreeElem);
int BaumAusgabe(struct AddressTreeElement * root);

struct AddressTreeElement * searchKey(struct AddressTreeElement * root, struct Address key);

int main()
{
    struct AddressTreeRoot * tree;
    struct AddressTreeElement * element;
    struct Address addy;
    tree = newAddressTree();


    addy.Number = 1;
    element = newTreeElement(tree, addy);


    addy.Number = 7;
    element = newTreeElement(tree, addy);


    addy.Number = 4;
    element = newTreeElement(tree, addy);



    BaumAusgabe(tree->Root);
    return 0;
}

struct AddressTreeElement * newTreeElement(struct AddressTreeRoot * root, struct Address data)
{
    struct AddressTreeElement * newNode = (struct AddressTreeElement *) malloc( sizeof( struct AddressTreeElement ) );

    //Muss ja nach irgendetwas sortiert werden
    newNode->Superior = NULL;
    newNode->Left = NULL;
    newNode->Right = NULL;

    newNode->Data = data;
    insertTreeNode(root, newNode);

    return newNode;
}
struct AddressTreeRoot * newAddressTree()
{
    struct AddressTreeRoot * newTree = (struct AddressTreeRoot *) malloc( sizeof( struct AddressTreeRoot ) );

    newTree->Root = NULL;
    return newTree;
}

void insertTreeNode(struct AddressTreeRoot * root, struct AddressTreeElement * newTreeElem)
{
    struct AddressTreeElement * y = NULL;
    struct AddressTreeElement * x = root->Root;

    while (x != NULL)
    {
        y = x;
        if (newTreeElem->Data.Number < x->Data.Number)
        {
            x = x->Left;
        }
        else
        {
            x = x->Right;
        }
    }

    newTreeElem->Superior = y;
    if (y == NULL)
    {
        root->Root = newTreeElem;
    }
    else
    {
        if (newTreeElem->Data.Number < y->Data.Number)
        {
            y->Left = newTreeElem;
        }
        else
        {
            y->Right = newTreeElem;
        }
    }

}

int BaumAusgabe(struct AddressTreeElement * root)
{
    if (!root) return 0;

    BaumAusgabe(root->Left);
    printf("key von X: %d\n", root->Data.Number);
    BaumAusgabe(root->Right);

    return 1;

}

struct AddressTreeElement * searchKey(struct AddressTreeElement * root, struct Address key)
{
    //kommt noch..
    return root;
}

@Xin: So läuft es jetzt.

Danke ihr beiden für eure Hilfe.

gruß stampuhh

[stampuhh]

So ich habe noch etwas weiter gebastelt und eine Suche und Löschen für bestimmte Knoten implementiert.

Code: Alles auswählen

#include <stdio.h>
#include <stdlib.h>

struct Address
{
    int  Number;
};

struct AddressTreeElement
{
    struct AddressTreeElement * Superior;       // übergeordnetes Element  (optional)

    struct AddressTreeElement * Left, * Right;  // Nachfolgende Elemente

    struct Address              Data;
};

struct AddressTreeRoot
{
    struct AddressTreeElement * Root;

    int                         Elements;
};

struct AddressTreeRoot * newAddressTree();

struct AddressTreeElement * newTreeElement(struct AddressTreeRoot * root, struct Address data);

void insertTreeNode(struct AddressTreeRoot * root, struct AddressTreeElement * newTreeElem);
void deleteTreeNode(struct AddressTreeRoot * root, struct AddressTreeElement * elemToDel);
int BaumAusgabe(struct AddressTreeElement * root);

struct AddressTreeElement * searchKey(struct AddressTreeElement * root, struct Address key);
struct AddressTreeElement * sucheNextChild(struct AddressTreeElement * element);
struct AddressTreeElement * sucheMinimum(struct AddressTreeElement * element);

int main()
{
    struct AddressTreeRoot * tree;
    struct AddressTreeElement * element;
    struct Address addy;
    tree = newAddressTree();


    addy.Number = 3;
    element = newTreeElement(tree, addy);

    addy.Number = 4;
    element = newTreeElement(tree, addy);

    addy.Number = 5;
    element = newTreeElement(tree, addy);

    addy.Number = 6;
    element = newTreeElement(tree, addy);

    addy.Number = 7;
    element = newTreeElement(tree, addy);

    addy.Number = 9;
    element = newTreeElement(tree, addy);

    printf("Key vom Wurzelknoten: %d\n",tree->Root->Data.Number);

    printf("----------------------------------------\n");
    printf("------------Ausgabe---------------------\n");

    BaumAusgabe(tree->Root);

    printf("----------------------------------------\n");
    printf("------------Suche-----------------------\n");

    addy.Number = 3;
    element = searchKey(tree->Root, addy);

    if (element == NULL)
        printf("Nichts gefunden\n");
    else
        printf("%d gefunden!\n", element->Data.Number);

    printf("----------------------------------------\n");
    printf("------------Loeschen---------------------\n");

    deleteTreeNode(tree, element);

    printf("----------------------------------------\n");
    printf("------------Ausgabe---------------------\n");

    BaumAusgabe(tree->Root);

    printf("----------------------------------------\n");
    printf("------------Rest loeschen---------------\n");

    //Umständlich müsste man mit Methode machen auch ohne dass man die einzlenen
    //Elemente und deren Keys kennt...
    addy.Number = 4;
    element = searchKey(tree->Root, addy);

    deleteTreeNode(tree, element);

            addy.Number = 5;
    element = searchKey(tree->Root, addy);

    deleteTreeNode(tree, element);

            addy.Number = 6;
    element = searchKey(tree->Root, addy);

    deleteTreeNode(tree, element);

            addy.Number = 7;
    element = searchKey(tree->Root, addy);

    deleteTreeNode(tree, element);

            addy.Number = 9;
    element = searchKey(tree->Root, addy);

    deleteTreeNode(tree, element);

    if(tree->Root != NULL)
        printf("Key vom Wurzelknoten: %d\n",tree->Root->Data.Number);
    else
        free(tree);

    return 0;
}

struct AddressTreeElement * newTreeElement(struct AddressTreeRoot * root, struct Address data)
{
    struct AddressTreeElement * newNode = (struct AddressTreeElement *) malloc( sizeof( struct AddressTreeElement ) );

    //Muss ja nach irgendetwas sortiert werden
    newNode->Superior = NULL;
    newNode->Left = NULL;
    newNode->Right = NULL;

    newNode->Data = data;
    insertTreeNode(root, newNode);

    return newNode;
}
struct AddressTreeRoot * newAddressTree()
{
    struct AddressTreeRoot * newTree = (struct AddressTreeRoot *) malloc( sizeof( struct AddressTreeRoot ) );

    newTree->Root = NULL;
    return newTree;
}

void insertTreeNode(struct AddressTreeRoot * root, struct AddressTreeElement * newTreeElem)
{
    struct AddressTreeElement * y = NULL;
    struct AddressTreeElement * x = root->Root;

    while (x != NULL)
    {
        y = x;
        if (newTreeElem->Data.Number < x->Data.Number)
        {
            x = x->Left;
        }
        else
        {
            x = x->Right;
        }
    }

    newTreeElem->Superior = y;
    if (y == NULL)
    {
        root->Root = newTreeElem;
    }
    else
    {
        if (newTreeElem->Data.Number < y->Data.Number)
        {
            y->Left = newTreeElem;
        }
        else
        {
            y->Right = newTreeElem;
        }
    }

}

int BaumAusgabe(struct AddressTreeElement * root)
{
    if (!root) return 0;

    BaumAusgabe(root->Left);
    printf("key von X: %d\n", root->Data.Number);
    BaumAusgabe(root->Right);

    return 1;

}

struct AddressTreeElement * searchKey(struct AddressTreeElement * root, struct Address key)
{
    if (root == NULL || root->Data.Number == key.Number)
    {
        //printf("Gefunden oder NULL\n");
        return root;
    }

    if (key.Number < root->Data.Number)
    {
        return searchKey(root->Left, key);
    }
    else
    {
        return searchKey(root->Right, key);
    }
}

void deleteTreeNode(struct AddressTreeRoot * root, struct AddressTreeElement * elemToDel)
{
    struct AddressTreeElement * tmp = NULL;
    struct AddressTreeElement * merk = NULL;
    if (elemToDel->Left == NULL || elemToDel->Right == NULL)
    {
        //Hat keine Kinder
        tmp = elemToDel;
    }
    else
    {
        //Hat Kinder, suche nächstes Kind
        tmp = sucheNextChild(elemToDel);
    }

    if (tmp->Left != NULL)
    {
        //Wenn das Linke Kind nicht NULL ist merke mir dieses da
        //es einen neuen Vater bekommt
        merk = tmp->Left;
    }
    else
    {
        //sonst merke mir das rechte Kind
        merk = tmp->Right;
    }

    if (merk != NULL)
    {
        //Wenn merk nicht NULL ist dann ist der neue Vater von merk der Vater von tmp
        merk->Superior = tmp->Superior;
    }

    if (tmp->Superior == NULL)
    {
        //Wenn die Wurzel von tmp NULL ist dann ist merk der Wurzelknoten
        root->Root = merk;
    }
    else if (tmp == tmp->Superior->Left)
    {
        //Wenn tmp's Vater gleichzeitig sein linkes Kind ist dann ist merk das neue
        tmp->Superior->Left = merk;
    }
    else
    {
        //ansonsten ist merk das neue rechte Kind
        tmp->Superior->Right = merk;
    }

    //tmp wurde jetzt aus dem Baum "entfernt"

    if (tmp != elemToDel)
    {
        //elemToDel bekommt die Daten von tmp
        elemToDel->Data = tmp->Data;
    }

    //tmp freigeben
    free(tmp);

}

struct AddressTreeElement * sucheNextChild(struct AddressTreeElement * element)
{
    struct AddressTreeElement * tmp = NULL;
    if (element->Right != NULL)
    {
        //Wenn es ein rechtes Kind gibt dann ist das kleinste Element aus dem rechtem
        //Teilbaum das nächste Kind
        return sucheMinimum(element->Right);
    }

    //Ansonsten liegt es links
    tmp = element->Superior;

    while (tmp != NULL && element == tmp->Right)
    {
        element = tmp;
        tmp = tmp->Superior;
    }

    return tmp;
}

struct AddressTreeElement * sucheMinimum(struct AddressTreeElement * element)
{
    while (element->Left != NULL)
    {
        //Suche solange wie das linke Kind noch Nachfolger hat
        element = element->Left;
    }
    return element;
}

Es läuft...

Aber auch hier mal wieder die Frage ob ich nicht irgendetwas vergessen habe??
(Also speziel jetzt auf C bezogen)

Die Algorithmen ansich müssten eigentlich stimmen da wir sowas schon mal in der Uni besprochen hatten. Allerdings mehr pseudomäßig und nie wirklich implementiert haben in irgendeiner Sprache. Ist jetzt noch mal eine gute Übung für mich^^

gruß stampuhh

[Xin]

Ich gucke mir den Code dann endlich mal an.... ^^

Mit fällt auf, dass Du bei newAddressTree den Member 'Elements' nicht initialisierst.

Wenn Deine Variablen innerhalb eine Funktion temp und merk heißen... dann ist das suboptimal. Gib den Dingern verständliche Namen.
Dazu kommen Kommentare wie "//Wenn die Wurzel von tmp NULL ist dann ist merk der Wurzelknoten". Da ich nur durch Refactoring den Code für mich lesbar machen kann, weil ich mit tempen kann, was merk ist, ist der Code von deleteTreeNode für mich nicht nachvollziehbar und damit - wärest Du einer meiner Schüler - wäre der Code falsch.
Ich bin mir nicht sicher, ob er in allen Wegen richtig verläuft, dafür müsste ich ihn eben nachvollziehen können => refactoren.
Bei der Funktion sucheNextChild könnte es nicht schaden, sich auf Deutsch oder Englisch zu einigen - gilt auch für 'merk' - man merkt, ich bevorzuge Englisch. ^^

Was ich ganz witzig finde ist, dass Du mal iterativ (insertTreeNode) und mal rekursiv (searchKey) arbeitest.

[AnGaiNoR]

Ich sehe aber, das du jedem Knoten im Baum, das selbe Baumelemnt zuweist(addy), da du immer nur die Referenz auf das selbe Objekt festlegst, und dann etwas veränderst, müsste Theoretisch jedes Datenfeld eines jeden Baumknoten den Wert 4 haben, was evt zu Komplikationen bei deinem Suchalgorithmus führen könnte.

Theoretisch sollte es das nicht, denn meines Wissens nach wird die Struktur addy in diesem Fall "by value" übergeben und das Element wird immer neu kopiert und eingesetzt. Ich persönlich würde die Initialisierung des Data-Members ein bisschen anders machen, vielleicht sogar nur einen Zeiger an die newTreeElement-Funktion geben und den Speicher kopieren.

[stampuhh]

Ich gucke mir den Code dann endlich mal an.... ^^

Mit fällt auf, dass Du bei newAddressTree den Member 'Elements' nicht initialisierst.

Richtig...lässt sich aber sicherlich schnell einbauen. Ist ja sicherlich als Variable für die Anzahl der Knoten gedacht?

Wenn Deine Variablen innerhalb eine Funktion temp und merk heißen... dann ist das suboptimal. Gib den Dingern verständliche Namen.
Dazu kommen Kommentare wie "//Wenn die Wurzel von tmp NULL ist dann ist merk der Wurzelknoten". Da ich nur durch Refactoring den Code für mich lesbar machen kann, weil ich mit tempen kann, was merk ist, ist der Code von deleteTreeNode für mich nicht nachvollziehbar und damit - wärest Du einer meiner Schüler - wäre der Code falsch.

hehe ja...die Kommentare waren mehr oder weniger nur für mich gedacht damit ich das nachvollziehen kann was da geschieht. Ich die Methoden etwas überarbeitet aber ich muss sagen, dass es schwer ist sinnvolle Namen für Variablen zu finden, die mehr oder weniger nur temporär vorhanden sind und außer "merken" keine Funktion haben

Code: Alles auswählen

void deleteTreeNode(struct AddressTreeRoot * root, struct AddressTreeElement * element)
{
    struct AddressTreeElement * elemToDel = NULL;
    struct AddressTreeElement * tmpElement = NULL;

    if (element->Left == NULL || element->Right == NULL)
    {
        elemToDel = element;
    }
    else
    {
        elemToDel = searchNextChild(element);
    }

    if (elemToDel->Left != NULL)
    {
        tmpElement = elemToDel->Left;
    }
    else
    {
        tmpElement = elemToDel->Right;
    }

    if (tmpElement != NULL)
    {
        tmpElement->Superior = elemToDel->Superior;
    }

    if (elemToDel->Superior == NULL)
    {
        root->Root = tmpElement;
    }
    else if (elemToDel == elemToDel->Superior->Left)
    {
        elemToDel->Superior->Left = tmpElement;
    }
    else
    {
        elemToDel->Superior->Right = tmpElement;
    }

    //elemToDel wurde jetzt aus dem Baum "entfernt"

    if (elemToDel != element)
    {
        element->Data = elemToDel->Data;
    }

    free(elemToDel);

}

struct AddressTreeElement * searchNextChild(struct AddressTreeElement * element)
{
    struct AddressTreeElement * nextChild = NULL;
    if (element->Right != NULL)
    {
        //Wenn es ein rechtes Kind gibt dann ist das kleinste Element aus dem rechtem
        //Teilbaum das nächste Kind
        return searchMinimum(element->Right);
    }

    //Ansonsten liegt es links
    nextChild = element->Superior;

    while (nextChild != NULL && element == nextChild->Right)
    {
        element = nextChild;
        nextChild = nextChild->Superior;
    }

    return nextChild;
}

struct AddressTreeElement * searchMinimum(struct AddressTreeElement * element)
{
    while (element->Left != NULL)
    {
        //Suche solange wie das linke Kind noch Nachfolger hat
        element = element->Left;
    }
    return element;
}

Also beim Löschen geschieht grob gesagt folgendes. Es gibt drei verschiedene Fälle die man beachten muss.

Der erste Fall welche auch bei mir überprüft wird ob das Element, welches gelöscht werden soll, keine Kinder hat. Dann ist die Lösung ja recht einfach. Nämlich direkt Löschen.
Dann gibt es noch die Fälle, dass es ein oder zwei Kinder hat. Bei einem Kind muss das Kind (bzw. der "Kindzweig") an den Vater von meinem zu löschendem Element gehangen werden.
Der schwierigste Fall ist, wenn mein Element zwei Kinder hat, da es sich ja um einen Binären Suchbaum handelt. Da wird der Nachfolger von meinem Element gesucht und dieser aus dem Baum "entfernt" bzw. später an der Stelle von meinem zu löschendem Element eingefügt. Genauer gesagt, ich lösche den Nachfolger (free(elemToDel)) und übergebe die Daten von diesem an mein Element.

Ich bin mir nicht sicher, ob er in allen Wegen richtig verläuft, dafür müsste ich ihn eben nachvollziehen können => refactoren.
Bei der Funktion sucheNextChild könnte es nicht schaden, sich auf Deutsch oder Englisch zu einigen - gilt auch für 'merk' - man merkt, ich bevorzuge Englisch. ^^

ist mir noch gar nicht aufgefallen dass ich Denglisch verwende

Was ich ganz witzig finde ist, dass Du mal iterativ (insertTreeNode) und mal rekursiv (searchKey) arbeitest.

Wie oben schon geschrieben. So "abwechslungsreich" haben wir das in der Uni gelernt
Vermutlich damit überall die Laufzeit von O(h) eingehalten wird (h = Höhe des Baumes).

Theoretisch sollte es das nicht, denn meines Wissens nach wird die Struktur addy in diesem Fall "by value" übergeben und das Element wird immer neu kopiert und eingesetzt. Ich persönlich würde die Initialisierung des Data-Members ein bisschen anders machen, vielleicht sogar nur einen Zeiger an die newTreeElement-Funktion geben und den Speicher kopieren.

Muss ich mal rum probieren ob ich verstanden habe, was du da vorschlägst

gruß stampuhh

[AnGaiNoR]

Code: Alles auswählen

element = newTreeElement(tree, addy);

An der Stelle schiebst du die ganze Struktur addy in die Funktion rüber (was bei einer so minimalen Struktur kein Problem ist).
Wenn du anstelle von "call by value" einfach nur einen Zeiger übergibst, also "call by reference", dann musst du nur die Adresse übergeben (die in diesem Fall aber genauso groß ist wie die Struktur selbst).

Code: Alles auswählen

// Funktion zum Erstellen neuer Elemente
struct AddressTreeElement * newTreeElement(struct AddressTreeRoot * root, struct Address * dataPtr)
{
    // ... "Zuweisung", vorher prüfen ob dataPtr existiert!
    if ( dataPtr != NULL )
        memcpy( &newNode->Data, dataPtr, sizeof(struct Address) );
}

// ... irgendwo, wo ein Element erzeugt werden soll
struct Address addy;
addy.Number = 1337;
struct AddressTreeElement *element = newTreeElement( root, &addy );

Im Übrigen brauchst du den durch newTreeElement erzeugten Zeiger nicht unbedingt der Variable element zuweisen, vor allem wenn du sie in der übernächsten Zeile neu belegst.

[stampuhh]

ah ok^^

Danke. Jetzt hab ich das verstanden. Werde das sobald ich Zeit habe mal austesten. Muss grade noch nen Xubuntu, nen XP und nen Vista neu aufsetzen

gruß stampuhh