[ponchosi]

#include <iostream>
#include <fstream>
using namespace std;
#include <stdlib.h>
#include <time.h>
#include <math.h>

typedef int kn_info ;

struct knoten
 {
   kn_info info;
   knoten * lnachf, * rnachf;
};

struct baum {
    knoten *wurzel;
    int anzknoten;
};


void baumaus(ofstream & ,baum );
void initialize(baum &);
unsigned long long int anz(int);
void aufbau(ofstream &,knoten *&,baum,int &, int,int);
void knot(ofstream &, const knoten *, int);

int main (){
    int n,m;
    baum b;

    initialize(b);
    ofstream datout;
    char datnameout[20];

    cout<<"Bitte geben Sie die Anzahl der Knoten ein ! \n";
    cin>>n;
    m = n;
    cout<<"Die Anzahl aller möglichen Strukturen ist gleich "<<anz(n)<<"\n";

    do{
         cout << "Namen fuer die Ausgabedatei eingeben: ";

         cin >> datnameout;

         datout.open(datnameout);

         if (datout.fail())

             cerr << "Datei \"" << datnameout
             << "\" kann nicht geoeffnet werden!! \n";
      } while (datout.fail());

      aufbau(datout,b.wurzel,b,b.anzknoten,n,m);



}

unsigned long long int anz(int n){
    

    if ((n == 0) || ( n == 1)) return 1;


    else {

        unsigned long long  int r=0;

        for (int i = 0;i < n;i++){
        
            r = r + anz(i) * anz((n-1-i));
    }

     return r;
    }
}


void aufbau(ofstream &datout,knoten *(&p),baum b,int &a,int n,int m){



   if (a == m) {
        baumaus(datout,b);
        p=NULL;
        a = a - 1 ;
        datout<<"\n\n";
       

    }

    if(n>0) {
        p = new knoten;
        p->lnachf = p->rnachf = NULL;
        p->info = n;
        a++;
        if(b.wurzel == NULL) b.wurzel = p;
    }

    else p = NULL;

    for (int i = 0; i <n; i ++){
        aufbau(datout,p->rnachf,b,a,i,m);
        aufbau(datout,p->lnachf,b,a,(n-1-i),m);
        
    }



    

}


void initialize(baum &b)
//   ==========                                 //
// Initialisiere den Baum "vb" ordnungsgemaess. //
{ b.wurzel = NULL;
  b.anzknoten = 0;
 } // <--- Ende initialize


void baumaus(ofstream & datout, const baum b)
//   =======                                   //
// Ausgabe des Baumes "vb" in seiner Struktur. //
{ knot(datout,b.wurzel,0);
 } // <--- Ende baumaus //


void knot(ofstream & datout, const knoten * p, int t)
//   ====                                           //
// Ausgabe des Baumes, Hilfsroutine fuer "baumaus". //
{ int i;
  if (p != NULL)
   { knot(datout,p->rnachf,t+1);
     for (i=1; i <= t; i++) datout << "   ";
     datout << p->info << "\n";
     knot(datout,p->lnachf,t+1);
    }
  
 } // <--- Ende knot