binäre Bäume (programmieren in C)
-
meine Aufgabe lautet:
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 zumEinfü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.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. Das Code sieht so aus:
[code]
/* Programm zum Erstellen und Nutzen eines binaeren Baumes */
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX 255struct 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;
}
}int einfuegen(struct binaer_baum *baum, unsigned int p){
struct binaer_knoten *knoten, **neu;neu =(struct binaer_knoten **) &baum->wurzel;
knoten= (struct binaer_knotenbaum->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] 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);
}
} while(wahl != 3);
return 1;
}
-
Ich weiss nicht genau wie ich das ganze mit Preorder, Postorder, Inorder und iterativ machen soll.
laut Wikipedia :preOrder( knoten ):print( knoten )
if knoten.links ≠ null then
preOrder( knoten.links )if knoten.rechts ≠ null then
preOrder( knoten.rechts )inOrder( knoten ):
if knoten.links ≠ null then
inOrder( knoten.links )print( knoten )
if knoten.rechts ≠ null then
inOrder( knoten.rechts )postOrder( knoten ):
if knoten.links ≠ null then
postOrder( knoten.links )if knoten.rechts ≠ null then
postOrder( knoten.rechts )print( knoten
aber damit kann ich nicht wirklich viel anfangen
vielendank für euere Hilfe...
-
den Code noch einmal weil es beim letzten mal nicht so geklappt hat:
/* 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; } } 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] 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); } } while(wahl != 3); return 1; }
[cpp]
-
Du hast alles iterativ gemacht. Dir fehlt die rekursive Version.
Rekursiv geht ungefähr so:void suchen(struct binaer_knoten *bn, 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); } }
Außerdem solltest du bei deiner Zahl einheitlich bleiben, du würfelst signed und unsigned int durcheinander.
Mir ist unklar was du an dem Wikipediacode nicht verstehst. Den kannst du kopieren, statt print nimmst du printf, statt print(knoten) kommt printf("%d ", knoten->ZAHL) und noch ein paar geschweifte Klammern und Typfestlegungen und fertig.
Dir fehlt übrigens noch das Balancieren. Suchbäume sind eigentlich nur balanciert sinnvoll, sonst arten sie in eine Liste aus und du hast O(n) statt O(log(n)). Das ist nicht so ganz einfach, aber das steht auch bei wiki.
char o[MAX]; wird nirgendwo benutzt. Init könntest du vielleicht in createBinaryTree oder erzeugeBinaerbaum umbenennen.
Oder ganz weglassen wenn du eh nur einen einzigen hast:struct binaer_baum re = {NULL, 0}; //... r=einfuegen(&re, p); oder struct binaer_baum bb = {NULL, 0}, *re = &bb;
-
na also da sind schon noch paar mehr fehler drin...
z.b.
knoten = *neu =malloc(sizeof *knoten);
neu =(struct binaer_knoten **) &baum->wurzel;würd das nochmal gründlich überdenken hier findest ganz guten source code
http://cslibrary.stanford.edu/110/BinaryTrees.htmlaber heut ist silvester und mehr als das kann ich dir heut nicht anbieten...
wünsche euch allen einen guten rutsch ins neue jahr 2010
lg lolo
-
ouch mir ist gerade beim durchlesen aufgefallen dass es eine neue version ist die alte war noch in c und bedeutend besser wenn ich davon ne copie finde lad ichs hoch und post den link, scheint so als wär der unterschied zwischen c und c++ nicht nur new vs. malloc sondern 1* vs. 3-
-
Danke erstmal für euer Hilfe Leute, ich versuchs mal das umzusetzen.
melde mich wieder wenn ich auf Probleme stösse
-
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?
-
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.valuebtw. 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
-
hab den link vergessen...
http://en.wikipedia.org/wiki/Tree_traversal
-
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); ... }
-
Edit...
-
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; }
-
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);
-
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; }
-
BAU DEINEN BAUM SAUBER UND TURN DANN....
-
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
-
arr
struct binaer_knoten *lookup(struct binaer_knoten* bn, int i){ statt struct node *lookup(struct node* bn, int i){
-
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); }
-
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