Rekursive Baumerstellung

Hallo,
ich habe folgende Klasse geschrieben:
tree.h:

#ifndef _TREE_H_
#define _TREE_H_
#include <string> 
#include <vector>

class node {
    private:
        std::string name;
        std::vector<node*> children;
        static int node_id;
    public:
        // Konstruktor
        node(const std::string& new_name = ""); 
        // Destruktor
        virtual ~node();
        // Elementfunktionen
        std::string get_name() const;
        void set_name(const std::string&);
        unsigned int get_nr_children() const;
        node* get_child(unsigned int i) const; 
        void add_child(node*);          
};
extern node* create_complete_tree(unsigned int, unsigned int);
#endif

tree.cxx:

#include "tree.h"
#include <sstream>
#include <iostream>

int node::node_id = 0;

// Konstruktor
node::node(const std::string& new_name) {
    if(new_name == "") {
        node_id++;
        std::stringstream str_sm;
        str_sm << node_id;  
        std::string node_id_str = "node_" + str_sm.str();      
        set_name(node_id_str);
    } else {
        set_name(new_name);
    }
}       
// Destruktor
node::~node() {
    std::cout << "enter ~node of " << "\"" << get_name() << "\"" << std::endl;
    for(unsigned int i = 0; i < children.size(); i++) {
            delete get_child(i);           
    }
    std::cout << "leave ~node of " << "\"" << get_name() << "\"" << std::endl;
}
// Elementfunktionen
std::string node::get_name() const {
    return name;
}

void node::set_name(const std::string& new_name) {
    name = new_name;
}

unsigned int node::get_nr_children() const {
    return children.size();
}

node* node::get_child(unsigned int i) const {
    return children.at(i);
}

void node::add_child(node* child) {
    children.push_back(child);
}

node* create_complete_tree(unsigned int nr_child_nodes,unsigned int tree_depth) {           
    /*for(unsigned int i = 0; i < nr_child_nodes; i++) {
        this->add_child(new node(""));
        if(tree_depth > 0) {
            this->children.at(children.size()-1)->create_complete_tree(nr_child_nodes, (tree_depth-2));
        }    
    }*/ 
}

Nun will ich einen kompletten Baum rekursiv durch eine externe Funktion (create_complete_tree) erstellen lassen, kriege das als solche aber nicht hin. Wenn das eine Elementfunktion wäre, wäre das kein Problem (siehe auskommentierten Teil der Funktion create_complete_tree).
Ein weiteres Problem ist, dass ich notwendigerweise nur die Parameter verwenden darf: nr_child_nodes und tree_depth. Ich weiß nicht wie ich damit eine rekursive Funktion erstellen kann, denn wenn ich einen Zeiger auf einen Knoten als Parameter hätte, wäre das wiederum kein Problem, das würde dann ungefähr so wie bei der Tiefensuche funktionieren (statt zu suchen, fügt man Knoten hinzu).
Ich weiß einfach nicht weiter. Kann mir jemand helfen?

314159265358979

Dein Include-Guard erzeugt undefiniertes Verhalten.

Bei mir kompiliert alles fehlerfrei. Kannst du das genauer beschreiben?

314159265358979

Er entspricht nicht den Regeln für erlaubte Bezeichner.

Wie wäre es dann richtig?

314159265358979

Anders.

pumuckl

arnas schrieb:

Wie wäre es dann richtig?

Pauschal fährst du ganz gut, wenn du führende Unterstriche sowie doppelte Unterstriche grundsätzlich vermeidest. Bezeichner mit doppelten Unterstrichen sind grundsätzlich der Implementierung vorbehalten, Bezeichner mit führenden Unterstrichen unter bestimmten Bedingungen auch.

Bevor jetzt ein Klugscheißer daher kommt, der die Regeln ganz exakt kennt: das ist restriktiver als der Standard, aber es ist leichter zu merken und tut nicht weh.

Ich hasse diese Witzbolde in dem Forum.
Schreibt doch immer gleich RTFM.

Erst passiert mir das mit SeppJ und jetz machts Pi auch net besser...

Für Arnas:

(However, names starting with one or two underscores, such as _GRANDFATHER_H and __GRANDFATHER_H, are reserved to the implementation and must not be used by the user.[1][2])

Einfach führende Unterstriche weglassen.

pumuckl schrieb:

arnas schrieb:

Wie wäre es dann richtig?

Pauschal fährst du ganz gut, wenn du führende Unterstriche sowie doppelte Unterstriche grundsätzlich vermeidest. Bezeichner mit doppelten Unterstrichen sind grundsätzlich der Implementierung vorbehalten, Bezeichner mit führenden Unterstrichen unter bestimmten Bedingungen auch.

Bevor jetzt ein Klugscheißer daher kommt, der die Regeln ganz exakt kennt: das ist restriktiver als der Standard, aber es ist leichter zu merken und tut nicht weh.

Ok, danke. Werde die Include Guards von _TREE_H_ auf TREE_H ändern.

314159265358979

RTFM

Bashar

arnas schrieb:

Ein weiteres Problem ist, dass ich notwendigerweise nur die Parameter verwenden darf: nr_child_nodes und tree_depth. Ich weiß nicht wie ich damit eine rekursive Funktion erstellen kann, denn wenn ich einen Zeiger auf einen Knoten als Parameter hätte, wäre das wiederum kein Problem, das würde dann ungefähr so wie bei der Tiefensuche funktionieren (statt zu suchen, fügt man Knoten hinzu).

Dann mach es mit einer rekursiven Hilfsfunktion, die du von create_complete_tree aus aufrufst.

TyRoXx

Bashar schrieb:

arnas schrieb:

Ein weiteres Problem ist, dass ich notwendigerweise nur die Parameter verwenden darf: nr_child_nodes und tree_depth. Ich weiß nicht wie ich damit eine rekursive Funktion erstellen kann, denn wenn ich einen Zeiger auf einen Knoten als Parameter hätte, wäre das wiederum kein Problem, das würde dann ungefähr so wie bei der Tiefensuche funktionieren (statt zu suchen, fügt man Knoten hinzu).

Dann mach es mit einer rekursiven Hilfsfunktion, die du von create_complete_tree aus aufrufst.

Die Funktion soll den Knoten doch erstellen, nicht als Argument erhalten. Die Lösung ist so einfach, dass ich sie einfach posten muss:

node* create_complete_tree(unsigned int nr_child_nodes, unsigned int tree_depth)
{
	std::auto_ptr<node> result(new node(whatever));
	if (tree_depth)
	{
		for (unsigned i = 0; i < nr_child_nodes; ++i)
		{
			std::auto_ptr<node> child(
				create_complete_tree(nr_child_nodes, tree_depth - 1));

			//weil add_child werfen kann
			result->add_child(child.get());
			child.release();
		}
	}
	return result.release();
}

Ist die Aufgabe so gemeint?
Natürlich sollte die Funktion unique_ptr<node> oder so zurückgeben, aber nichts geht über gute alte Ausnahmefrickelei.

Bashar schrieb:

arnas schrieb:

Ein weiteres Problem ist, dass ich notwendigerweise nur die Parameter verwenden darf: nr_child_nodes und tree_depth. Ich weiß nicht wie ich damit eine rekursive Funktion erstellen kann, denn wenn ich einen Zeiger auf einen Knoten als Parameter hätte, wäre das wiederum kein Problem, das würde dann ungefähr so wie bei der Tiefensuche funktionieren (statt zu suchen, fügt man Knoten hinzu).

Dann mach es mit einer rekursiven Hilfsfunktion, die du von create_complete_tree aus aufrufst.

In meiner Aufgabenstellung heißt es, dass create_complete_tree selbst rekursiv sein soll. So wie ich das verstehe, darf man eben keine solche Hilfsfunktion verwenden... Das ist ja das ganze Problem.

Wenn der Knoten nun mit der Funktion erstellt wurde, kann man diesen doch sicher auch mit einer Überladung des <<-Operators ausgeben. Ich habe das mal versucht, aber ich scheine auf fehlerhafte Speicherbereiche zuzugreifen, da ich nichts brauchbares erhalte.

[cpp]std::ostream& operator<<(std::ostream& s, Node* n)
{
return s << n->get_name();
}[code]

Ausgabe macht sowas wie: 0FA513...

Jemand noch eine Idee, wie man mir da helfen könnte? Suche brachte mir keine Ergebnisse.