Rekursives Erstellen einer Baumstruktur

[Cloppy]

Wieso kommt hier immer kein Eintragsmodus gewählt? Ich kann nichts mehr abschicken was über mehrere Zeilen geht.

[Eisflamme]

Hast du auch ein Codetag benutzt?

Edit: Bei mir gehen mehrere Zeilen.

[Cloppy]

Ja. Die gleiche Fehlermeldung kommt auch, wenn ich einfach nur mehrere Zeilen Text schreibe. Ich versteh ich die Welt nicht mehr.

Edith: Ah jetzt gehts wieder.

Also ich habe eine Nodeklasse und mit der soll ich eine Baumstruktur per rekursive Funktion erstellen.
Allerdings hab ich mit rekursiven Funktionen immernoch so meine Probleme, deswegen fehlt mir der Ansatz.

Das ist die NodeKlasse.

#include <vector>
#include <string>

class node
{
private:
	std::string name;							// name of node
	std::vector<node*> children;				// vector of childnodes
	static int node_id;							// nodeID

public:
	node(std::string nodeName);
	node();
	virtual ~node();

	const std::string*	get_name();				// get name of node
	const node*			get_child(int i);		// get specified child of node

	int		get_nr_children();					// get number of children
	void	set_name(std::string* setName);		// set a new name
	void	add_child(node* newNode);			// add a child
};

extern void create_complete_tree(int nr_child_nodes, int tree_depth);	// create a complete tree

Die Sache ist auch die, dass ich doch eigentlich nen node* firstnode Parameter in der create_complete_tree Funktion bräuchte oder nicht?

Ich hab echt keine Idee.
Ich hoffe, ihr könnt mir einen Anstoß geben.

Edith2: Achso, das ganze soll per DFS enstehen. Also immer zuerst bis ganz runter, dann wieder rauf und wieder runter.

[Eisflamme]

Hi,

Wieso ist deine Erstellungsmethode extern deklariert? Und wie soll deine Baumstruktur aussehen, also welche Daten sollen da überhaupt rein? Oder möchtest Du eine leere Struktur erstellen, die eine fixe Breite und Tiefe hat, aber noch keinen Inhalt? Das könntest Du auch über den ctor machen. Überhaupt gefällt es mir eine Methode im Baum bereitzustellen.

Wieso speicherst Du Zeiger auf subnodes im Vector statt normalen subnodes?

class node
{
// ...
public:
node(int childNodes, int depth); // Dritter ctor, der leeren Baum mit childNodes Kindern und Tiefe depth erstellt
// ...
};

node::node(int childNodes, int depth)
{
    if(depth != 0)
        for(std::size_t n = 0; n < childNodes; ++n)
        {
            node* newNode = new node(childNodes, depth - 1);
            children.push_back(newNode);
        }
}

Sollte auf die Weise auch DFS sein.

Wenn Du das von außerhalb implementierst, musst Du natürlich auch immer den Node mitgeben, auf den sich das bezieht. Da würdest Du am Anfang also den rootNode mitgeben und statt "new node(childNodes, depth - 1)" erst das node erstellen (mit einem deiner anderen zwei ctors) und einfach "createFullTree(newNode, childNodes, depth - 1)" schreiben und für das push_back in den children-vector brauchste dann halt ne Zugriffsmethode auf den node.

Eine weitere Alternative wäre zum Erstellen des Baumes auch eine statische Methode, weil die Zugriff auf die Interna der Klasse hat.

[Cloppy]

Das ist eine Uniaufgabe, mir erschließt sich auf nicht der Sinn, dass ganze extern zu deklarieren.

Rein sollen pro Element im Baum ein Node, der immer auf seine Kinder zeigt, bei der Paramterübergabe (2,4) z.B. wäre es halt ein Binärbaum, dessen Nummern per DFS ermittelt wurde.
Edit: Also ich erstelle den Wurzelknoten und zwei Kinderknoten, dann ruft sich die Funktion wieder selbst auf, geht zum ersten Kinderknoten und erstellt dort wieder zwei Kinderknoten immer mit add_child().

Das mit dem constructor wäre meiner Ansicht nach auch das sinnvollste, weil man dann direkt den Bezug zum Wurzelknoten hat. Aber was will ich machen. Da kann man ewig diskutieren

Das mit vector<class*> statt vector<class> hab ich irgendwann mal so gelernt. Ich nahm immer an, dass das beim Zugriff und übergeben einfach schneller ist. Oder ist das eher weniger gut, vektoren mit Pointern zu füllen?

Ich denke, ich mach das erstmal per dritten Konstruktor und schau dann, was der Übungsleiter meint. Weil alles andere wäre meiner Meinung nach zu umständlich und auch sinnbefreit, wenn ich die Baumerstellung außerhalb der Klasse lagere.

Danke erstmal für die Hinweisen. Das mit den Pointern in vector würde mich noch interessieren, was du damit meintest.

[Eisflamme]

Na ja, man sollte immer Gründe haben, wenn man Zeiger statt den Objekten selbst nutzt. Wenn man nachher umorganisieren möchte, macht das Sinn. Der Zugriff ist ohne Zeiger theoretisch schneller, auch wenn das keiner merkt. Es kostet nur etwas mehr Zeit bei der Erstellung wegen der Kopien, aber die lassen sich u.U. ja auch durch Move-Semantik verbessern.

Ja und sonst haben Zeiger noch den Vorteil, dass man sie leichter kopieren kann. Wenn Du wegen irgendwas viele Kopien hast, ist es vermutlich besser mit Zeigern zu arbeiten. Auch das Umordnen geht schneller, wenn man irgendwo ein Objekt löscht. Je nach Tiefe des Baumes geht das deutlich besser.

Da es recht wahrscheinlich ist, dass man Mal etwas löscht oder umhängt, ist ein Baum mit Zeigern wohl besser. Wenn man das ausschließen kann, finde ich die Variante ohne Zeiger aber gerade hübscher, auch wenn ich die ebenfalls noch nie gesehen habe. Weiß hier jemand was darüber?

[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.