Rekursives Erstellen einer Baumstruktur

[314159265358979]

In diesem Fall muss er sogar Zeiger nehmen, für den Fall, dass der vector einen neuen Speicherbereich alloziert und umkopiert. In eine std::list könnte er per Value speichern.

[Michael E.]

314159265358979 schrieb:

In diesem Fall muss er sogar Zeiger nehmen, für den Fall, dass der vector einen neuen Speicherbereich alloziert und umkopiert. In eine std::list könnte er per Value speichern.

Versteh ich nicht.

Als Grundregel: Wenn man sich nicht sicher ist, welchen Container man braucht, nimmt man nen std::vector (ohne Pointer). Wenn dann am Ende die Geschwindigkeit nicht zufriedenstellend ist, kann man immer noch den Containertyp wechseln, wenn man alles schön mit typedef gemacht hat.

[314159265358979]

Das hat nichts mit Geschwindigkeit zu tun. Wenn ein vector seine Elemente umkopiert, werden ALLE Zeiger auf die vorherigen Elemente ungültig. Und jede Node hat einen parent-Zeiger im Normalfall. Was ich übersehen habe, ist, dass seine Nodes keinen haben. In diesem Fall könnte er natürlich auch per Value speichern. Mein Fehler.

[Eisflamme]

Aber das spricht ja eher gegen Zeiger, oder? Wenn ich 100 Kinder habe beim vector und den parent-Zeiger nach dem Einfügen eines Elements in den vector setze, hab ich ja quasi verloren.

Deswegen sind Indizes viel besser, aber dann braucht man einen Zeiger auf den vector zusätzlich, was mehr Platz belegt. Aber bei Änderungen darf man alles umschießen, das nervt auch.

Oder wir setzen alle Zeiger, nachdem alle Elemente in den vector eingefügt worden sind bzw. machen am Anfang erstmal ein resize...

Vectors ändern ihr Speicherzeug ja nicht, wenn man nicht ihnen mehr Elemente gibt, richtig? Dann wäre zumindest das kein Problem.

Wie macht man das denn dann gscheit?

[314159265358979]

Man nimmt eine Datenstruktur, bei der die Zeiger/Iteratoren gültig bleiben, wie z.B. ein std::list

[DDler]

Hast du das komplette Projekt und könntest mir das zur Verfügung stellen? Ich hänge an den selben Aufgaben fest und verzweifle

[Eisflamme]

31415926535897932:
Hm, ist es das ggü. der Performance des vector wert? Gefällt mir aber schon Mal.

DDler:
Was brauchst Du? Ich habe weiter oben ja schon einen einfachen Algo für den Wunsch des OP gepostet.

[DDler]

Mich würde interessieren, wie die Methode/Funktion zum Erstellen des Baumes aussieht. Da beiß ich mir gerade die Zähne dran aus. Mir fehlt da auch die Übergabe des Nodes, um an den was dranzubasteln.

Eigentlich müsste man da ja ein "this" verwenden können, aber da sagt die IDE (VS2010 Express), dass das in der statischen Methode nicht gehen soll.

[CStoll]

Warum hast du denn diese Methode auch static definiert? Sowas sollte eine ganz normale (nicht-statische) Methode der Klasse werden.

[DDler]

Hab jetzt das Erzeugen hinbekommen. Laut Aufgabenstellung ist das Erzeugen keine Methode, die in der Klasse Node liegen soll. Allerdings soll jetzt auch noch das ganze Konstrukt (der Baum) ausgegeben werden mit Einrückungen, damit man die Verschachtelung sieht. Kann da jemand helfen?

Hier mal meine tree.h

#include <string>
#include <vector>
#include <sstream>
using namespace std;

class Node
{
	public:
		Node();									//leerer Konstruktor
		Node(string name);						//Konstruktor mit Namen als Parameter
		virtual ~Node();						//virtueller Destruktor
		string get_name();						//Methode - übergibt Namen
		Node* get_child(int);					//Methode - übergibt Kindknoten
		int get_nr_children();					//Methode - übergibt Anzahl Kindknoten
		void set_name(string);					//Methode - setzt neuen Namen
		void add_child(Node*);					//Methode - fügt neuen Kindknoten an Elternknoten
	private:
		string m_name;							//Member - speichert Knotennamen
		vector<Node*> m_childs;					//Member - Liste der Kindknoten
		static int node_id;						//Member - Anzahl erzeugter Knoten
		static int output_tabs;					//Member - Anzahl Einrückungen bei Ausgabe
};	

extern Node &create_complete_tree(int, int);	//kompletten Baum erstellen
extern string show_complete_tree(Node);			//kompletten Baum darstellen

Und dann folglich mal noch das Erzeugen, damit man sieht, wie das gelöst wurde:

/*
	Funktion
		Erstellen eines kompletten Baumes
*/
Node &create_complete_tree(int nr_child_nodes, int tree_depth) 
{ 
	//Knoten erzeugen  
	Node *root = new Node();  
	//Kinder erzeugen und der Elternknoten knüpfen  
	if (tree_depth > 1)  
	{
		for (int i = 0; i < nr_child_nodes; i++) 
		{
			root->add_child(&create_complete_tree(nr_child_nodes, tree_depth - 1)); 
		}
	}
	return *root; 
}

Hier wäre dann die Ausgabe, da hänge ich allerdings gerade:

/*
	Funktion
		Darstellen eines kompletten Baumes
*/

string show_complete_tree(Node node)
{
	string str;
	for(int i=0; i < node.get_nr_children(); i++)
	{
		show_complete_tree(*node.get_child(i));
	}

	return node.get_name();
}

[CStoll]

Wenn du etwas ausgeben willst, solltest du dir mal die Stream-Klassen ansehen (wobei hier schon cout ausreicht). Und ich würde den Einrückungs-Level nicht als statisches Element verwenden, sondern als Parameter weiterreichen:

void show_tree(const node& root, int level=0)
{
  if(level>0) cout<<setw(level)<<' ';
  cout<<root.getname()<<endl;
  for(int i=0;i<root.get_nr_children();++i)
    show_tree(*(root.get_child(i)),level+1));
}

Außerdem solltest du ein wenig über const-correctness nachlesen.