Baum kopieren

O

Ozzy Ozborn

Erfahrenes Mitglied
Hi,

ich habe das Problem, dass ich gerade an einem Projekt sitze, wo ich mit Binärbäumen arbeite, in die ich aussagenlogische Formeln einfügen soll. Um am Ende die Belegung dieser Formel auszuwerten, wollte ich eine Kopie von dem Baum anlegen, und auf dem weiterarbeiten. Und genau da ist jetzt auch mein Problem.


Hier meine Baum.cpp: (alles nur die emtsprechenden Auszüge)

Baum::Baum()
: left(NULL),
right(NULL),
key() {
return;
};

Baum::Baum(const Baum &baum)
: left(baum.left ? baum.left->clone() : NULL),
right(baum.right ? baum.right->clone() : NULL),
key(baum.key) {
return;
};

Baum *Baum::clone() const {
return new Baum(*this);
};

void Baum::inorder(Baum *root)
{
if (root == NULL)
return ;
inorder(root->left); // linken Baum traversieren
cout << root->key << " "; // Schluessel ausgeben
inorder(root->right); // rechten Baum traversieren
}
​

und die Baum.h:

Baum *clone() const;

private: Baum *left, *right;
string key;

};
​


Und die Main.cpp:

Baum baum;
Read read;

// Anfang Modul 1
string f = read.einlesen();
Baum *tree = new Baum();

if (f!="") {
baum.insert(tree,f);
cout << endl << endl;
cout << "Baumstruktur (inorder)" << endl;
baum.inorder(tree); cout << endl << endl;
// Ende Modul 1
// Anfang Modul 2

Baum *tree = baum.clone();

baum.belegung();
baum.aufruf(tree);

baum.inorder(tree2);

}
​


Also, mein Problem ist nun, dass er den tree2 genauso verändert, wie den tree, obwohl die clone-Funktion vor der Veränderung aufgerufen wird.
Hat jemand dazu eine Idee?

Vielen Dank schon einmal für Euer Kopfzerbrechen,
MfG, Ozzy
 
Hallo,

ich denke das liegt daran das deine clone Methode keine deep copy erzeugt.
Alles unterhalb deiner Wurzel da werden einfach nur die Zeiger kopiert.
D.h. machst du Aenderungen am gecloneden Baum so uebertragen sich die Aenderungen nat. auch auf
den Original Baum da die internen Zeiger auf die selben Kindknoten zeigen...

Besser ist denke ich so:

C++: 
#include <iostream>

using namespace std;

class Tree{
    private:
        Tree* left;
        Tree* right;
        int element;

    public:

        Tree(int element) : element(element){}

        Tree* clone(){
            Tree* copy = new Tree(element);
            if(left != NULL)
                copy->left = left->clone();
            if(right != NULL)
                copy->right = right->clone();
            return copy;
        }

        ~Tree(){
            if(right != NULL)
                delete right;
            if(left != NULL)
                delete left;
        }
};


Gruß

RedWing
 
Hallo,

bspw so (in main wird clone aufgerufen):

Code: 
#include <iostream>

using namespace std;

class Tree{
	private:
		Tree* left;
		Tree* right;
		int element;
		
	public:
		
		Tree(int element) : element(element), left(NULL), right(NULL){}
		
		Tree* clone(){
			Tree* copy = new Tree(element);
			if(left != NULL)
				copy->left = left->clone();
			if(right != NULL)
				copy->right = right->clone();
			return copy;
		}
		
		void add(int elem){
			if(elem < element){
				if(left != NULL)
					left->add(elem);
				else
					left = new Tree(elem);
			}
			else{
				if(right != NULL)
					right->add(elem);
				else
					right = new Tree(elem);
			}
		}
		
		//ein Element suchen und veraendern (wenn gefunden)
		void changeElem(int search, int toChange){
			if(search == element)
				element = toChange;
			if(left != NULL)
				left->changeElem(search, toChange);
			if(right != NULL)
				right->changeElem(search, toChange);
		}	
		
		//Baum in inorder ausgeben
		friend ostream& operator<<(ostream& cout, Tree* toPrint){
			if(toPrint->left != NULL)
				cout << toPrint->left;
			cout << toPrint->element << " ";
			if(toPrint->right != NULL)
				cout << toPrint->right;
			return cout;
		}
		
		//Speicher wieder freigeben
		~Tree(){
			if(right != NULL)
				delete right;
			if(left != NULL)
				delete left;	
		}
};

int main(){
	Tree* t1 = new Tree(10);
	t1->add(5);
	t1->add(12);
	t1->add(4);
	Tree* t2 = t1->clone(); //hier wird geclont
	cout << "t2: " << t2 << endl;
	t2->changeElem(12, 7);	//hier wird das element 12 zu 7 in t2 veraendert
	cout << "t1: " << t1 << endl;
	cout << "t2: " << t2 << endl;
	delete t1;
	delete t2;
}

Habs versucht ein wenig zu kommentieren, falls du noch fragen haben solltest nur zu ;)

Gruß

RedWing
 
Hi,

also bei mir gibt er nichts aus... Ich versuche das einfach noch mal zu rekapitulieren, vielleicht findest Du ja dann den Fehler:

Die Baum.h:
Code: 
class Baum 
{    
public:
             Baum(string key) : key(key){}
             
             Baum* clone(){            
                   cout << "test";
                   Baum* copy = new Baum(key);            
                   if(left != NULL)                
                   copy->left = left->clone();            
                   if(right != NULL)                
                   copy->right = right->clone();            
                   return copy;        }
             
private:  Baum *left, *right;
          string key;

};

Und die Main.cpp:
Code: 
int main()
{
    Baum baum;
    Read read;

    // Anfang Modul 1
    string f = read.einlesen();
    Baum *tree = new Baum();

    if (f!="") {
       baum.insert(tree,f);
       cout << "Baumstruktur (inorder)" << endl;
       baum.inorder(tree); cout << endl << endl;
       // Ende Modul 1
       // Anfang Modul 2
       Baum* tree2 = tree->clone(); 

       baum.belegung();
       baum.aufruf(tree);
       cout << "Baum2" << endl;
       baum.inorder(tree2);

    }
    system("PAUSE");
    return EXIT_SUCCESS;

Nach Baum2 kommt aber gähnende Leere. Hab noch mal ein cout in die clone eingebaut, und die ruft er auch freundlichst auf, und gibt auch die keys schön aus.
Und was mir auch aufgefallen ist, ist, dass er das Fenster auf einmal sofort nach dem Ende der Ausführung schließt, und das PAUSE völlig vernachlässigt...

So, hoffe, Du kannst mir helfen, und siehst den Fehler, schon einmal vielen Dank für Deine Hilfe,

MfG, Ozzy
 
Hallo,

leider kann ich nur raten:

Deine 2 Teilbäume werden nirgends initialisiert:

Versuch es mal mit dem Konstruktor:
Code: 
class Baum 
{    
public:
             Baum(string key) : key(key), left(NULL), right(NULL){}
             ...
private:  Baum *left, *right;
          string key;

};

Gruß

RedWing
 
Hi,

hab das jetzt probiert, jetzt sagt er mir aber:
14 C:\Programme\Dev-Cpp\Projektaufgabe\Main.cpp no matching function for call to `Baum::Baum()'
und zeigt auf die Zeile
Baum *tree = new Baum();

Hast Du da noch eine Idee?

MfG, Ozzy
 
Hallo,

hab das jetzt probiert, jetzt sagt er mir aber:
14 C:\Programme\Dev-Cpp\Projektaufgabe\Main.cpp no matching function for call to `Baum::Baum()'
und zeigt auf die Zeile
Baum *tree = new Baum();

Hast Du da noch eine Idee?
Zum Vergrößern anklicken....

Du musst nat. den Konstruktoraufruf so gestalten wie du deinen Konstruktor
definiert, hast. Also:
Code: 
Baum *tree = new Baum("Hallo");

Wenn du nicht weiterkommen solltest dann poste doch mal deinen kompletten
Baum...

Gruß

RedWing
 
Hi,

also momentan scheitert es erst einmal daran, dass ich irgendwie die Funktionen aus der Baum.cpp nicht mehr aus der Main.cpp aufrufen kann. Also dieses
Code: 
Baum baum;
funktioniert jetzt nicht mehr, und so kennt er auch meine Funktionen in der Klasse Baum nicht mehr.
Hier einmal die komplette Main.cpp:
Code: 
#include <iostream>
#include "Main.h"
#include "Read.h"

using namespace std;

int main()
{
    //Baum baum;
    Read read;

    // Anfang Modul 1
    string f = read.einlesen();
    Baum *tree = new Baum("");

    if (f!="") {
       tree.insert(tree,f);

       cout << "Baumstruktur (inorder)" << endl;
       baum.inorder(tree); cout << endl << endl;

       Baum* tree2 = tree->clone(); //
       baum.praedikate(tree);     
       baum.praed_ausgeben();
       baum.belegung();
       baum.aufruf(tree);
       baum.modell(tree);
       //baum.inorder(tree); cout << endl << endl;
       //cout << "Baum2" << endl;
       //baum.inorder(tree2);

    }
    else { cout << "Formel falsch eingegeben, keine weitere bearbeitung moeglich" << endl; }

    system("PAUSE");
    return EXIT_SUCCESS;  
}

Und Auszüge der Baum.h:
Code: 
class Baum 
{    
public:
             Baum(string key) : key(key), left(NULL), right(NULL){}
             void inorder(Baum *root);
             string insert(Baum *&root, string f);

             Baum* clone(){            
                   cout << key;
                   Baum* copy = new Baum(key);            
                   if(left != NULL)                
                   copy->left = left->clone();            
                   if(right != NULL)                
                   copy->right = right->clone();            
                   return copy;        }
             
private:  Baum *left, *right;
          string key;

};

Und noch einmal das wichtigste der Baum.cpp:
Code: 
Baum::Baum()
  : left(NULL),
    right(NULL),
    key() {
            return;
};

void Baum::inorder(Baum *root)
{
    if (root == NULL)
        return ;
    inorder(root->left);                                        // linken Baum traversieren
    cout << root->key << " ";                                   // Schluessel ausgeben
    inorder(root->right);                                       // rechten Baum traversieren
}

string Baum::insert(Baum *&root, string f) {                    // fügt die Formen in den Baum ein

     int j=0;
     int k=0;
     bool leer=true;
     string ausdruck;
     cout << endl << "Element gelesen: " << f[s] << endl;       // Gibt das gelesene Element aus
     if (root == 0) {                                           // wenn Wurzel leer neuen Baum anfügen
        root = new Baum;
        root->left = root->right = 0;
        root->key = "";                                         // Schreibt erst einmal nichts in die Wurzel
        cout << "Wurzel erstellt" << endl;                      // Rückmeldung: Wurzel erstellt
        
     }
          
     if (f[s]==40) {                                            // Wenn eine öffnende Klammer gefunden wurde
        s++;
        
        if (root->left==NULL) {                                 // Wenn der linke Sohn NULL ist
           cout << "nach links" << endl;                        
           insert(root->left, f);                               // dann mache die Rekursion links
        }
        else {
             cout << "nach rechts (" << endl;
             insert(root->right, f);                            // ansonsten rechts
        }
     }
     else if ( (f[s]!=38)&&(f[s]!=43)&&(f[s]!=62) ) {           // solange kein Zeichen wie &,*,>
             j=s;
             if (f[s]==33) {                                    // Wenn das Zeichen ein !
                ausdruck="";                                    // ist der Ausdruck leer
                leer=false;
                s--;
             }
             
             while ( (f[j]!=38)&&(f[j]!=43)&&(f[j]!=62)&&(f[j]!=41)&&(f[j]!=33) ) {
                   ausdruck = ausdruck + f[j];                  // solange kein Verknüpfungszeichen kommt
                   k++;                                         // verlängere den Ausdruck
                   j++;
             }
             if (ausdruck!="") {
                root->key = ausdruck;                           // und füge ihn im Knoten ein
             }
             cout << "Zeichen " << ausdruck << " wird eingefuegt" << endl;
             if (leer==false) {
                s=s+k+1;
             }
             else {
                  s=s+k;                                      // weiterspringen in der Formel um die entspr. Zeichen
             }
     }
          
     
     if ((root->key=="")&&(leer==true)) {                       // wenn im Knoten nichts steht
        cout << "fuege in leeren Knoten ein" << endl;
        while (f[s]==41) {                                      // Keine ")"
              s++;
              }
        root->key=f[s];                                         // Füge Verknüpfungszeichen aus der Formel ein
        cout << "Verknuepfung " << f[s] << " wird eingefuegt" << endl;
        s++;
        cout << "nach rechts" << endl;
        insert(root->right, f);                                 // rekursiv rechts entlang
     }
     cout << endl << "REKURSION" << endl << endl;
     return f;
}

Ansonsten habe ich alles auch noch mal hochgeladen:
http://www.Chiaroscuro.de/Projektaufgabe.rar

Vielen Dank noch einmal für Deine Hilfe,
Ozzy
 
Hi,

also kurzzeitig klappte es, jetzt aber nicht mehr, obwohl ich nichts verändert habe...
Nun liegt sein Problem in der Baum.cpp bei:
Code: 
Baum::Baum()
  : left(NULL),
    right(NULL),
    key() {
            return;
};
wo er mir sagt:
18 C:\Programme\Dev-Cpp\Projektaufgabe\Baum.cpp prototype for `Baum::Baum()' does not match any in class `Baum'

Hast Du dafür noch eine Idee

MfG, Ozzy
 
Zuletzt bearbeitet:
Um antworten zu können musst du eingeloggt sein.

Neue Beiträge

Zurück