Seite 1 von 2 12 LetzteLetzte
Ergebnis 1 bis 10 von 14

Thema: binäre Bäume (programmieren in C)

  1. #1
    binbaum
    Gast

    Beitrag binäre Bäume (programmieren in C)

    hallo Leute, Ich hoffe auf euere Hilfe
    meine Aufgabe lautet:
    [highlight] Implementieren Sie die nötigen Funktionen, um sortierte binäre Bäume verwenden zu können.Dafür ist zum einen die Datenstruktur zu deklarieren, und zum anderen sind Funktionen zum Einfügen von Knoten/Blättern und zur Ausgabe des Baumes erforderlich. Informieren Sie sich über die Möglichkeiten einen Suchbaum auszugeben und implementieren Sie Funktionen, dieden Baum in Preorder, Postorder und Inorder ausgeben.
    Implementieren Sie zusätzlich die in der Vorlesung vorgestellte Suche in Binärbäumen rekursiv
    und iterativ. Legen Sie zum Testen einen Baum an und fügen Sie 12 Werte hinzu. Nutzen Sie dann die Funktionen um nach einem Knoten
    zu suchen und den Baum auszugeben. [highlight]

    mein Problem ist mit REKURSIV und mit mit verschiednen ORDER klappt es nicht so gut.
    ich zähle auf euere Hilfe

    Ich habe nicht viel Ahnung von Programmieren, deshalb habe ich zwar angefangen aber das nicht noch nicht so toll aus.

    Das Programm kann nur zahlen speichern un wieder geben.
    mein code lautet foldendermassen:
    Code:
    * Programm zum Erstellen und Nutzen eines binaeren Baumes */
    #include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    #define MAX 255
    
    struct binaer_knoten{
       int ZAHL;
       struct binaer_knoten *links;
       struct binaer_knoten *rechts;
    };
    
    struct binaer_baum{
       struct binear_knoten *wurzel;
       unsigned int counter;
    };
    
    struct binaer_baum *init (void){
       struct binaer_baum *baum =malloc(sizeof *baum);
       if(baum == NULL) {
          fprintf(stderr, "Speicherplatzmangel!!!\n");
    
          return NULL;
       }
       else {                                                                       /*Initialisieren*/
          baum->wurzel = NULL;
          baum->counter=0;
          return baum;
       }
    }
    
    void PrintTree (struct binear_knoten * wurzel, int * einruecken)
    {
     int i;
     
     if (wurzel != NULL)             /* Ist der Baum leer? Nein, dann gib ihn aus */
     {
       
        for (i=0; i<=(*einruecken); i++)
            printf("     ");
       
        printf("%d\n",wurzel->ZAHL);    /* Preorder-Notation: W */
    
        (*einruecken)++;                    /* vorruecken */
    
        PrintTree(wurzel->links,einruecken);   /* Preorder-Notation: L */
        PrintTree(wurzel->rechts,einruecken);  /* Preorder-Notation: R */
    
        (*einruecken)--;                    /* zuruecksetzen */
    }
     return;
    };
    
    
    int einfuegen(struct binaer_baum *baum, unsigned int p){
       struct binaer_knoten *knoten, **neu;
    
       neu =(struct binaer_knoten **) &baum->wurzel;
       knoten= (struct binaer_knoten *) baum->wurzel;
       for(;;) {
          if(knoten == NULL) {
             /* Haben wir einen freien Platz gefunden? */
             knoten = *neu =malloc(sizeof *knoten);
             if(knoten != NULL) {
                /* Daten einfuegen */
                knoten->ZAHL = p;
                knoten->links=knoten->rechts=NULL;
                baum->counter++;
                /* Beendet die Funktion erfolgreich. */
                return 1;
             }
             else {
                fprintf(stderr, "Speicherplatzmangel\n");
                return 0;
             }
          }
          /* Ist die aktuelle Zahl groesser? */
          else if(p > knoten->ZAHL)  {
             /* Dann gehts rechts weiter im Baum. */
             neu = &knoten->rechts;
             knoten = knoten->rechts;
          }
          else { /* Der letzte Fall, die aktuelle ZAHL ist kleiner, */
             /* dann eben nach links weiter im Baum. */
             neu = &knoten->links;
             knoten = knoten->links;
          }
       }
    }
    
    void binaere_suche_Zahl(const struct binaer_baum *baum,
                           unsigned int p) {
       const struct binaer_knoten *knoten;
    
       knoten = (struct binaer_knoten *) baum->wurzel;
       for(;;) {
          if(knoten == NULL) {
             printf("Ihre gesuchte Zahl (%d) ist NICHT im binaeren Baum gefunden worden!\n",p);
             return;
          }
          if(p == knoten->ZAHL) {  /* Gefunden */
             printf("Ihre gesuchte Zahl (%d) ist im binaeren Baum enthalten!\n", p);
             return;
          }
          else if(p > knoten->ZAHL)   /* Gesuchtes Element groesser:  */
             knoten=knoten->rechts;  /* rechts am Baum weiter.     */
          else                       /* Gesuchtes Element kleiner: */
             knoten=knoten->links;   /* links am Baum weiter.      */
       }
    }
    
    
    int main(void) {
       struct binaer_baum *re;
       char o[MAX];
       unsigned int p;
       int wahl, r;
    
       re = init();
       if(re == NULL) {
          printf("Konnte keinen neuen binaeren Baum erzeugen!\n");
          return 0;
       }
       else
          printf("Binaerbaum wurde erfolgreich initialisiert\n");
    
       do {
          printf("\n[1] Neue Zahl hinzufuegen\n");
          printf("[2] Zahl suchen\n");
          printf("[3] Baum ausgeben\n");
          printf("[4] Ende\n\n");
          printf("Ihre Wahl : ");
          scanf("%d",&wahl);
    
          if(wahl == 1) {
             printf("Bitte geben Sie eine neue Zahl ein : ");
             do{ scanf("%5u",&p); }while( (getchar()) != '\n' );
             r=einfuegen(re,p );
             if(r == 0)
                return 0;
           }
           
           else if(wahl == 2) {
              printf("Welche Zahl suchen Sie: ");
              scanf("%5u",&p);
              binaere_suche_Zahl(re, p);
           }
           /*else if(wahl==3){
                printtree*/
        } while(wahl != 4);
       
       return 1;
    }
    Achtung: Dies ist ein alter Thread im HTML und Webmaster Forum
    Diese Diskussion ist älter als 90 Tage. Die darin enthaltenen Informationen sind möglicherweise nicht mehr aktuell. Erstelle bitte zu deiner Frage ein neues Thema im Forum !!!!!

  2. #2
    binbaum
    Gast

    Standard AW: binäre Bäume (programmieren in C)

    Gibt es niemand, der helfen kann....

  3. #3
    Forum Guru Avatar von The User
    Registriert seit
    28.10.2007
    Ort
    Zwischen Pazifik und Atlantik...
    Beiträge
    4.044
    Danke
    0
    Bekam 0 mal "Danke" in 0 Postings

    Standard AW: binäre Bäume (programmieren in C)

    Zur Ausgabe: Warum übergibst du einruecken als Pointer?
    Nimm doch einfach ein "unsigned int". Der Pointer bringt gar nichts außer Verlangsamung und mehr Code. Du brauchst mit einem einfachen "unsigned int" weder zu dekrementieren noch zu dereferenzieren. Als Standard-Wert kannst du für einruecken dann die 0 wählen und der Aufruf gestaltet sich einfacher.
    Und Inorder und Postorder, da musst du nur das printf verschieben.

    Zum Einfügen:
    Schreib Casts wenn möglich nicht hin. Bei dir wird z.B. gar nicht gecastet, auch wenn du es dahin schreibst. Die Schreibweise "for(;" ist anti-intuitiv, verwende lieber "while(1)".

    Rekursion:
    Einfügen:
    Wenn knoten == NULL: knoten := neuer wert
    Wenn knoten >= wert: Einfügen(knoten->links, wert)
    Sonst: Einfügen(knoten->rechts, wert)
    Suchen:
    Wenn knoten == NULL: Nicht gefunden
    Wenn knoten == wert: Knoten gefunden
    Wenn knoten >= wert: Suche(knoten->links, wert)
    Sonst: Such(knoten->rechts, wert)

    Die Frage ist noch, ob du Doppeleinträge zulassen möchtest.

    Was studierst du denn?

    Viele liebe Grüße
    The User

  4. #4
    binbaum
    Gast

    Daumen hoch binäre Bäume (programmieren in C)

    Danke für die Hilfe...
    Ich studiere Informatik an der TU Aachen, 7. Semester...

  5. #5
    binbaum
    Gast

    Lächeln AW: binäre Bäume (programmieren in C)

    möchte mich von den harten, ungerechten aussagen der vorposter distanziern... meilenweit
    bin der hilfe dankbar...
    kennt ihr noch ein weiteres gutes forum besonders für c++?

  6. #6
    der/die Göttliche Avatar von jojo87
    Registriert seit
    23.03.2007
    Ort
    Leipzig
    Alter
    30
    Beiträge
    3.131
    Danke
    0
    Bekam 0 mal "Danke" in 0 Postings

    Standard AW: binäre Bäume (programmieren in C)

    kennt ihr noch ein weiteres gutes forum besonders für c++?
    Wie wärs hiermit:
    http://www.c-plusplus.de/forum/

    PS: habe den Thread mal bereinigt

  7. #7
    Forum Guru Avatar von The User
    Registriert seit
    28.10.2007
    Ort
    Zwischen Pazifik und Atlantik...
    Beiträge
    4.044
    Danke
    0
    Bekam 0 mal "Danke" in 0 Postings

    Standard AW: binäre Bäume (programmieren in C)

    Darfst ruhig auch weiterhin hier mal was schreiben.
    Ich schau hier durchaus regelmäßig rein, kann aber sein, dass mal ein Abend an mir vorbei geht.

  8. #8
    binbaum
    Gast

    Standard AW: binäre Bäume (programmieren in C)

    Hallo,
    Ich habe preorder eingebaut, aber ich bekomme nichts ausgegeben. kann jemand mir bitte tipps geben...


    hier ist der code:

    struct binaer_knoten{
    int ZAHL;
    struct binaer_knoten *links;
    struct binaer_knoten *rechts;
    };

    void baum_ausgeben (struct binaer_knoten * wurzel)
    {
    int i;

    if (wurzel != NULL) /* Ist der Baum leer? Nein, dann gib ihn aus */
    {


    printf("%d\n",wurzel->ZAHL); /* Preorder-Notation: W */

    baum_ausgeben(wurzel->links); /* Preorder-Notation: L */
    baum_ausgeben(wurzel->rechts); /* Preorder-Notation: R */

    }
    return;
    };
    ......
    ......


    int main(void) {
    .....
    baum_ausgeben(re->wurzel);




    meine freage ist: wie muss ih das in main() funktion arbeiten

  9. #9
    Forum Guru Avatar von The User
    Registriert seit
    28.10.2007
    Ort
    Zwischen Pazifik und Atlantik...
    Beiträge
    4.044
    Danke
    0
    Bekam 0 mal "Danke" in 0 Postings

    Standard AW: binäre Bäume (programmieren in C)

    Nimm %i statt %d. (denn es ist ja ein Integer)
    Ansonsten fehlt noch die Einrückungstiefe. Entweder du übergibst die als int, oder aber du übergibst gleich eine Zeichenkette mit der gewünschten Anzahl an Leerzeichen. Im ersten Fall muss der Standardwert 0 sein (void baum_ausgeben (struct binaer_knoten * wurzel, int indent = 0)), im zweiten Fall "" (void baum_ausgeben (struct binaer_knoten * wurzel, const char * indent = ""). Im ersten Fall musst du nach dem printf inkrementieren, im zweiten Fall ein " " dranhängen (dafür gibt es eine Funktion in string.h).

    Grüße
    The User

    PS:
    Nach 17 Minuten brauchst du deinen Thread doch noch nicht zu pushen, dadurch wird der auch nicht besser sichtbar. Wenn du etwas editieren möchtest, registriere dich am besten, dann geht das.
    Geändert von The User (05.01.2010 um 19:57 Uhr)

  10. #10
    binbaum
    Gast

    Daumen hoch AW: binäre Bäume (programmieren in C)

    Vielen Dank!
    meine Funktion sieht jetzt folgendermaßen aus:

    void baum_preorder (struct binaer_knoten * wurzel, int *einruecken)
    {
    int i;

    if (wurzel != NULL) /* Ist der Baum leer? Nein, dann gib ihn aus */
    { for(i=0;i<=(*einruecken);i++)
    printf(" ");


    printf("%i\n",wurzel->ZAHL); /* Preorder-Notation: W */
    (*einruecken)++;
    baum_preorder(wurzel->links, einruecken); /* Preorder-Notation: L */

    baum_preorder(wurzel->rechts, einruecken); /* Preorder-Notation: R */
    (*einruecken)--;
    }
    return;
    };

    habs folgendermaßen in die main-Funktion eingebaut:

    int main(void) {
    struct binaer_baum *re;
    ...
    else if(wahl==4){
    baum_preorder(re,"");
    }

    Das Problem besteht darin, dass mir das Programm nur eine unsinnige ZAhl ausgibt. Woran könntge das liegen?

Ähnliche Themen

  1. Bot programmieren
    Von Hesoyam im Forum HTML & CSS Forum
    Antworten: 1
    Letzter Beitrag: 29.11.2008, 20:47
  2. Browsergame programmieren
    Von goldeneye im Forum PHP Forum - Apache - CGI - Perl - JavaScript und Co.
    Antworten: 14
    Letzter Beitrag: 14.07.2008, 02:58
  3. [C++] Binäre Datei downloaden
    Von lugga im Forum Forum für alle anderen Programmiersprachen
    Antworten: 3
    Letzter Beitrag: 05.11.2007, 11:46
  4. PHP-Forum programmieren
    Von Raknarok im Forum PHP Forum - Apache - CGI - Perl - JavaScript und Co.
    Antworten: 8
    Letzter Beitrag: 19.02.2007, 13:48
  5. programmieren mit einem mac
    Von ladyinred im Forum HTML & CSS Forum
    Antworten: 3
    Letzter Beitrag: 17.10.2006, 08:44

Stichworte

Berechtigungen

  • Neue Themen erstellen: Nein
  • Themen beantworten: Nein
  • Anhänge hochladen: Nein
  • Beiträge bearbeiten: Nein
  •