Suche Beispielcode zu 2d-Baum



  • Hallo!

    Ich bin mit Bäumen bzw. deren Strukturen noch nicht 100%ig vertraut und such daher ein Codebeispiel zu meiner Baumstruktur:

    #define node struct node
    #define point struct point
    
    point 
    {
        int  x, y, info;
    };
    
    node
    {
        point p;
        node *next, *l, *r; // l = linker, r = rechter Sohn
    };
    
    node *head // Wurzel
    point *p;
    

    Der Baum soll mit ein Paar Punkten (x- und y-Koordinaten) befüllt werden und dann durch die Funktion preorder() traversiert und die x- und y-Koordinaten ausgegeben werden.

    Ich wäre euch dafür sehr dankbar!

    mfg MrLINK



  • für sowas nimmt man normal einen r-tree



  • Kann man den Baum, wie ich ihn vorgebe, nicht preorder traversieren?

    mfg MrLINK



  • MrLINK schrieb:

    Kann man den Baum, wie ich ihn vorgebe, nicht preorder traversieren?

    sicher aber da fehlt doch noch das ganze drum herum...



  • Gut, dann werde ich mal ein wenig konkreter 😉

    Ich habe die Datenstruktur erstellt sowie (neben anderen Funktionen), die preorder-Funktion deklariert:

    point 
    {
        int  x, y, info;
    };
    
    int y = max_height, x = max_width;
    
    node
    {
        point p;
        node *next, *l, *r; // l = linker, r = rechter Sohn
    };
    
    void preorder(node *n); // preorder
    
    node *z, *head, *n; // head -> Wurzel
    point *p;
    

    (Habe den Baum im Programm initialisiert und Punkte eingelesen.)

    Dann wollte ich die preorder Funktion aufrufen, indem ich die Adresse von Head, also die Wurzel, der Funktion übergebe:

    preorder(head);
    

    Übergebe ich die Adresse, erscheint jedoch folgende Fehlermeldung:

    cannot convert `node' to `node*' for argument `1' to `void preorder(node*)'**

    Ich habe dann den Adressoperator weggelassen (was jedoch meines Erachtens falsch ist) und das Programm konnte kompiliert werden. Die Funktion preorder soll den Baum preorder traversieren und mir für jeden Knoten die x- und y-Koordinate ausgeben:

    void preorder(node *n)
    {  
        if(n)
        {
             printf("%i %i", n->p.x, n->p.y);
             //preorder (n->l);
             //preorder (n->r);
        }
    }
    

    Irgendwas stimmt ja offensichtlich nicht, denn wenn ich die beiden rekursiven Funktionsaufrufe einkommentieren, stürzt das Programm einfach ab.

    Ich bräuchte etwas Hilfe 😉

    mfg MrLINK



  • #include <stdio.h>
    #include <stdlib.h>
    //#include <graphics.h>
    #include <time.h>
    #define node struct node
    #define point struct point
    
    // Anzahl der Knoten
    const int max_notes = 100;
    // GUI-Fenster-Breite
    const int max_width = 300;
    // GUI-Fenster-Höhe
    const int max_height = 300;
    
    point 
    {
        int  x, y, info;
    };
    
    node
    {
        point p;
        node *next, *l, *r; // l = linker, r = rechter Sohn
    };
    
    node *z, *head, *n; // head -> Wurzel
    point *p;
    
    void input();
    void tree2Dinsert(point p);
    void preprocess(point p[], int anzahl);
    void preorder(node *n);
    
    int main()
    {   
        input();
        preorder(head);
        printf("\n\n\t\t");
        //system("PAUSE");
        return 0;
    }
    
    //------------------------------------------------------------------------------
    
    // erzeugt Punkte
    void input()
    {
        int note_number, i;
    
        point p_feld[max_notes];
    
        srand(time(0));
    
        printf("\t\tBaumprogramm\n\t\t============\n\n");
        printf("\t\tPunktanzahl (1-%i): ", max_notes);
        scanf("%i", &note_number);
        printf("\n\n");
    
        for(i = 1; i <= note_number; i++)
        {
             p_feld[i].x = rand() % (max_width +1);
             p_feld[i].y = rand() % (max_height +1);
    
             printf("\t\tBaum %i (x y):\t", i);
             printf("%i %i", p_feld[i].x, p_feld[i].y);
             printf("\n");
        }    
    
        preprocess(p_feld, note_number);
    }
    
    //------------------------------------------------------------------------------
    
    // initialisiert den Baum
    void preprocess(point p[], int anzahl) 
    {
        int i;
    
        p[0].x = 0; 
        p[0].y = 0; 
        p[0].info = 0;
    
        z = (node*)malloc(sizeof *z);
    
        z->l = z; 
        z->r = z; 
        z->p = p[0];
    
        head = (node*)malloc(sizeof head);
    
        head->r = z; 
    
        head->p = p[0];
    
        //initwindow(max_width, max_height);
    
        for (i = 1; i <= anzahl; i ++)
        { 
             tree2Dinsert(p[i]);
        }
    }
    
    //------------------------------------------------------------------------------
    
    // fügt die generierten Punkte in den Baum ein
    void tree2Dinsert(point p)
    {
        node *f, *t;
        int d, td, info;
    
        int time;
    
        for (d = 0, t = head; t != z; d != d) 
        {
             td = d ? (p.x < t->p.x) : (p.y < t->p.y);
    
             f = t; 
    
             t = td ? t->l : t->r;
        }
    
        t = (node*)malloc(sizeof *z);
    
        t->p = p; 
        t->l = z; 
        t->r = z;
    
        if (td) 
        {
             f->l = t; 
             printf("%i", t);
        }
        else 
        {
             f->r = t;
        }
    }
    
    //------------------------------------------------------------------------------
    
    void preorder(node *n)
    {   
        if(n)
        {
             printf("\n\t\t%i %i\n\n", n->p.x, n->p.x);
             preorder (n->l);  
             preorder (n->r);
        }
    }
    

    Könnt ihr mir vielleicht helfen? Die Funktion soll den Baum durchlaufen und dann die Koordinaten ausgeben (preorder()). Das Programm stürzt jedoch dauernd ab, aber wieso?

    Vielen Dank im Voraus!

    mfg MrLINK



  • ich glaub dir haben sie noch keine lokalen variablen beigebracht oder 🙄



  • Kannst du das etwas spezifizieren?

    mfg MrLINK



  • kennerDerNoobs schrieb:

    ich glaub dir haben sie noch keine lokalen variablen beigebracht oder 🙄



  • Deine Andeutung hilft mir aber nur bedingt weiter.. wenn du mir nicht helfen möchtest, dann lass es doch einfach.

    Gibt es hier vielleicht noch jemanden der helfen kann anstatt mit wichtigtuerischen Anspielungen um sich zu schmeißen?

    mfg MrLINK



  • machen wir einen deal einstein, du beantwortest meine frage und ich deine, ganz einfach oder 😕



  • Angebot abgelehnt. Ich habe freundlich um Hilfe gebeten und nicht um das Geschwätz eines arroganten Proleten - ganz einfach, oder? 😕

    MrLINK



  • soweit ich das beurteilen kann, haben die besucher dieses forums bis auf ausnahmen kein helfersyndrom. sie wollen unterhalten sich über neuigkeiten austauschen und gegenseitig ⚠ helfen... da du offensichtlich nicht gewillt bist anderen zu helfen brauchts auf meine hilfe auch nicht zählen. bin ja mal gespannt wer dir deine frage beantwortet...



  • Ich habe mir einige Threads durchgelesen und dort nirgends gesehen, dass wenn jemand eine Frage hatte, der Antwortende erst eine entsprechende Gegenleistung gefordert hat. Von welcher Hilfe sprichst du überhaupt? Glaubst du ernsthaft ich erhoffe mir was von dir? Eher steht Einstein morgen vor meiner Tür als dass du mir deine so teuere Hilfe anbietest. 🙄

    MrLINK



  • MrLINK schrieb:

    Glaubst du ernsthaft ich erhoffe mir was von dir?

    scheinbar indirekt sonst wärst nicht vom c++ ins ansi c unterforum gewechselt...


Anmelden zum Antworten