C/C++ Forum :: Sortieren mit binärem Baum

Unregistrierter

Hallo,

mit Hilfe eines binären Baumes möchte ich einen Vektor sortieren. Die Funktion sort() soll nacheinander die int-Werte des Vektors an die insert() Funktion übergeben. Die insert() Funktion soll die Zahlen an der entsprechenden Stelle in den Baum einfügen. Leider erhalte ich mit meinem folgenden Code einige Fehlermeldungen (siehe unten). Wäre super, wenn mir hier jemand weiterhelfen könnte. Danke!

C/C++ Code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42	1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42	#include <iostream> #include <fstream> #include <stdlib.h> #include <vector> #include <cctype> #include <string> using namespace std; template <typename object> class bst { public: bst(object o) ; // Initialisiere neuen binären Baum bst<object> insert(object) ; // Gib neuen Baum zurück, welcher nun o enthält* private: object value ; // Der int Wert (Schlüssel) dieses Knotens bst<object> left ; // Sub-Baum: Kleiner als Schlüssel* bst<object> right ; // Sub-Baum: Größer/Gleich dem Schlüssel* } ; // Initialisiere einen neuen binären Baumknoten template <typename object> bst<object>::bst(object o) { this->value = o; this->left = NULL; this->right = NULL; } // Gib neuen Baum zurück, welcher o enthält template <typename object> bst<object> insert(object v) { if (this* == NULL) { bst<object> node = new bst<object>(v); return node; } if (v < value) return left->insert(v); else return right->insert(v); }

C/C++ Code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42	#include <iostream> #include <fstream> #include <stdlib.h> #include <vector> #include <cctype> #include <string> using namespace std; template <typename object> class bst { public: bst(object o) ; // Initialisiere neuen binären Baum bst<object> insert(object) ; // Gib neuen Baum zurück, welcher nun o enthält* private: object value ; // Der int Wert (Schlüssel) dieses Knotens bst<object> left ; // Sub-Baum: Kleiner als Schlüssel* bst<object> right ; // Sub-Baum: Größer/Gleich dem Schlüssel* } ; // Initialisiere einen neuen binären Baumknoten template <typename object> bst<object>::bst(object o) { this->value = o; this->left = NULL; this->right = NULL; } // Gib neuen Baum zurück, welcher o enthält template <typename object> bst<object> insert(object v) { if (this* == NULL) { bst<object> node = new bst<object>(v); return node; } if (v < value) return left->insert(v); else return right->insert(v); }

C/C++ Code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42	#include <iostream> #include <fstream> #include <stdlib.h> #include <vector> #include <cctype> #include <string> using namespace std; template <typename object> class bst { public: bst(object o) ; // Initialisiere neuen binären Baum bst<object> insert(object) ; // Gib neuen Baum zurück, welcher nun o enthält* private: object value ; // Der int Wert (Schlüssel) dieses Knotens bst<object> left ; // Sub-Baum: Kleiner als Schlüssel* bst<object> right ; // Sub-Baum: Größer/Gleich dem Schlüssel* } ; // Initialisiere einen neuen binären Baumknoten template <typename object> bst<object>::bst(object o) { this->value = o; this->left = NULL; this->right = NULL; } // Gib neuen Baum zurück, welcher o enthält template <typename object> bst<object> insert(object v) { if (this* == NULL) { bst<object> node = new bst<object>(v); return node; } if (v < value) return left->insert(v); else return right->insert(v); }

Und hier die aufrufende Sortierfunktion:

C/C++ Code:
1 2 3 4 5 6 7 8 9 10	1 2 3 4 5 6 7 8 9 10	// Sortiere alle Zahlen aus dem Vektor 'vec' durch hinzufügen in bst<int> void sort(vector<int> &vec) { bst<object> tree; for (int i=0; i<vec.size(); i++) { tree = tree->insert(vec[i]); } return; }

C/C++ Code:
1 2 3 4 5 6 7 8 9 10	// Sortiere alle Zahlen aus dem Vektor 'vec' durch hinzufügen in bst<int> void sort(vector<int> &vec) { bst<object> tree; for (int i=0; i<vec.size(); i++) { tree = tree->insert(vec[i]); } return; }

C/C++ Code:
1 2 3 4 5 6 7 8 9 10	// Sortiere alle Zahlen aus dem Vektor 'vec' durch hinzufügen in bst<int> void sort(vector<int> &vec) { bst<object> tree; for (int i=0; i<vec.size(); i++) { tree = tree->insert(vec[i]); } return; }

Mein code führt zu folgender Fehlermeldung:

Code:
1 2 3 4 5 6 7 8	1 2 3 4 5 6 7 8	bst.h: In function ‘bst<object>* insert(object)’: bst.h:23: error: invalid use of ‘this’ in non-member function bst.h:29: error: ‘value’ was not declared in this scope bst.h:29: error: request for member ‘insert’ in ‘std::left->’, which is of non-class type ‘std::ios_base& ()(std::ios_base&)’ bst.h:30: error: request for member ‘insert’ in ‘std::right->’, which is of non-class type ‘std::ios_base& ()(std::ios_base&)’ sort.cpp:12: error: variable or field ‘sort’ declared void sort.cpp:12: error: ‘vector’ was not declared in this scope sort.cpp:12: error: expected primary-expression before ‘int’

Code:
1 2 3 4 5 6 7 8	bst.h: In function ‘bst<object>* insert(object)’: bst.h:23: error: invalid use of ‘this’ in non-member function bst.h:29: error: ‘value’ was not declared in this scope bst.h:29: error: request for member ‘insert’ in ‘std::left->’, which is of non-class type ‘std::ios_base& ()(std::ios_base&)’ bst.h:30: error: request for member ‘insert’ in ‘std::right->’, which is of non-class type ‘std::ios_base& ()(std::ios_base&)’ sort.cpp:12: error: variable or field ‘sort’ declared void sort.cpp:12: error: ‘vector’ was not declared in this scope sort.cpp:12: error: expected primary-expression before ‘int’

Code:
1 2 3 4 5 6 7 8	bst.h: In function ‘bst<object>* insert(object)’: bst.h:23: error: invalid use of ‘this’ in non-member function bst.h:29: error: ‘value’ was not declared in this scope bst.h:29: error: request for member ‘insert’ in ‘std::left->’, which is of non-class type ‘std::ios_base& ()(std::ios_base&)’ bst.h:30: error: request for member ‘insert’ in ‘std::right->’, which is of non-class type ‘std::ios_base& ()(std::ios_base&)’ sort.cpp:12: error: variable or field ‘sort’ declared void sort.cpp:12: error: ‘vector’ was not declared in this scope sort.cpp:12: error: expected primary-expression before ‘int’

Scorcher24 Mitglied 05:05:04 24.10.2009 Titel:

bst<object>::bst(object o)
Das <object> kannst beim Constructor weglassen.
bst::bst(object o)
reicht.
rya.

Unregistrierter

Das löst leider nicht das Problem. Ich erhalte ohne <object> folgende Meldungen zusätzlich:

Code:
bst.h:12: error: ‘template<class object> class bst’ used without template parameters bst.h:12: error: ISO C++ forbids declaration of ‘bst’ with no type bst.h:12: error: declaration of template ‘template<class object> int bst(object)’

Code:
bst.h:12: error: ‘template<class object> class bst’ used without template parameters bst.h:12: error: ISO C++ forbids declaration of ‘bst’ with no type bst.h:12: error: declaration of template ‘template<class object> int bst(object)’

Code:
bst.h:12: error: ‘template<class object> class bst’ used without template parameters bst.h:12: error: ISO C++ forbids declaration of ‘bst’ with no type bst.h:12: error: declaration of template ‘template<class object> int bst(object)’

Unregistrierter

Die meisten Fehler habe ich in der Zwischenzeit gelöst. Zeile 11 der folgenden Prozedur macht allerdings noch Probleme.

C/C++ Code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20	1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20	#include <iostream> #include <fstream> #include <stdlib.h> #include <vector> #include <cctype> #include <string> #include "bst.h" // Sortiere alle Zahlen aus dem Vektor 'vec' durch hinzufügen in bst<int> void sort(vector<int> &vec) { bst<object> tree; for (int i=0; i<vec.size(); i++) { tree = tree->insert(vec[i]); } return; }

C/C++ Code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20	#include <iostream> #include <fstream> #include <stdlib.h> #include <vector> #include <cctype> #include <string> #include "bst.h" // Sortiere alle Zahlen aus dem Vektor 'vec' durch hinzufügen in bst<int> void sort(vector<int> &vec) { bst<object> tree; for (int i=0; i<vec.size(); i++) { tree = tree->insert(vec[i]); } return; }

C/C++ Code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20	#include <iostream> #include <fstream> #include <stdlib.h> #include <vector> #include <cctype> #include <string> #include "bst.h" // Sortiere alle Zahlen aus dem Vektor 'vec' durch hinzufügen in bst<int> void sort(vector<int> &vec) { bst<object> tree; for (int i=0; i<vec.size(); i++) { tree = tree->insert(vec[i]); } return; }

Kann mir jemand erklären, wieso ich folgenden Fehler bekomme?

Code:
1 2 3 4 5 6 7 8	1 2 3 4 5 6 7 8	sort.cpp: In function ‘void sort(std::vector<int, std::allocator<int> >&)’: sort.cpp:14: error: ‘object’ was not declared in this scope sort.cpp:14: error: template argument 1 is invalid sort.cpp:14: error: invalid type in declaration before ‘=’ token sort.cpp:14: error: ‘object’ cannot appear in a constant-expression sort.cpp:14: error: template argument 1 is invalid sort.cpp:14: error: invalid conversion from ‘int*’ to ‘int’ sort.cpp:16: error: base operand of ‘->’ is not a pointer

Code:
1 2 3 4 5 6 7 8	sort.cpp: In function ‘void sort(std::vector<int, std::allocator<int> >&)’: sort.cpp:14: error: ‘object’ was not declared in this scope sort.cpp:14: error: template argument 1 is invalid sort.cpp:14: error: invalid type in declaration before ‘=’ token sort.cpp:14: error: ‘object’ cannot appear in a constant-expression sort.cpp:14: error: template argument 1 is invalid sort.cpp:14: error: invalid conversion from ‘int*’ to ‘int’ sort.cpp:16: error: base operand of ‘->’ is not a pointer

Code:
1 2 3 4 5 6 7 8	sort.cpp: In function ‘void sort(std::vector<int, std::allocator<int> >&)’: sort.cpp:14: error: ‘object’ was not declared in this scope sort.cpp:14: error: template argument 1 is invalid sort.cpp:14: error: invalid type in declaration before ‘=’ token sort.cpp:14: error: ‘object’ cannot appear in a constant-expression sort.cpp:14: error: template argument 1 is invalid sort.cpp:14: error: invalid conversion from ‘int*’ to ‘int’ sort.cpp:16: error: base operand of ‘->’ is not a pointer

Siassei Mitglied 09:37:12 24.10.2009 Titel:

Servus,

die sort-Funktion ist eine Funktion im globalen Namensraum

Du musst beim Implementieren darauf achten, dass du sie zu einer Klassen::Methode machst.

C/C++ Code:
template <typename object> void bst<object>::sort(vector<int> &vec) { // ... }

C/C++ Code:
template <typename object> void bst<object>::sort(vector<int> &vec) { // ... }

C/C++ Code:
template <typename object> void bst<object>::sort(vector<int> &vec) { // ... }

Sebastian Pizer Mitglied 09:54:52 24.10.2009 Titel:

Pack Deinen Code doch mal vollständig auf codepad drauf und schick den Link rum.

Eines vorweg: Dein insert ist eine nicht-statische Elementfunktion, die einen "this==NULL" Vergleich enthält. Das ist schonmal sehr verdächtig. Ich würde es als statische Elementfunktion machen:

C/C++ Code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34	1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34	template<typename T> class bst : boost::noncopyable { public: explicit bst(T const& x) : left(0), right(0), value(x) {} static bst<T>* insert(bst<T>& root, T const& x); private: bst<T> left; bst<T>* right; T value; }; template<typename T> bst<T>* bst<T>::insert(bst<T>& root, T const& x) { bst<T>* pp = &root; while (pp) { bst<T> & current = pp; if (x < current.value) pp = &current.left; else* pp = &current.right; } pp = new* bst<T>(x); return pp; } int* foo() { bst<int>* wurzel = 0; bst<int>::insert(wurzel,5); bst<int>::insert(wurzel,4); bst<int>::insert(wurzel,8); // löschen nicht vergessen! }

C/C++ Code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34	template<typename T> class bst : boost::noncopyable { public: explicit bst(T const& x) : left(0), right(0), value(x) {} static bst<T>* insert(bst<T>& root, T const& x); private: bst<T> left; bst<T>* right; T value; }; template<typename T> bst<T>* bst<T>::insert(bst<T>& root, T const& x) { bst<T>* pp = &root; while (pp) { bst<T> & current = pp; if (x < current.value) pp = &current.left; else* pp = &current.right; } pp = new* bst<T>(x); return pp; } int* foo() { bst<int>* wurzel = 0; bst<int>::insert(wurzel,5); bst<int>::insert(wurzel,4); bst<int>::insert(wurzel,8); // löschen nicht vergessen! }

C/C++ Code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34	template<typename T> class bst : boost::noncopyable { public: explicit bst(T const& x) : left(0), right(0), value(x) {} static bst<T>* insert(bst<T>& root, T const& x); private: bst<T> left; bst<T>* right; T value; }; template<typename T> bst<T>* bst<T>::insert(bst<T>& root, T const& x) { bst<T>* pp = &root; while (pp) { bst<T> & current = pp; if (x < current.value) pp = &current.left; else* pp = &current.right; } pp = new* bst<T>(x); return pp; } int* foo() { bst<int>* wurzel = 0; bst<int>::insert(wurzel,5); bst<int>::insert(wurzel,4); bst<int>::insert(wurzel,8); // löschen nicht vergessen! }

(ungetestet)

Gruß,
SP

Unregistrierter

Danke!

@Sebastian: Das Problem ist, dass die verwendeten Methoden aus der Klasse bst bereits vordeklariert sind. Das heißt, ich kann aus der insert() Funktion mit EINEM Argument keine insert() Funktion mit ZWEI Argumenten machen. Es wäre tatsächlich schön, wenn ich dieser Funktion immer den root pointer übergeben könnte. Ich darf dieser Funktion aber nur EIN Argument vom Typ "object" übergeben. Demzufolge muss ich doch über den this pointer auf den entsprechenden Knoten zugreifen, oder?

@Siassei: Ich verstehe gerade nicht so ganz, wieso die sort() Funktion zu einer Klasse gehören muss. Ich denke, sie darf definitiv nicht zur Klasse bst gehören, denn sort() erstellt doch die Objekte vom Typ bst<object>. Meinst du, es muss eine zusätzliche Klasse geben, welche die sort() Funktion enthält?

Folgende Funktionen sind in der Klasse bst fest vordefiniert und dürfen nicht verändert werden:

Code:
bst(object o) ; bst<object> insert(object) ; bst<object> lookup(object) ; void showme(vector<object>&) ; object value ; bst<object> left ; bst<object> right ;

Code:
bst(object o) ; bst<object> insert(object) ; bst<object> lookup(object) ; void showme(vector<object>&) ; object value ; bst<object> left ; bst<object> right ;

Code:
bst(object o) ; bst<object> insert(object) ; bst<object> lookup(object) ; void showme(vector<object>&) ; object value ; bst<object> left ; bst<object> right ;

Und folgende Funktionen müssen in seperaten Dateien sort.cpp und parser.cpp sein:

Code:
void sort(vector<int> &vector_to_sort) ; bool parse_file(const string &file_name,vector<int> &vector_of_ints_in_file) ;

Code:
void sort(vector<int> &vector_to_sort) ; bool parse_file(const string &file_name,vector<int> &vector_of_ints_in_file) ;

Code:
void sort(vector<int> &vector_to_sort) ; bool parse_file(const string &file_name,vector<int> &vector_of_ints_in_file) ;

Th69 Mitglied 09:04:34 25.10.2009 Titel:

Die beiden Funktionen müssen nicht in der Klasse definiert werden.

Dein Fehler in der sort-Funtkion war ganz einfach, daß "object" dort unbekannt ist: du mußt schon den richtigen Datentyp angeben (im Kommentar steht es ja schon!):

C/C++ Code:
1 2 3 4 5 6 7 8 9	1 2 3 4 5 6 7 8 9	// Sortiere alle Zahlen aus dem Vektor 'vec' durch hinzufügen in bst<int> void sort(vector<int> &vec) { bst<int>* tree; // <-- int statt object (und Zeiger statt Instanz) for (int i=0; i<vec.size(); i++) { tree = tree->insert(vec[i]); } }

C/C++ Code:
1 2 3 4 5 6 7 8 9	// Sortiere alle Zahlen aus dem Vektor 'vec' durch hinzufügen in bst<int> void sort(vector<int> &vec) { bst<int>* tree; // <-- int statt object (und Zeiger statt Instanz) for (int i=0; i<vec.size(); i++) { tree = tree->insert(vec[i]); } }

C/C++ Code:
1 2 3 4 5 6 7 8 9	// Sortiere alle Zahlen aus dem Vektor 'vec' durch hinzufügen in bst<int> void sort(vector<int> &vec) { bst<int>* tree; // <-- int statt object (und Zeiger statt Instanz) for (int i=0; i<vec.size(); i++) { tree = tree->insert(vec[i]); } }

Dies löst aber nur deine syntaktischen Probleme.

Der obige Funktionscode ist jedoch nicht lauffähig, weil der Baum nicht initialisiert ist (die Abfrage in der insert-Methode auf "this == NULL" wurde ja schon angesprochen!) und die Zuweisung des Rückgabewerts von der insert-Methode an 'tree' ergibt auch keinen wirklichen Sinn (bezogen auf einen Binärbaum)...

Sebastian Pizer Mitglied 09:31:55 25.10.2009 Titel:

Mark007 schrieb:

Das Problem ist, dass die verwendeten Methoden aus der Klasse bst bereits vordeklariert sind. Das heißt, ich kann aus der insert() Funktion mit EINEM Argument keine insert() Funktion mit ZWEI Argumenten machen. Es wäre tatsächlich schön, wenn ich dieser Funktion immer den root pointer übergeben könnte. Ich darf dieser Funktion aber nur EIN Argument vom Typ "object" übergeben.

Das ist nicht schlimm. Du musst die Funktion nur sinnvoll implementieren. "this==NULL" ist Quatsch, da Du die Funktion nur auf einem gültigen Objekt aufrufen darfst.

Du brauchst dann eine Fallunterscheidung: Gibt es schon einen Wurzelknoten oder gibt es ihn noch nicht? Diese Sonderbehandlung kannst Du trotzdem in einer neuen Funktion verstecken, die Dir das Leben leichter macht:

C/C++ Code:
1 2 3 4 5 6 7 8 9	1 2 3 4 5 6 7 8 9	template<typename T> bst<T>* leichter_benutzbares_insert( bst<T>& root, typename* boost::call_traits<T>::param_type x) { if (root) return root->insert(x); root = new bst<T>(x); return root; }

C/C++ Code:
1 2 3 4 5 6 7 8 9	template<typename T> bst<T>* leichter_benutzbares_insert( bst<T>& root, typename* boost::call_traits<T>::param_type x) { if (root) return root->insert(x); root = new bst<T>(x); return root; }

C/C++ Code:
1 2 3 4 5 6 7 8 9	template<typename T> bst<T>* leichter_benutzbares_insert( bst<T>& root, typename* boost::call_traits<T>::param_type x) { if (root) return root->insert(x); root = new bst<T>(x); return root; }

Der erste Parameter ist eine Referenz auf einen Zeiger. Der Zeiger kann also bleibend verändert werden, zB wenn es noch keinen Knoten gibt. Der zweite Parameter ist vom Typ T bzw "const T&", je nachdem, was vielversprechender bzgl Performance ist. Ich habe es aber auch benutzt, damit der 2. Parameter nicht vom Compiler dazu benutzt wird, T zu herzuleiten. Du kannst die Funktion dann auch so aufrufen:

C/C++ Code:
bst<double>* wurzel = 0; leichter_benutzbares_insert(wurzel,24);

C/C++ Code:
bst<double>* wurzel = 0; leichter_benutzbares_insert(wurzel,24);

C/C++ Code:
bst<double>* wurzel = 0; leichter_benutzbares_insert(wurzel,24);

(24 ist ein int, wird aber zu double konvertiert)

Ich schätze, man will, dass Du bst<T>::insert als Rekursion implementierst. Das ist natürlich möglich, aber meiner Meinung nach unschön, weil es wieder eine Sonderbehandlung erfordert (nicht wegen der Rekursion, wegen der nicht-statischen Elementfunktion) und zweitens auf Kosten des automatischen Speichers geht (wegen der Rekursion).

Gruß,
SP

Unregistrierter

Hallo zusammen,

Vielen Dank für eure Hilfe!! Ich muss jetzt doch nochmal fragen und es klingt für euch wahrscheinlich total dämlich :o)

aber ich steh gerade einfach auf dem Schlauch und komme alleine nicht weiter.

Mein Problem ist, dass die insert() Funktion nur EINEN Parameter haben darf. Es darf kein Wurzelzeiger übergeben werden, sondern nur der Integer-Schlüssel. Dass this==NULL keinen Sinn macht, sehe ich jetzt. Ich wollte damit überprüfen, ob der Knoten bereits existiert. Da ich keinen root-pointer übergeben bekommen darf, muss ich doch irgendwie mit dem this-pointer arbeiten. Ich muss davon ausgehen, dass das aufrufende Objekt die Wurzel meines Baumes ist.

Meine insert() Funktion sieht noch folgendermaßen aus:

C/C++ Code:
1 2 3 4 5 6 7 8 9 10 11	1 2 3 4 5 6 7 8 9 10 11	template <typename object> bst<object> bst<object>::insert(object v) { if (this* == NULL) { bst<object> node = new bst<object>(v); return node; } if (v < value) return left->insert(v); else return right->insert(v); }

C/C++ Code:
1 2 3 4 5 6 7 8 9 10 11	template <typename object> bst<object> bst<object>::insert(object v) { if (this* == NULL) { bst<object> node = new bst<object>(v); return node; } if (v < value) return left->insert(v); else return right->insert(v); }

C/C++ Code:
1 2 3 4 5 6 7 8 9 10 11	template <typename object> bst<object> bst<object>::insert(object v) { if (this* == NULL) { bst<object> node = new bst<object>(v); return node; } if (v < value) return left->insert(v); else return right->insert(v); }

Und die Aufrufende Funktion:

C/C++ Code:
1 2 3 4 5 6 7 8 9 10	1 2 3 4 5 6 7 8 9 10	void sort(vector<int> &vec) { bst<int>* tree; for (int i=0; i<vec.size(); i++) { tree = tree->insert(vec[i]); } return; }

C/C++ Code:
1 2 3 4 5 6 7 8 9 10	void sort(vector<int> &vec) { bst<int>* tree; for (int i=0; i<vec.size(); i++) { tree = tree->insert(vec[i]); } return; }

C/C++ Code:
1 2 3 4 5 6 7 8 9 10	void sort(vector<int> &vec) { bst<int>* tree; for (int i=0; i<vec.size(); i++) { tree = tree->insert(vec[i]); } return; }

Es gibt im Netz viel über binäre Suchbäume (Beispiel auf Wikipedia etc.), aber ALLE die ich bisher gefunden habe, bekommen in der insert Funktion den Wurzelknoten mitübergeben, was das ganze viel einfacher macht.