Binärer Baum

cHillb3rT

Hat hier einer von euch eine Quellcodevorlage, die er mal darüber geschrieben hat, damit ich mir mal die Funktionsweise anschauen kann.

Sie sind ja den verketteten Listen sehr ähnlich, nur dass du sie halt nicht linear aufbaust... Ich hab zwar gerade keinen Code zur Hand, aber ich würde es nach dem Muster aufbauen, dass du eine Struktur knoten definierst, in welcher du einen Pointer auf das Element links und rechts davon deklarierst. Der eigentliche Baum wäre dann sozusagen der Grundknoten... Also auch ein Zeiger auf knoten

Falls das zu unverständlich sein sollte:

struct Knoten
{
	...
	Knoten* links;
	Knoten* rechts;
};

struct Baum
{
	Knoten* wurzel;
}

Wobei ich meine Hand dafür nicht ins Feuer lege

curry-king

http://www.hard-code.de/content/cprogs/bin_tree.txt

feigling

http://feigling.php-4.info/xIRC_p10/dict.c
http://feigling.php-4.info/xIRC_p10/dict.h

wobei der Binary Tree (noch) keine Funktion hat, um die Anzahl der Knoten rechts und links in Waage zu halten, also immer wieder zu schauen, ob es nicht besser wäre wenn ein anderer Knoten root wäre bzw links statt rechts und umgekehrt stände. An das habe ich mich noch ned getraut

cHillb3rT

@ Feigling:
Bei mir gibts da Fehler, weil er die Bibiliotheksdateien nicht erkennt. (Unable to open include 'common.h')
Daher kann ich nicht genau sehen, ob dein Programm geht, ansonsten sieht es schon mal sehr gut aus.

@ Bashor:
Haste gleich mal Werbung für deine eigene Seite gemacht ne *g*

feigling

cHillb3rT schrieb:

@ Feigling:
Bei mir gibts da Fehler, weil er die Bibiliotheksdateien nicht erkennt. (Unable to open include 'common.h')
Daher kann ich nicht genau sehen, ob dein Programm geht, ansonsten sieht es schon mal sehr gut aus.

Ist klar, dass er die nicht kennt ^_
Du musst einfach anstatt der common.h malloc.h & stdio.h einbinden, vielleicht auch noch ein paar andere. Da bin ich mir jetzt ned sicher. Austesten

Die common.h macht einfach nur folgendes:

#include <arpa/inet.h>
#include <ctype.h>
#include <malloc.h>
#include <stdarg.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

Wobei du davon vielleicht 2 bis 3 brauchen solltest.

Geht aber einfacher als Array.
Heap als binärer Baum: http://www.fh-merseburg.de/~roesch/mirror/x/stud/zips/pr27.zip

Bye, TGGC (Pipe my World.)

cHillb3rT

@ Feigling:
Damit gehts schon mal besser.... aber komisch, dass mein Compiler, das nicht gleich richtig so umgesetzt hat, wie deiner, aber liegt wahrscheinlich daran, dass wir verschiedene benutzen.

@ Bash0R:
Deine Lösung von deiner Page mit den zufällig erzeugten Zahlen per "srand" passt auch sehr gut und ich setze jetzt einfach mal diese Lösung um für den Fall, dass man eine Eingabe hat.

cHillb3rT

Ich bekomme andauernd Speicheradressenfehler von dem Code hier:

#include <stdio.h>
#include <string.h>
#include <malloc.h>
#include <stdlib.h>
#include <conio.h>

typedef struct Knoten
{
  char *word;
  int count;
  struct Knoten* Eltern;
  struct Knoten* links;
  struct Knoten* rechts;
}Knotendaten;

struct Baum
{
  struct Knoten* wurzel;
}Baumdaten;

Knotendaten *anfang;

// Funktionen
int Knoteneinbauen(char *s);
Knotendaten *Knotenerschaffen(void);

Knotendaten *Knotenerschaffen(void)
{
  Knotendaten *knoten = malloc(sizeof(struct Knoten));

  /* Startwerte festlegen */
  knoten->word = NULL;
  knoten->Eltern = NULL;
  knoten->links = NULL;
  knoten->rechts = NULL;

  return knoten;
}

int Knoteneinbauen(char *s)
{
  struct Knoten *knoten,
                *derzeitiger,
                *letzter;
  int richtung = 0;
  int vergleich = 0;

  /* Kein Speicherplatz vorhanden */
  if( (knoten = Knotenerschaffen()) == NULL)
  {
    printf("Wir haben keinen Speicherplatz mehr vorhanden ! :(\n");
    exit(1);
  }

  /* Speicher für den String allokieren */
  knoten->word = malloc(sizeof(*s));
  strcpy(knoten->word,s);

  /* Hat der Bau,m schon eine Wurzel */
  if (anfang == NULL)
  {
    anfang = knoten;
  }
  else
  {
    // Hangel dich durch den Baum
    derzeitiger = anfang;
  }

  while (derzeitiger != NULL)
  {
    // Merke dir den letzten Ast
    letzter = derzeitiger;

    // Vergleiche die Strings - 
    vergleich = strcmp(knoten->word,derzeitiger->word);

    //Wenn der einzuführende String kleiner ist
    //dann gehts links entlang
    if (vergleich < 0)
    {
      richtung = 0;
      derzeitiger = derzeitiger->links;
    }
    else if (vergleich > 0)
    {
      richtung = 1;
      derzeitiger = derzeitiger->rechts;
    }
    else //der String existiert schon im Baum
    {
      printf("Diesen String gibt es schon im binaeren Baum. Bitte geben sie etwas anderes ein !", s);
      return 1;
    }
  }
  // Vater des einzufügenden Knotens setzen
  knoten->Eltern = letzter;

  // Ist der Knoten links oder rechts vom Vater
  if (richtung == 0)
  {
    letzter->links = knoten;
  }
  else
  {
    letzter->rechts = knoten;
  }
  return 0;
}

int main(int argc, char* argv[])
{
  int i;
  char eingabe[10]; /* Problem hierbei ist anscheinend, dass er
  ohne den Zeiger nicht richtig das Programm durchlaufen kann. Das
  versteh ich noch nicht so ganz. */
  //char *eingabe = (char *)malloc(sizeof(char));

  printf("--- Binaere Baumstruktur ---\n");
  printf("Bitte geben sie einen Satz ein: \n");

  scanf("%s", eingabe);
  Knoteneinbauen(eingabe);
  printf("Knoten %s wurde erstellt", eingabe);

  getch();
  return 0;
}
//---------------------------------------------------------------------------

Sieht jemand von euch den Fehler ?

Bashar

cHillb3rT schrieb:

/* Hat der Bau,m schon eine Wurzel */
  if (anfang == NULL)
  {
    anfang = knoten;
  }
  else
  {
    // Hangel dich durch den Baum
    derzeitiger = anfang;
  }

  while (derzeitiger != NULL)
  {
    // Merke dir den letzten Ast
    letzter = derzeitiger;

Hier kann irgendwas nicht stimmen, derzeitiger ist uninitialisiert, wenn anfang==NULL ist. Denk den Algorithmus bitte nochmal durch.

cHillb3rT

ach ich sehe es..... "derzeitiger" muss noch einen Wert bekommen, damit beim Vergleich überhaupt noch ein Ergebnis raus kommt. Dadurch entsteht der Fehler !

cHillb3rT

So ich hab auch noch ein paar andere Programme zu binären Bäumen mal geschrieben:

Vielleicht hilft das einigen Leuten ja weiter !!

// Alexander Gilbert
// 15.02.2005
// Binärer Baum

// Includes
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>

/* Die Zeiger auf die Struktur selbst, dienen zur Orientierung wegen links und rechts */
struct knoten
{
  int wert;
  struct knoten *links;
  struct knoten *rechts;
};
typedef struct knoten KNOTEN;

void zeige_baum(KNOTEN *zeiger);

/* Globale Variable: kann man auch in jeder Funktion und im Haupt-
programm extra definieren */
int zahl;

KNOTEN *einordnen(KNOTEN *zeiger)
{
  /* Wenn der Zeiger noch keine Speicheradresse hat, also nirgends hinzeigt,
  dann, wird erstmal Speicher allokiert. */
  if(zeiger == NULL)
  {
    /* Zeiger allokiert knotenweise Speicher. Dies bedeutet im Klartext,
    dass durch (KNOTEN *) der Zeiger drei Werte hat. Beispiel bei Eingabe
    von der Zahl 1 (1, NULL, NULL). */
    zeiger=(KNOTEN *)malloc(sizeof(KNOTEN));
    if(zeiger == NULL)
    {
      printf("Konnte keinen Speicherplatz "
                      "reservieren!!!\n");
      exit (0);
    }
    /* Der Wert der Zahl, die man eingegeben hat, wird an die Struktur weitergegeben. Rechts
    wird dem wird ein leere Speicheradresse zugeordnet und auf der linken Seite wird der Zeiger
    als Speicheradressenhalter benutzt. */
    zeiger->wert=zahl;
    zeiger->links=zeiger->rechts=NULL;
  }
  /* Wenn die "zahl" kleiner ist als der Wert auf den der Zeiger zeigt, dann ordnet man
  die Zahl auf die linke Seite ein. Wenn die "zahl" größer ist, dann ordnet man sie in die
  rechte Seite ein. */
  else if(zeiger->wert >= zahl)
  {
    zeiger->links=einordnen(zeiger->links);
  }
  else if(zeiger->wert < zahl)
  {
    zeiger->rechts=einordnen(zeiger->rechts);
  }
  return (zeiger); /* Der Zeiger wird zurückgegeben mit der Speicheradrese */
}

int main()
{
   KNOTEN *wurzel=NULL; /* am Anfang hat man noch keine Wurzel und
   braucht auch daher keine Speicheradresse in diesem Fall. Aus diesem
   Grund vergibt man auch den Begriff NULL an *wurzel. */

   printf("*** Dieses Programm zeigt ihnen die Funktionsweise eines binaeren Baumes ***\n");

   do
   {
     printf("Bitte Zahl eingeben : ");
     scanf("%d",&zahl);
     wurzel = einordnen(wurzel);
   }
   while(zahl != 0);
   getch();
   zeige_baum(wurzel); /* man startet von der Wurzel ab durch den Baum */
   getch();
   return 0;
}

/* Baumstruktur zeigen */
void zeige_baum(KNOTEN *zeiger)
{
  /* Wenn der Zeiger eine Speicheradresse hat, dann kann erst ausgeführt
  werden. Dabei verwendet man Rekursion, damit die Funktion immer wieder aufge-
  rufen werden kann, um auch die Werte, die auf dem linken und rechten Ast
  liegen auszugeben.  */
  if(zeiger != NULL)
  {
    printf("\n%d->",zeiger->wert);
    zeige_baum(zeiger->links); // Rekursion
    zeige_baum(zeiger->rechts); // Rekursion
  }
}