PraktikumProgrammierung1:Aufgabe 6
Aus Tudwiki
binbaum.c:[Bearbeiten]
/* binbaum.c */
#include <stdio.h> #include <stdlib.h> #include <ctype.h> #include "baumfunktionen.h"
char Menueauswahl() {
char a;
printf("\nBitte auswaehlen: \n");
printf("\ni => Informationen anzeigen");
printf("\nk => Weiteren Knoten anfuegen");
printf("\ne => Knoten einer Ebene anzeigen");
printf("\nx => Programmende\n");
printf("\nBitte auswaehlen: ");
do { a = toupper(getchar());
} while ((a != 'I')&&(a != 'K')&&(a != 'E')&&(a != 'X'));
return a;
}
int main()
{
node tree = NULL; int z; char ch;
printf("\n Baum eingeben: \n");
printf(" Eingabe <=0 : Eingabeende\n");
printf(" Eingabe >0 : Knoten anfuegen\n\n");
do
{ printf(" Key: ");
scanf("%i", &z);
if (z > 0) /* Knoten anfuegen */
TreeInsert(&tree,z);
} while (z>0); /* sonst Eingabeende */
do
{ ch = Menueauswahl();
switch (ch)
{ case 'I': Info(tree); break;
case 'K': printf(" Key (>0) : ");
scanf(" %i", &z);
if (z > 0) TreeInsert(&tree,z);
else printf("unzulaessiger Wert\n");
break;
case 'E': printf(" welche Ebene : ");
scanf(" %i", &z);
if (z > Hoehe(tree))
printf("\nSo hoch ist der Baum nicht!\n");
else
{ printf("\nIn der %d. Ebene liegen die Knoten: \n\n",z);
Ebene(tree,z,1);
printf("\n\n");
}
break;
} /* end of switch */
} while (ch != 'X');
printf(" Programmende !\n ");
return 0;
}
baumfunktionen.h:[Bearbeiten]
/* baumfunktionen.h */
#ifndef BAUMFUNC_H
#define BAUMFUNC_H #include <stdlib.h>
typedef struct ele *node;
void TreeInsert(node *t, int n);
int Anzahl(node t);
int Blaetter(node t);
int Hoehe(node t);
void Info(node t);
void Ebene(node t, int e, int h);
#endif
baumfunktionen.c:[Bearbeiten]
/* baumfunktionen.c */
#include <stdio.h> #include <stdlib.h> #include "baumfunktionen.h"
typedef struct ele {
int key;
node left, right;
} tree_ele ;
void TreeInsert(node *t, int n)
{
/* Die Funktion 'TreeInsert' erzeugt einen neuen Knoten, weist
ihm den Schluesselwert n zu und fuegt ihn geordnet in
den Binaerbaum *t ein (kann auch leer sein!) */
if(*t==NULL)
{
*t=(node)malloc(sizeof(tree_ele));
(*t)->key=n;
(*t)->left=NULL;
(*t)->right=NULL;
}
else /* gleiche Schluessel werden nicht doppelt eingefuegt */
if((*t)->key>n)
TreeInsert(&(*t)->left,n);
else
if ((*t)->key<n)
TreeInsert(&(*t)->right,n);
}
int Anzahl(node t)
{
/* Die Funktion 'Anzahl' ermittelt die Anzahl der Knoten des
Binaerbaumes t */
if(t==NULL)
return 0;
else return 1 + Anzahl(t->left) + Anzahl(t->right);
}
int Blaetter(node t)
{
/* Die Funktion 'Blaetter' ermittelt die Anzahl der
Blattknoten des Binaerbaumes t */
if(t==NULL)
return 0;
else
if(t->left==NULL && t->right==NULL)
return 1;
else return Blaetter(t->left) + Blaetter(t->right);
}
int Hoehe(node t)
{
/* Die Funktion 'Hoehe' ermittelt die maximale Pfadlaenge
des Binaerbaumes t */
int hl,hr;
if(t==NULL)
return 0;
else
{
hl = Hoehe(t->left);
hr = Hoehe(t->right);
if(hl>hr)
return 1+hl;
else
return 1+hr;
}
}
void Info(node t)
{
/* Die Funktion 'Info' gibt Informationen ueber den
Binaerbaum t auf dem Bildschirm aus */
printf("\nDer Baum hat %d Knoten ( %d davon sind Blaetter) \
und eine Hoehe von %d\n\n", Anzahl(t), Blaetter(t), Hoehe(t));
}
void Ebene(node t, int e, int h)
{
/* Die Funktion 'Ebene' (rekursiv) soll die Schluesselwerte aller
Knoten auf dem Bildschirm ausgeben, die in der Ebene e liegen ( h ist dabei die aktuelle Ebene des rekursiven Aufrufs, der Wurzelknoten bildet die Ebene 1 ). */
/* Implementierung ist auf verschiedene Arten (auch ohne Nutzung
* von "h" moeglich. */
if(t!=NULL)
{
if(e==h)
printf("%8d",t->key);
else
{
h++;
Ebene(t->left,e,h);
Ebene(t->right,e,h);
}
}
}
