Binary Tree, kleines Prob in Standardconstruktor

[Graf-Porno]

Hi Leute, ich habe ein kleines Problem mit dem Standardkonsttruktor, ich bekomme ein komischen Fehler beim compilen, den ich leider nicht zuordnen kann.
außerdem wäre ich über jede Hilfe beim generellen erstellen meiner Klasse sehr dankbar! <- Problem gefunden und behoben.
Jedoch funktioniert das einfügen nicht wirklich, könnte jemand dieses Machwerk vielleicht korrigieren?
P.S in der Main steht mist!

// BaumKlasse.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <stdlib.h>
class tree {
	public:
	tree *rechts;
	tree *links;
	int Wert;
	void erstellen (tree *neu);
	tree (); 
	~tree();
	int setzen (int k);
};

tree::tree() {
rechts = NULL;
links = NULL;
Wert = 0;
}


int tree::setzen(int k) {
	rechts = NULL;
	links = NULL;
	Wert = k;
	return 0;
};


class Knoten  {
public:
	tree *root;
	int index;
	void erstellen (tree *neu);
	Knoten ();
	~Knoten ();
};

Knoten::Knoten() {
	root = NULL;
	index = 0;
};




void Knoten::erstellen(tree *neu) {
	if (root == NULL) {
		root= neu;
		root->links=NULL;
		root->rechts= NULL;
		index =1;
	}
	else {root->erstellen(neu);
	}
}

void tree::erstellen(tree *neu) {
	//if (root != NULL) {
		if ((neu = (tree *)malloc(sizeof (tree)))!=NULL);
		if (neu->Wert<Wert) {
			if (links == NULL) { 
				links = neu; }
			else {links->erstellen(neu);
			}
		}
		else {
			if (rechts == NULL) {
				rechts = neu; }
			else {rechts->erstellen(neu);
			}
		}
	}

//}

	

			
		
	
		
		
		







int _tmain(int argc, _TCHAR* argv[])
{
	Knoten k1();
	
	tree l1;
	l1.Wert = 1;
	l1.erstellen(k1);
	return 0;
}

Ich bin mal wieder für jede Hilfe dankbar!

 

[claW.]

und wie lautet der "komische" fehler? ohne den zu wissen kann man dir nur sehr begrenzt helfen

 

[Graf-Porno]

Error 1 error C2533: 'tree::{ctor}' : constructors not allowed a return type c:\dokumente und einstellungen\philipp\eigene dateien\visual studio 2005\projects\baumklasse\baumklasse\baumklasse.cpp 16.

So habe das Problem mit dem Konstruktor wohl gelöst, jedoch kann ich nichts in den Baum einfügen.

Der aktualisierte Quellcode steht oben.

 

[cplusplus]

Hi Graf-Porno, dein Code ist leider nicht sehr übersichtlich und hat keine erkennbare Struktur, was Groß und Kleinschreibung angeht (ich würde vorschlagen alle Klassen groß zu schreiben und die Member klein). Kommentare helfen die Lesbarkeit zu unterstützen. Es ist so recht mühsam deinen Gedankengängen beim Schreiben des Algorithmus zu folgen.

Zunächst mal hast du ein Memory Leak, d.h. du reservierst Speicher, gibst ihn aber nirgends mehr frei. Jeder mit malloc() geholte Speicherbereich muss früher oder später wieder durch ein free() freigegeben werden. Anstatt malloc und free solltest du in C++ die Operatoren new und delete verwenden. Mit malloc/free wird weder ein Constructor noch ein Destructor aufgerufen!

Ich nehme an, du willst mit der Methode

void tree::erstellen(tree *neu)

Elemente in den Baum einfügen. Was neu ist kann ich nur raten, aber ich denke mal das ist ein in den Baum einzufügender Teilbaum. Die Variable neu wird aber direkt in der übernächsten Zeile mit dem Rückgabewert von malloc() überschrieben, d.h. für die Methode tree::erstellen ist es unerheblich mit welchem Parameter neu es aufgerufen wird.

Dadurch dass durch malloc der Constructor nicht zum Zug kommt ist in der darauf folgenden if-Anweisung nicht definiert, welche Zahl in neu->Wert steht:

		if ((neu = (tree *)malloc(sizeof (tree)))!=NULL);
		if (neu->Wert<Wert) {

Verwendet man anstatt malloc() den Operator new

		neu = new tree;
		if (neu->Wert<Wert) {

so ist neu->Wert immer gleich 0 (siehe Constructor von tree). Die if-Anweisung ist dann gleichbedeutend mit if (0<Wert). Das ist für mich ein Hinweis, dass hier irgendwas nicht so läuft, wie du es geplant hast.

Noch ein paar Kommentare von mir:

if ((neu = (tree *)malloc(sizeof (tree)))!=NULL);

Führe eine leere Anweisung aus, falls neu ungleich 0. Der if-Block ist nur ein Semikolon, daher sollte das folgende äquivalent sein:

neu = (tree *)malloc(sizeof (tree)));

Nicht ganz nachvollziehen kann ich die doppelte Modellierung von Knoten. Für mich ist die Klasse tree schon ein Knoten. Kannst du das vielleicht etwas weiter erläutern?

Viele Grüße
Daniel

 

[Graf-Porno]

Hi Danke für die Antwort, hab das ganze mal versucht etwas ordentlicher zu gestalten.

// BaumKlasse.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <stdlib.h>


class BaumElement {
public:	
	BaumElement *rechts;							//Pointer auf das jeweils recht und linke Element	
	BaumElement *links;
	int index;										//Indexierungswert um den Baum bzw ein anderer beliebiger Wert um den Baum zu strukturieren
	BaumElement ();									//Std. construktor der ein Element erzeugt das in keine Richtung zeigt mit dem Indexwert 0.
	~BaumElement ();
	void einfuegen (BaumElement *BElement);			//Eine Funktion um  ein neues Baum Element in den Baum einzufügen.
};

BaumElement::BaumElement() {
	rechts = NULL;
	links  = NULL;
	index = 0;
};

//WuzelKlasse sie stellt die Wurzel für den Baum dar und soll die größe speichern, falls der Baum NULL ist soll hier eine das neue Element zur Wurzel werden

class Wurzel {
public:
	BaumElement *root;
	int size;
	Wurzel ();
	~Wurzel();
};

Wurzel::Wurzel() {
	root->links=NULL;
	root->rechts=NULL;
	size = 0;
};


void BaumElement::einfuegen(BaumElement *BElement) {
	BaumElement *neu;	
	neu = new BaumElement;   //So mein Problem hier ist nun wie greife ich auf mein vorheriges Element zu, um zu prüfen ob der Wert größer oder kleiner ist, bzw ob er überhaupt existiert,damit 
	                                            // er zur neuen Wurzel werden kann?

}







int main (void) {
	return 0;
}

War gestern auch etwas spät danke für deine Hilfe im Übrigen.

 

[cplusplus]

Wurzel::Wurzel() {
	root->links=NULL;
	root->rechts=NULL;
	size = 0;
}

Das gibt einen Speicherzugriffsfehler, da root nicht sinnvoll initialisiert ist. Designtechnisch würde ich auch sagen, dass BaumElement für die Initialisierung seiner Member zuständig sein sollte. Mein Vorschlag:

Wurzel::Wurzel() {
	root = NULL;
	size = 0;
}

Damit hast du einen leeren Baum. Wurzel::einfuegen könnte dann so aussehen:

Wurzel::einfuegen(BaumElement *elem) {
	size++;
	if (root)
		root->einfuegen(elem);   // in den bestehenden Baum einfügen
	else
		root = elem;             // der Baum ist leer => elem wird zur Wurzel
}

Das Einfügen in den Baum geschieht in BaumElement::einfuegen(BaumElement *elem) und damit zu deiner Frage. Du hast zwei Möglichkeiten: Entweder der Baum selbst erstellt das BaumElement oder derjenige, der in den Baum einfügt. Bei Wurzel::einfuegen oben habe ich angenommen, dass der Aufrufende das BaumElement erzeugt, was die Signatur deiner BaumElement::einfuegen Methode nahelegt. Du hast hier ja schon zwei Elemente, die du vergleichen kannst:

void BaumElement::einfuegen(BaumElement *elem) {
	if (index < elem->index) {
		...
	} else {
		...
	}
}

So mein Problem hier ist nun wie greife ich auf mein vorheriges Element zu, um zu prüfen ob der Wert größer oder kleiner ist, bzw ob er überhaupt existiert,damit er zur neuen Wurzel werden kann?

Du brauchst das vorherige Element nicht und die Wurzel muss sich nicht ändern außer du hast eine Balancierung des Baums. Du willst doch im aktuellen Element wissen, ob du links oder rechts absteigen mußt um das neue Element elem einzufügen oder willst du einen anderen Baum als ich implementieren?

Du mußt dir dann noch Gedanken machen, wer den Speicher wieder aufräumt. Am einfachsten wird es sein, wenn dafür der Baum zuständig ist, d.h. du solltest in den jeweiligen Destructoren root, links und rechts mit delete löschen.

Viele Grüße
Daniel

 

[Graf-Porno]

Hi, ich habe mal versucht deine Ratschläge so gut wie möglich umzusetzten, könntest du nocheinmal einen Blick draufwerfen, da das ganze noch Probleme bereitet.

// BaumKlasse.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <stdlib.h>


class BaumElement {
public:	
	BaumElement *rechts;							//Pointer auf das jeweils recht und linke Element	
	BaumElement *links;
	int index;										//Indexierungswert um den Baum zu ordnen
	BaumElement ();									//Std. construktor der ein Element erzeugt das in keine Richtung zeigt mit dem Indexwert 0.
	~BaumElement ();
	void einfuegen (BaumElement *Belement);			//Eine Funktion um  ein neues Baum Element in den Baum einzufügen.
	BaumElement (int wert);
};

BaumElement::BaumElement(int wert)
{
	index = wert;
};

BaumElement::~BaumElement () {
	delete links;
	delete rechts;
};

BaumElement::BaumElement() {
	rechts = NULL;
	links  = NULL;
	index = 0;
};

//WuzelKlasse sie stellt die Wurzel für den Baum dar und soll die größe speichern, falls der Baum NULL ist soll hier eine das neue Element zur Wurzel werden

class Wurzel {
public:
	BaumElement *root;
	int size;	
	Wurzel ();
	~Wurzel();
	void einfuegen (BaumElement *Belement);
};

Wurzel::Wurzel() {
	root = NULL;
	size = 0;
};


Wurzel::~Wurzel () {
	delete root;
}

void BaumElement::einfuegen(BaumElement *Belement) {
	if (Belement->index < index ) {
		if (links == NULL) {
			links = Belement;
			printf ("Eingefügt");
		} else {
		printf (" <<- ");
		links->einfuegen (Belement);
		}
	}
	if (Belement->index > index ) {
		if (rechts == NULL) {
			rechts = Belement;
			printf ("Eingefügt");
		}else {
			printf (" ->> ");
		rechts->einfuegen (Belement);
		}		
	}
}
	
void Wurzel::einfuegen(BaumElement *Belement) {
	size++;
	if (root) {
		root->einfuegen(Belement);
	} else {
		root = Belement;
	}
};

int main (void) {
	Wurzel t();
	Wurzel test2;
	
//	test2 = new Wurzel();
	BaumElement n(3);
	test2.einfuegen (&n);
	return 0;
}

Gruß

 

[cplusplus]

Ich habs jetzt nicht selbst kompiliert und ausprobiert, aber bis auf die main Funktion sollte es funktionieren (Belement->index == index wird noch nicht behandelt => Memory Leak!).

In deiner main Funktion gehst du wieder davon aus, dass Objekte von BaumElement der main Funktion gehören. Du mußt dich einmal für einen Weg entscheiden (Ownership). Ich finde es sinnvoller, wenn die Ownership beim Aufrufen von einfuegen() an den Baum übergeht (darum auch das delete im Destructor). Du kannst also entweder die delete's in den Destructoren weglassen (links und rechts gehört dann nicht dem BaumElement) oder du gestaltest deine main folgendermaßen (das neu erzeugte BaumElement wird vom Baum gelöscht, darum wird in der main kein delete mehr aufgerufen):

int main (void) {
	Wurzel t();
	t.einfuegen(new BaumElement(3));
	return 0;
}

Dein von dir auskommentierter Code sieht eher nach raten aus und kann nicht funktionieren:

	Wurzel test2;
	test2 = new Wurzel();

test2 ist eine Instanz von Wurzel und wird auf dem Stack erzeugt. new Wurzel() allokiert Speicher im Heap und gibt einen Pointer auf Wurzel zurück, also Wurzel*. Entweder also

	Wurzel test2;
	test2.einfuegen(...);

oder

	Wurzel* test2 = new Wurzel();
	test2->einfuegen(...);
	...
	delete test2;

PS: Bei einmaligen einfuegen() in der Wurzel wirst du deine printf's noch nicht sehen, da das Element von Wurzel an root zugewiesen wird.

Viele Grüße
Daniel

 

[Graf-Porno]

Jo das stimmt ich aber auch nur gemacht da ich immer wieder accesviolation Fehler bekomme..

hab den Fall Belement->index == index einfach noch zum rechten Teil gepackt und somit abgefangen.

// BaumKlasse.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <stdlib.h>


class BaumElement {
public:	
	BaumElement *rechts;							//Pointer auf das jeweils recht und linke Element	
	BaumElement *links;
	int index;										//Indexierungswert um den Baum zu ordnen
	BaumElement ();									//Std. construktor der ein Element erzeugt das in keine Richtung zeigt mit dem Indexwert 0.
	~BaumElement ();
	void einfuegen (BaumElement *Belement);			//Eine Funktion um  ein neues Baum Element in den Baum einzufügen.
	BaumElement (int wert);
};

BaumElement::BaumElement(int wert)
{
	index = wert;
};

BaumElement::~BaumElement () {
	delete links;
	delete rechts;	
};

BaumElement::BaumElement() {
	rechts = NULL;
	links  = NULL;
	index = 0;
};

//WuzelKlasse sie stellt die Wurzel für den Baum dar und soll die größe speichern, falls der Baum NULL ist soll hier eine das neue Element zur Wurzel werden

class Wurzel {
public:
	BaumElement *root;
	int size;	
	Wurzel ();
	~Wurzel();
	void einfuegen (BaumElement *Belement);
};

Wurzel::Wurzel() {
	root = NULL;
	size = 0;
};


Wurzel::~Wurzel () {
	delete root;
}

void BaumElement::einfuegen(BaumElement *Belement) {
	
	if (Belement->index < index ) {
		if (links == NULL) {
			links = Belement;
			printf ("Eingefügt");
		} else {
		printf (" <<- ");
		links->einfuegen (Belement);
		}
	}
	if (Belement->index >= index ) {
		if (rechts == NULL) {
			rechts = Belement;
			printf ("Eingefügt");
		}else {
			printf (" ->> ");
		rechts->einfuegen (Belement);
		}		
	}
}
	
void Wurzel::einfuegen(BaumElement *Belement) {
	size++;
	if (root) {
		root->einfuegen(Belement);
	} else {
		root = Belement;
	}
};

int main (void) {
	Wurzel* test2 = new Wurzel();
	BaumElement* k = new BaumElement (4);
	test2->einfuegen(k);
	delete test2;
	return 0;
}

Ist mein erster Baum und mit Pointer hab ich auch noch nie so richtig was gemacht.,
mal wieder Danke im Vorraus!

 

[cplusplus]

Dein Constructor BaumElement::BaumElement(int wert) initialisiert rechts und links nicht mit NULL. Daher wahrscheinlich auch die Access Violations.

PS: Statt dem "if (Belement->index >= index )" würde es auch ein einfaches else der darüber liegenden if-Anweisung tun.

 

[Graf-Porno]

Jau läiuft alles ich dank dir!