PraktikumProgrammierung1:Aufgabe 6

binbaum.c:

/* 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:

/* 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:

/* 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);
               }
       }

}