Binary Search Tree

[Mark007]

Hallo,

für eine Übungsaufgabe muss ich mit einem Treesort Algorithmus in C++ Zahlen sortieren. Die Zahlen befinden sich in einer "vector"-Struktur und sollen nacheinander über eine "insert()" Funktion in meinen Baum eingefügt werden.

Ich soll dabei die binary search tree template Klasse verwenden. Nach längerer online-Recherche habe ich nichts brauchbares über "GENAU DIESE" Klasse gefunden. Ich weiß schon, was ein binary search tree ist; nur frage ich mich gerade, wo ich etwas über dieses Template finden kann. In meinem C++ Buch ist diese nämlich nicht erwähnt.

Der Entwurf meiner entsprechenden Funktion sieht bisher folgendermaßen aus:

// initialise a new binary tree node
template <typename object>
bst<object>::bst(object o)
{

}

// return new tree with o added
bst<object> *insert(object t)
{
    if (t == null) return new v;
    if (v < t.val) t.left = insert(t.left, v);
    else t.right = insert(t.right, v);
    return t;
}

// append objects in infix order to the vector
void showme(vector<object>&)
{

}

/* in der .h Datei bereits deklarierte Variablen:
private:
	object value ;			// the object in this tree node
	bst<object> *left ;		// sub-tree of values less than key
	bst<object> *right ;		// sub-tree of values greater than or equals key
} ;*/

MfG Mark

[abcok]

hi,
die stl container set, map und multimap haben intern eine binäre, balancierte baumstruktur.
für nackte zahlen, wo die zahl der schlüssel ist, nimmsu set.
http://www.cplusplus.com/reference/stl/set/set/

[Mark007]

Danke für deine Antwort! Das Problem ist, dass ich mich an die Vorgaben halten muss und ich denke dass ich nicht einfach irgendetwas mit interner Baumstruktur nehmen darf. Es heißt explizit, ich muss die binary search tree template Klasse verwenden. Die Frage ist, gibt es eine derartige Klasse, oder ist damit wirklich gemeint, dass man sowas wie set nimmt, da diese container intern eine Baumstruktur haben?

[unskilled]

lies doch mal die teilaufgaben vor dieser durch - da steht mit ziemlicher sicherheit, dass du diese klasse erst mal erstellen sollst!?

bb

[ugh]

die oben genannten klassen sind stl template klassen.
aber vllt sollt ihr eure eigene zur übung programmieren?