Tree

Eisflamme

Werner hat einfach nur eine Definition für tree_node vorausgesetzt, weil Du Deine noch nicht geposted hattest. Da Du deine jetzt ja gezeigt hast, musste das halt entsprechend dafür umbauen.

Außerdem hast Du keinen Binärbaum, sodass Du sowieso etwas Transferleistung bringen musst.

Okey, vielen Dank!

Jeps, hab's soweit gemacht. Allerdings hab ich noch zwei Fragen:

1.) Wenn man sowas hat:
if( nd )
return //...
dann prüft man einfach, ob "nd" vorhanden und korrekt gewählt ist, oder?

2.)Wie überprüft man, ob es sich um einen external_node (Blattknoten) handelt? ..also wie sieht die Idee dazu aus?

CStoll

MaxC++ schrieb:

1.) Wenn man sowas hat:
if( nd )
return //...
dann prüft man einfach, ob "nd" vorhanden und korrekt gewählt ist, oder?

Das ist im Prinzip äquivalent zu if(nd!=NULL)... - und wenn du unbenutzte Zeiger mit NULL vorbelegst, kannst du auf diese Weise prüfen, ob er belegt ist. Mit deinem vector<> kannst du dir die Überprüfung sparen (s.u.)

2.)Wie überprüft man, ob es sich um einen external_node (Blattknoten) handelt? ..also wie sieht die Idee dazu aus?

Wie ist denn der Begriff "Blatt" definiert - ein Knoten, der keine Nachfolger hat. Bei deinem Design ist das ganz einfach festzustellen, da alle Nachfolgerknoten in deinem vector<tree_node*> _children; untergrabracht sind.

Ahh..und ich dacht' schon, was die "_children" konkret sein sollen.

Eine Schlussfrage habe ich noch: Mein Compiler hat bei der tree_height-Methode etwas gejammert. Links- und Rechtsknoten gibt es bei mir ja eigentlich nicht - wie soll ich die Methode denn ohne li- re-Knoten implementieren?

CStoll

Auch über die children-Liste - du bestimmst die Höhe jedes Unterbaums (die einzelnen Kinder können als Wurzeln eines kleineren Unterbaums betrachtet werden), nimmst davon das Maximum und addierst noch 1 (für die Wurzel selber).

Okey, also ich hab mal sowas gemacht:

int tree::height() const
{
	return std::max(_children.size()) + 1;    
}

..was aber nicht stimmen kann, da: _children ja eigentlich ein private-Argument ist und ich also nicht so direkt darauf zugreifen kann..

CStoll

Nein, so klappt da nicht, du willst schließlich die maximale Höhe der Kinder haben und nicht die Größe der Kinder-Liste. Du mußt schon in einer Schleife über diese Liste laufen:

int kind_hoehe=0;
for(int i=0;i<children.size();++i)
  kind_hoehe=std::max(kind_hoehe,children[i]->height();
return kind_hoehe+1;

(und als nächstes lernen wir dann, wie du das selbe mit den STL-Algorithmen hinbekommst :D)

Aber Frage: _children ist in tree_node.hpp private, d.h. dass man ja nicht direkt darauf zugreifen kann..
(oder?)

STL-Algo? ..etwas einfacheres?

CStoll

MaxC++ schrieb:

Aber Frage: _children ist in tree_node.hpp private, d.h. dass man ja nicht direkt darauf zugreifen kann..
(oder?)

Die offensichtlichste Lsung ist dann wohl, diesen Code dorthin zu packen, wo du darauf zugreifen kannst - idealerweise wäre das die Methode tree_node::height().

STL-Algo? ..etwas einfacheres?

Nicht unbedingt einfacher, aber mitunter eleganter. Wenn du mehr darüber wissen willst, im Magazin gibt es noch einen alten Artikel von mir über die STL.

Okey, so hats eigentlich funktioniert.
Nur: Kann ich die Methode in tree.cpp nicht mit
"tree_node::height()" aufrufen?
..ich frage so dumm, weil mein Compiler da leider anderer Meinung ist..

Gerne, da werd' ich nachher einen Blick rein werfen

CStoll

Wenn du die Methode aufrufst, mußt du ihr auch sagen, für welches Objekt du sie anwenden willst - die Antwort heißt _root-height().

Ahh shit - das hab' ich eben auch gerade raus bekommen.
..darauf hätt' ich eigentlich sofort kommen sollen..

However, jetzt funktioniert alles wie gwünscht
Vielen herzlichen Dank für die Unterstützung euch allen!