Sortieren mit binärem Baum

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!

#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:

// 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:

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’

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

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

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)’

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

#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?

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

Servus,

die sort-Funktion ist eine Funktion im globalen Namensraum Du musst beim Implementieren darauf achten, dass du sie zu einer **Klassen::**Methode machst.

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

Sebastian Pizer

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:

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

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:

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:

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

Th69

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!):

// 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

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:

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:

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

Hallo zusammen,

Vielen Dank für eure Hilfe!! Ich muss jetzt doch nochmal fragen und es klingt für euch wahrscheinlich total dämlich 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:

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:

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.

Sebastian Pizer

Mark007 schrieb:

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

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);
}

immer noch Murks! Du hast Dir meinen vorherigen Beitrag nicht zu Herzen genommen, wie?

Wie ruft man Elementfunktionen auf? Man ruft sie auf einem Objekt auf. Also entweder o.insert(23); oder p->insert(42); wobei o ein bst-Objekt und p ein Zeiger auf ein existierendes bst-Objekt ist -- also p!=0. Der Fall p==0 ist nicht erlaubt! Deswegen macht auch dein this==NULL Vergleich keinen Sinn.

Mark007 schrieb:

Und die Aufrufende Funktion:

void sort(vector<int> &vec)
{
    bst<int>* tree;
    for (int i=0; i<vec.size(); i++)
    {
	  tree = tree->insert(vec[i]);
    }

    return;
}

tree wurde nicht initialisiert und Du rufst doch eine nicht-statische Elementfunktion auf! Der Zeiger tree zeigt irgendwo hin, wo's mit hoher Wahrscheinlichkeit KEIN bst-Objekt gibt. Was soll bst<>::insert eigentlich zurückgeben?! Ein Zeiger, klar, aber auf welchen Knoten soll der zeigen?

Gruß,
SP

pumuckl

weiter gehts hier:

http://www.c-plusplus.net/forum/viewtopic-var-t-is-252916.html