Vollständig Binärer Baum (Klasse)
-
Hallo,
Wir sollen eine Klasse schreiben für VbB.
Folgende Struktur ist vorgegeben:class knoten
{ f r iend c l a s s VabBaum;
public :
. // Konstruktoren
. // Destruktor
.
pr ivate :
knoteninfo info ;
knoten * lnachf , * rnachf ;
} ;
Vollständig ausgeglichene binäre Bäume:
Die Grundstruktur der Klasse
class VabBaum
{ publ ic :
. // Konstruktoren
. // Destruktor
. // Elementfunktionen, ueberladene Operatoren
.
private :
knoten * wurzel ; // Zeiger auf die Wurzel
unsigned anz ; // Anzahl der Knoten des Baumes
} ;Nun bin ich eigentlich schon recht weit, das einzige, dass noch probleme bereitet, ist der CopyKonstruktor und der Destruktor !
Ich komme hier einfach nicht weiter und bin schon am verzweifeln -.-
vllt seht ihr das problem :#include "stdafx.h" #include <iostream> #include <fstream> using namespace std; using namespace System; typedef int knoteninfo; int log2(int n); int sqr(int n); int pot2(int n); class knoten{ friend class vabbaum; friend void aufbauvoll(knoten *(&) , int n); friend void knot(const knoten * p, int t); friend ostream & operator<<(ostream &ostr,const knoten &b); friend void anhaengen(knoten * (& wurzel), int n,const knoteninfo inf); friend knoten * suchen(knoten *p,const knoteninfo inf); friend bool loeschen(const vabbaum &b,const knoteninfo inf); friend knoten * letztknot(knoten * wurzel, int n); public : knoten(){ lnachf=NULL; rnachf=NULL; info = 0; } knoten(knoteninfo inf){ lnachf=NULL; rnachf=NULL; info = inf ; } ~knoten(){ lnachf=NULL; rnachf=NULL; info = 0; } private : knoteninfo info ; knoten * lnachf , * rnachf ; } ; ostream & operator<<(ostream &ostr,const knoten &b){ ostr<<"Knoteninfo : "<</*b.info<<*/endl; return ostr; } class vabbaum { friend void baumaus(const vabbaum vb); friend bool isempty(const vabbaum &M); friend ostream& operator <<( ostream&,const vabbaum &) ; friend istream& operator >>( istream&, vabbaum &) ; friend void insert(vabbaum & vb, const knoteninfo inf); friend bool loeschen(const vabbaum &b,const knoteninfo inf); friend knoten * lastnode(vabbaum vb); public : vabbaum(): wurzel(NULL) , anz(0) {}; vabbaum(unsigned int n){ aufbauvoll(wurzel,n); anz = n; } vabbaum(const vabbaum &b){ if(b.anz == 0) { wurzel = 0; anz=0; } else{ anz = b.anz; wurzel = new knoten(b.wurzel->info); kopieren(wurzel->rnachf,b.wurzel->rnachf); kopieren(wurzel->lnachf,b.wurzel->lnachf); } } vabbaum operator+(const knoteninfo inf){ vabbaum z(*this); insert(z,inf); return z; } vabbaum operator+=(const knoteninfo inf){ insert(*this,inf); return *this; } vabbaum operator-(const knoteninfo inf){ vabbaum z(*this); loeschen (z,inf); return z; } vabbaum operator -=(const knoteninfo inf){ if(loeschen(*this,inf)) anz--; return *this; } void operator--(){ if(anz != 0){ knot(wurzel->lnachf,0); cout<<endl<<endl<<endl; } } void operator++(){ if(anz != 0){ knot(wurzel->rnachf,0); cout<<endl<<endl<<endl; } } // //~vabbaum(){ // destroy(wurzel); //} private : knoten * wurzel ; // Zeiger auf die Wurzel unsigned anz ; // Anzahl der Knoten des Baumes static void kopieren(knoten *a,const knoten *b){ while(b != NULL) { a = new knoten(b->info); kopieren(a->rnachf,b->rnachf); kopieren(a->lnachf,b->lnachf); } } //static void destroy(knoten *node){ // // if(node){ // destroy(node->lnachf); // destroy(node->rnachf); // delete node; // } //} h } ; ostream & operator<<(ostream &ostr,const vabbaum &b){ ostr<<"Anzahl der Knoten : "<<b.anz<<endl; ostr<<"Ausgabe des Baumes "<<endl; if(!isempty(b)) ostr<<"Baum ist leer"<<endl; ostr<<endl<<endl<<endl; baumaus(b); ostr<<endl<<endl<<endl; return ostr; } istream& operator >>( istream& istr, vabbaum &b) { unsigned int n; cout<<"Bitte Knotenanzahl eingeben "<<endl<<endl; cin>>n; if(n>0){ cout<<"Bitte Knoteninfos eingeben "<<endl; aufbauvoll(b.wurzel,n); } b.anz = n; return istr; } int main(array<System::String ^> ^args) { int n; vabbaum x,z; cin>>x; /* vabbaum y(x); cout<<y; y-=10; cout<<y;*/ cout<<x; --x; ++x; cin>>n; return 0; } bool isempty(const vabbaum &B){ return B.anz; } void baumaus(const vabbaum vb) // ======= // // Ausgabe des Baumes "vb" in seiner Struktur. // { knot(vb.wurzel,0); } // <--- Ende baumaus // void knot(const knoten * p, int t) // ==== // // Ausgabe des Baumes, Hilfsroutine fuer "baumaus". // { int i; if (p != NULL) { knot(p->rnachf,t+1); for (i=1; i <= t; i++) cerr << " "; cerr << p->info << "\n"; knot(p->lnachf,t+1); } } // <--- Ende knot void aufbauvoll(knoten * (& p), int n) // ========== // // n - Anzahl der Knoten // // Baut die Struktur eines vollstaendigen // // Baumes aus n Knoten auf // { knoteninfo u; if(n!=0){ cin>>u; } if (n > 3) { p = new knoten; p->lnachf = p->rnachf = NULL; p->info = u; int k = log2(n+1), nst = pot2(k)-1, rest = n - nst; if (rest==0) { n = (n-1)/2; aufbauvoll(p->lnachf,n); aufbauvoll(p->rnachf,n); } else if (rest <= ((nst+1)/2)) { int nr = (nst-1)/2, nl = nr + rest; aufbauvoll(p->lnachf,nl); aufbauvoll(p->rnachf,nr); } else {//nl = (nst-1)/2 + (nst+1)/2 = nst, nr = rest-1// aufbauvoll(p->lnachf,nst); aufbauvoll(p->rnachf,rest-1); } } else if (n==3) { p = new knoten; p->info = u; p->lnachf = new knoten; p->lnachf->lnachf = p->lnachf->rnachf = NULL; cin>>u; p->lnachf->info = u; p->rnachf = new knoten; p->rnachf->lnachf = p->rnachf->rnachf = NULL; cin>>u; p->rnachf->info = u; } else if (n==2) { p = new knoten; p->info = u; p->lnachf = new knoten; p->lnachf->lnachf = p->lnachf->rnachf = NULL; cin>>u; p->lnachf->info = u; p->rnachf = NULL; } else if (n==1) { p = new knoten; p->info = u; p->lnachf = p->rnachf = NULL; } else if (n==0) { p = NULL; } } // <--- Ende aufbauvoll // int log2(int n) // ==== // // ganzzahliger Zweierlogarithmus von n // // °($(n\geqslant 1),\quad k = \lfloor\log_2(n)\rfloor$)° // { if (n == 1) return 0; else return (log2(n/2) + 1); } // <--- Ende log2 // int sqr(int n) // === // // Quadrat einer natuerlichen Zahl // { return n*n; } // <--- Ende sqr // int pot2(int n) // ==== // // Zweierpotenz von n: °($2^n,\quad (n \geqslant 0)$)° // // "schnelles Potenzieren", binaer // { if (n == 0) return 1; else if (n%2) return sqr(pot2(n/2))*2; else return sqr(pot2(n/2)); } // <--- Ende pot2 // void insert(vabbaum & vb, const knoteninfo inf) // ====== // // Mit Hilfe von "anhaengen" wird ein neuer Knoten // // mit Info "inf" in den Baum "vb" eingefuegt. // { anhaengen(vb.wurzel,vb.anz,inf); vb.anz++; } // <--- Ende insert // void anhaengen(knoten * (& wurzel), int n, const knoteninfo inf) // ========= // // In einen vollstaendigen Baum wird der letzte // // Knoten so ergaenzt, dass der Baum vollstaendig // // mit HEAP-Eigenschaft bleibt. // { int nst, rest, k; if (n>2) { k = log2(n+1); nst = pot2(k)-1; rest = n - nst; if (rest==0) { n = (n-1)/2; anhaengen(wurzel->lnachf,n,inf); } else if ((rest+1)<=((nst+1)/2)) { n = (nst-1)/2 + rest; anhaengen(wurzel->lnachf,n,inf); } else //=n-(nst+1)=(nst-1)/2+rest-pot2(k-1);// { n = rest - 1; anhaengen(wurzel->rnachf,n,inf); } } else if (n==2) { wurzel->rnachf = new knoten; wurzel->rnachf->lnachf = NULL; wurzel->rnachf->rnachf = NULL; } else if (n==1) { wurzel->lnachf = new knoten; wurzel->lnachf->lnachf = NULL; wurzel->lnachf->rnachf = NULL; } else // n==0 ! { wurzel = new knoten; wurzel->info = inf; wurzel->lnachf = wurzel->rnachf = NULL; } } // <--- Ende anhaengen // bool loeschen(const vabbaum &b,const knoteninfo inf){ knoten *p,*m; p = suchen(b.wurzel,inf); if(p != NULL) { m = lastnode(b); p->info = m->info; delete m; return true; } return false; } knoten * suchen(knoten *p,const knoteninfo inf){ while(p != NULL){ if(p->info = inf) return p; else{ suchen(p->rnachf,inf); suchen(p->lnachf,inf); } } return NULL; } knoten * lastnode(vabbaum vb) // ======== // // Suche letzten Knoten in einem vollstaendigen // // Baum "vb". // // Funktion stuetzt sich auf "letztknot" --> Rekursion!// { return letztknot(vb.wurzel,vb.anz); } // <--- Ende lastnode // knoten * letztknot(knoten * wurzel, int n) // ========= // // Suche letzten Knoten in einem vollstaendigen Baum // // mit n Knoten. // { int nst, k, rest; if (n>1) // °($k = \lfloor\log_2(n+1)\rfloor,\quad n'=2^k-1,\quad r=n-n'$)° { k = log2(n+1); nst = pot2(k)-1; rest = n - nst; if (rest==0) { n = (n-1)/2; return letztknot(wurzel->rnachf,n); } else if (rest <= ((nst+1)/2)) { n = (nst-1)/2 + rest; return letztknot(wurzel->lnachf,n); } else //n=n-(nst+1)=(nst-1)/2+rest-pot2(k-1)// { n = rest - 1; return letztknot(wurzel->rnachf,n); } } else if (n==1) return wurzel; else return NULL; } // <--- Ende letztknotDie Kommentare im Code sind nicht immer aktuell !
Die relevanten Sachen wäre hier :
Aufbau des Baumes,
Konstruktor,
DestruktorDa ich vieles auf den Konstruktor aufbauen möchte, is der Kram für den weiteren Verlauf sehr wichtig.
Der Standardkonstruktor von Visual Studios kopiert leider komplett alles und raus kommt quasi einfach nur eine Referenz auf den Ausgangsbaum !
Dies bringt mir aber nicht viel, da der Ursprungsbaum nicht verändert werden soll, wenn ich den kopierten verändere, sprich, die müssen beide eigenständig sein und nicht die gleichen Speicherplätze beschreiben.Habt vielen Dank
-
Hast du zu 450 Zeilen Code auch etwas konkreteres als Frage zu liefern als "Hilfe, ich komme nicht weiter!"? So wird sich das niemand durchlesen.
-
Hallo,
wie schon geschrieben, es geht nur um den Kopier und Destruktor !
Alles andere, das nicht mit diesen beiden Funktionen zusammenhängt, läuft soweit !
Habe nur den ganzen Code gepostet, weil ich nicht genau weiß, wo der Fehler liegt ! Afaik kann es aber nur am Konstruktor, Destruktor oder am Aufbau liegen !
-
Poste nur den zur Problemlösung relevanten Code und stelle eine konkrete Frage. "Es geht um den CopyCtor ist KEINE klare Frage".
Niemand wird sich 450 Zeilen Code durchlesen.Dein Code ist übrigens extrem grenzwertig. Wieso benutzt du freie Funktionen und nicht Methoden? Da kannst du auch gleich in C programmieren...
Und vor Satzzeichen macht man übrigens keine Leerzeichen;)
