4. binäre Bäume (programmieren in C)

binäre Bäume (programmieren in C)

  • ?

    Danke erstmal für euer Hilfe Leute, ich versuchs mal das umzusetzen.
    melde mich wieder wenn ich auf Probleme stösse

    0
  • ?

    Mir ist noch ein Problem aufgefallen, nämlich wo packe ich preorder, postorder und inorder hin?
    Und wenn ichs dann habe soll ich eine if-Abfrage benutzen womit der Benutzer wählen kann, welche Art zu suchen er haben möchte oder habt ihr eine bessere Idee?

    0
  • ?

    Mir ist noch ein Problem aufgefallen, nämlich wo packe ich preorder, postorder und inorder hin?

    am besten in ne eigene function 😉 ,nein spaß beiseite mach doch erst mal nen sauberen baum bevor du anfängst darin rum zu turnen...

    wikipedia schrieb:

    preorder(node)
    print node.value
    if node.left ≠ null then preorder(node.left)
    if node.right ≠ null then preorder(node.right)
    inorder(node)
    if node.left ≠ null then inorder(node.left)
    print node.value
    if node.right ≠ null then inorder(node.right)
    postorder(node)
    if node.left ≠ null then postorder(node.left)
    if node.right ≠ null then postorder(node.right)
    print node.value

    btw. hab bisher nur ein oder zwei mal ne iterative variante gesehen und die war dann nicht ohne, könnt natürlich auch sein das ich wie so oft falsch lieg

    lg lolo

    0
  • ?

    hab den link vergessen...
    http://en.wikipedia.org/wiki/Tree_traversal

    0
  • N

    binibini schrieb:

    Mir ist noch ein Problem aufgefallen, nämlich wo packe ich preorder, postorder und inorder hin?
    Und wenn ichs dann habe soll ich eine if-Abfrage benutzen womit der Benutzer wählen kann, welche Art zu suchen er haben möchte oder habt ihr eine bessere Idee?

    Preorder, Postorder und Inorder haben mit Suchen garnichts zu tun. Das ist nur die Reihenfolge in der die Elemente ausgegeben werden wenn der Baum ausgegeben wird.
    Wahrscheinlich willst du eine neue Option "Baum ausgeben" mit 3 Unteroptionen für die verschiedenen Ausgabereihenfolgen.
    Entweder mache dir 3 Funktionen void BaumAusgebenPreorder(struct binaer_baum *), BaumAusgebenPostorder usw. oder packe alles in eine Funktion:

    enum Ausgabemodus {Preorder, Postorder, Inorder};
void BaumAusgeben(struct binaer_baum *bb, Ausgabemodus m){
    switch (m){
    case Preorder: ...
    case Postorder: ...
    ...
}

int main(){
    ...
    BaumAusgeben(re, Inorder);
    ...
}
    0
  • F

    Edit...

    0
  • ?

    Sry das ich soviel Text poste, aber ich denk dass ist nötig um das Problem erkennen zu können. Und zwar habe ich eine Funktion um den Baum preorder auszugeben. Jedoch funktioniert diese noch nicht. Hat einer von euch eine Idee waoran es liegt? Die gemeinte Funktion heißt PrintTree.

    /* 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;
}
    0
  • ?

    versteh mich nicht falsch aber das kann nicht gehen, langsam frag ich mich wieso das bei euch geht und mir immer das system zerhaut... du holst dir mit malloc speicher für nen zeiger brauchst aber speicher für ne structur... hab das auch schon mal geschrieben, die zeilen die ich meine sind

    struct binaer_baum *baum =malloc(sizeof(struct binaer_baum));
statt
struct binaer_baum *baum =malloc(sizeof *baum);

und 

knoten = malloc(sizeof(struct binaer_knoten));
statt
knoten = *neu =malloc(sizeof *knoten);

    😞 😞

    0
  • ?

    So hab hier mal nur ein Teil reinkopiert und zwar gehts einmal um die iterative(binaere_suche_zahl) und die rekursive(suchen) Suche. Hab beide getestet, aber der rekursive Weg funktioniert nich. Glaube es liegt an den Strukturen bin mir aber nicht sicher. Habt ihr eine Idee?

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

struct binaer_baum{
   struct binear_knoten *wurzel;
   unsigned int counter;
};

/*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.      */
/*   }
}*/

void suchen(struct binaer_knoten *bn, unsigned int i){ 
    if (!bn){ //rekursionsabbruch: keine blätter mehr da die man durchsuchen kann 
        printf("Zahl nicht gefunden"); 
        return; 
    } 
    if (bn->ZAHL==i){ //rekursionsabbruch: zahl gefunden 
        printf("gefunden"); 
        return; 
    } 
    else{ //rekursiv weitersuchen 
        if (bn->ZAHL>i) suchen(bn->rechts, i); 
        else suchen(bn->links, i); 
    } 
}

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);
          suchen(re, p);
          /*binaere_suche_Zahl(re, p);*/
       }
       /*else if(wahl==3){
            printtree*/
    } while(wahl != 4);

   return 1;
}
    0
  • ?

    BAU DEINEN BAUM SAUBER UND TURN DANN....

    0
  • ?

    noobLolo schrieb:

    BAU DEINEN BAUM SAUBER UND TURN DANN....

    sry das war ein bischen wild...

    in dem link den ich dir geschickt hab in den du evtl. reingeschaut hast steht das so...

    /*
 Given a binary tree, return true if a node
 with the target data is found in the tree. Recurs
 down the tree, chooses the left or right
 branch by comparing the target to each node.
*/
static int lookup(struct node* node, int target) {
  // 1. Base case == empty tree
  // in that case, the target is not found so return false
  if (node == NULL) {
    return (false);
  }
  else {
    // 2. see if found here
    if (target == node->data) return(true);
    else {
      // 3. otherwise recur down the correct subtree
      if (target < node->data) return(lookup(node->left, target));
      else return(lookup(node->right, target));
    }
  }
}

    und für dich schaut das dann so ungefähr aus

    /*
 Given a binary tree, return true if a node
 with the target data is found in the tree. Recurs
 down the tree, chooses the left or right
 branch by comparing the target to each node.
*/
struct node *lookup(struct node* bn, int i){
  if(bn == NULL)
    return NULL;
  else if(i == bn->ZAHL)
    return bn;
  else{
    if(i < bn->ZAHL)
      return lookup(bn->links, i);
    else
      return lookup(bn->rechts, i);
  }
}

    und verwendet wirds

    int main(void){
  struct binaer_baum root;
  struct binaer_knoten a;
  struct binaer_knoten b;
  struct binaer_knoten c;
  root.wurzel = &a;
  a.ZAHL = 5;
  b.ZAHL = 2;
  c.ZAHL = 7;
  a.links = &b;
  a.rechts = &c;
  b.links = NULL;
  c.links = NULL;
  b.rechts = NULL;
  c.rechts = NULL;

  if(lookup(root.wurzel,5)==NULL)
    printf("oO nix gefunden");
  else
    printf("jipee hab was");
}

    axo und

    void suchen(struct binaer_knoten *bn, int i){
statt
void suchen(struct binaer_knoten *bn, unsigned int i){

    und

    struct binaer_knoten *knoten, **neu;
statt
struct binaer_knoten *knoten, *neu;

und dann
neu = baum->wurzel;
und
knoten= baum->wurzel;

und
neu = knoten->rechts; 
statt
neu = &knoten->rechts; 

und
neu = knoten->links; 
statt
neu = &knoten->links;

    sonst sollte suchen schon mehr oder weniger passen... also bau mal das bäumchen sauber

    0
  • ?

    arr

    struct binaer_knoten *lookup(struct binaer_knoten* bn, int i){ 
statt
struct node *lookup(struct node* bn, int i){
    0
  • ?

    so schauts bischen besser aus

    if(bn == NULL)
  return NULL;
else{
  if(i < bn->ZAHL)
    return lookup(bn->links, i);
  else
    if(i == bn->ZAHL)
      return bn;
    else
      return lookup(bn->rechts, i);
}
    0
  • ?
     

    if(bn == NULL)
  return NULL;
else{
  if(i < bn->ZAHL)
    return lookup(bn->links, i);
  else
    if(i > bn->ZAHL)
      return lookup(bn->rechts, i);
    else
      return bn;
}

    so jetzt reichts aber 😃

    0
  • ?

    machs doch gleich so 😉

    if(bn == NULL)
  return NULL;
else if(i < bn->ZAHL)
  return lookup(bn->links, i);
else if(i > bn->ZAHL)
  return lookup(bn->rechts, i);
else
  return bn;
    0
  • ?

    Danke für die Hilfe.
    Übrigens lolo der Baum is ja wohl recht ordentlich! Manman!

    BAU DEINEN BAUM SAUBER UND TURN DANN....

    0
  • ?

    hallo, ich habe die vorbeiträge gelesen. Auch ich arbeite an einer ähnlichen Aufgabe.
    Deshalb die frage: Ich habe preorder eingebaut, aber ich bekomme nichts ausgegeben. hier der coder baumausgabefunktion

    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);
    0
  • ?

    Das problem ist das mit der ausgabe in main() funktion...

    0
  • ?

    Hier wird anschneind nicht geholfen....

    0
  • ?

    Zeig doch den gesamten Code. So viel sollte es nicht sein.

    0
Anmelden zum Antworten