[c++]Bibliothek mit Baumstruktur erstellen

[Z!ppo]

Hallo Leute,
ich muss bis Sonntag für die Uni ein eigentlich einfaches c++ Terminal Programm schreiben. Ich bin erst im zweiten Semester und kenne mich zwar mit der c-Syntax und Algorithmen aus, aber ich verzweifle grad an der ganzen OOP Sache

Die Aufgabe ist folgende:

- drei Dateien (tree.h, tree.cxx und main.cxx) erstellen.
- Es soll eine Baumstruktur erstellt werden mit einem Objekt namens "node"
- die Memberfunktionen sind :

• Konstruktor
• Destruktor
• get_name() const
• set_name(new_name)
• get_nr_children() const
• get_child(i) const
• add_child(node)

die genaue Aufgabe ist

1 Praxis
1.1 Bibliothek mit Baumdatenstruktur (5 Pt)

1.1.1 Grundgerüst der Baumdatenstruktur (2 Pt)

Erstellen Sie zwei neue Dateien tree.h und tree.cxx und implementieren Sie
eine Baumdatenstruktur wie folgt.
Die Knotenklasse node soll einen Namen vom Typ std::string speichern
können und folgende Methoden bereitstellen (Typen der Argumente und Rückgabewerte
sind bewusst weggelassen und müssen erschlossen werden)

• Konstruktor mit einem Argument vom Typ const std::string&, das den
  Knotenname initialisiert
• Destruktor zum Löschen aller Kindknoten mit dem delete-Operator. Deklarieren
  Sie den Destruktor als virtuelle Methode.
• get_name() const ... gibt den Namen des Knotens zurück
• set_name(new_name) ... setzt den Namen des Knotens auf einen neuen
  Namen
• get_nr_children() const ... gibt die Anzahl der Kindknoten an
• get_child(i) const ... gibt einen Zeiger auf den i-ten Kindknoten zurück
• add_child(node) ... fügt am Ende einen neuen Kindnoten hinzu

Nutzen Sie zum Speichern der Kindknotenzeiger die Template Klasse std::vector
der Standard Template Library, die im Header <vector> deklariert ist.

1.1.2 Programmstruktur (2 Pt)

Erstellen Sie eine dritte Datei main.cxx. Binden Sie tree.h mit einem entsprechenden
#include-Befehl ein

• Implementieren Sie eine main-Funktion, die einen Baum mit einem Wurzelknoten
  namens "root" und zwei Kindern namens "left child" und
  "right child" erzeugt und danach den ganzen Baum mit dem delete-
  Operator angewendet auf den Wurzelknoten wieder löscht.
• Erstellen Sie zwei Visual Studio Projekte - ein Projekt namens tree, das
  aus tree.cxx eine statische Bibliothek erzeugt und ein Projekt namens
  tree_test, das aus main.cxx eine Anwendung erstellt. Setzen Sie in der
  Solution das Projekt tree_test als abhängig vom Projekt tree.

meine tree.h:

#include <iostream>
#include <string>
#include <vector>

Class node
{
	private:
	string name;		//name des Knotens
	int nr_children;
	vector<int> vec;
	
	public:
	node(void){const std::string& name;};     //constructor
	virtual ~node(void);                 //destructor
		
	//=======GET=========//
	
	//liest den Namen aus
	get_name(){								
		return name;
	};
	
	//gibt die Nummer der Kindknoten aus
	get_nr_children(){		
				
	};
	
	//gibt die Nummer 
	get_child(i);
	// =======SET========//
	set_name(new_name){
		name = new_name;
	};
	
	add_child(node){};
};

die tree.cxx:
also so wie ich das mitbekommen habe wird die Datei dann automatisch vom Visual Studio erstellt. Das ist aber gerade noch am downloaden, deswegen hab ich mich mal selbst dran probiert ^^

#include "tree.h"

node::node(void){}

node::virtual ~node(void){}

und die main.cxx:

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


int main(){
	root = new node("root");
	left_child = new node("left");
	right_child = new node("right");
	
	
	
	return 0;
}

Ich habe echt keine Ahnung wo ich anfangen soll und das Gefühl dass ich irgendwas grundlegendes falsch mache. Mir gehts jetzt eigentlich nur darum, die Nodes erstellen zu können und den Namen zu speichern, auszugeben und die Kindknotenanzahl anzuzeigen. Und natürlich die Knoten wieder löschen zu können.

Ich weis, das ist ziemlich viel stuff, aber wäre echt cool wenn sich jemand die Mühe machen würde und mal alles durchsehen würde

Ich will auch nich unbedingt den genauen Code wissen, nur rein logisch betrachtet, was ich machen muss und wie ich die Memberfunktionen richtig einsetze. Und vor allem wie ich das mit dem Vektor als Relation für die Knoten richtig hinbekomme.

[xNopex]

Erstmal rein von der Theorie:

In die Headerdatei (*.h) kommen nur deklarationen rein, d.h. Methodenköpfe, Variablendeklarationen, Klassendeklarationen, etc. Die Rümpfe der Methoden programmierst du in der *.cpp Datei:

tree.h:

#include <string>
#include <vector>

class node
{
	private:
	    std::string name;
	    std::vector<node*> children;
	public:
	    node(const std::string& new_name);     //constructor
	    virtual ~node(void);                 //destructor
	
	    std::string get_name();
	    unsigned int get_nr_children();
	    node* get_child(unsigned int i);
	    void set_name(std::string new_name);
	    void add_child(node* new_node);
};

tree.cpp:

#include "tree.h"

node::node(const std::string& new_name)
{
    this->name = new_name;
}

node::~node()
{
    for(unsigned int i = 0; i < this->children.size(); i++)
        delete(this->children.at(i));
}

std::string node::get_name()
{
    return this->name;
}

void node::set_name(std::string new_name)
{
    this->name = new_name;
}

unsigned int node::get_nr_children()
{
    return this->children.size();
}

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

void node::add_child(node* new_node)
{
    this->children.push_back(new_node);
}

main.cpp:

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

using namespace std;

int main()
{
    node* root = new node("root");
    root->add_child(new node("left child"));
    root->add_child(new node("right child"));
    delete root;
    return 0;
}

Code ohne Gewähr auf vollständigkeit und Richtigkeit. Schaus dir gut an, frag nach, sonst kannst du dir dein Studium knicken. Sind halt echte Basics.

[Z!ppo]

Ahhh nice, langsam versteh ich das.
Danke vielmals, dein Code ist erstmal sehr verständlich für mich

Ich hab die Idee, den Vektor dreidimensional zu machen, der dann die Zeiger auf den Parent-Node und die 2 Child-Nodes speichert.

Originally Posted by xNopex

Schaus dir gut an, frag nach, sonst kannst du dir dein Studium knicken. Sind halt echte Basics.

Hab ich mir in letzter Zeit auch gedacht. Hab bis jetzt viel verpennt im Studium und wenn ich mir die c++ Beispiele so angucke die es am Anfang des Semesters gab und die ich alle schon drauf haben müsste merke ich dass ich echt noch ne menge zu büffeln hab ... nix mit Party und Chilln - so wie ich es das erste Semester gemacht hab ^^

[xNopex]

Ich hab die Idee, den Vektor dreidimensional zu machen, der dann die Zeiger auf den Parent-Node und die 2 Child-Nodes speichert.

Nicht sehr sinnvoll. Dann lieber drei verschiedene Attribute einrichten. Aber das geht ein bisschen am Ziel der Datenstruktur vorbei. Der Baum unterscheidet nicht nach "left-child" und "right-child", das ist dem pups-egal. Er durchläuft später einfach rekursiv alles mal.
Beim geordneten Bin-Baum sieht das schon anders aus.

[Z!ppo]

Aber eine Baumstruktur heißt doch, dass z.B. das erste "Left_Child" auch wieder ein left und right child haben kann.

                    root _ node
                   /              \
         left_c                     right_c
        /       \                  /        \
left_c         right_c       left_c           right_c

Wenn ich jetzt was mit den Nodes anstellen will brauch ich ja auch noch die Zeiger für jeden Node auf die (max 2) child Nodes und auf den root Node. was ja eher auf eine (3 * n)-Matrix hinauslaufen würde ...

Wenn ich die child Nodes einfach an den Vektor anfüge ergibt sich doch eigentlich nur eine Folge von Nodes, also:

root -> left_c -> right_c -> left_c -> right_c ..... usw


Und übrigens funktioniert dein Code super, kein Fehler

[xNopex]

Das, was du hier aufgezeichnet hast, ist eben ein Spezialfall. Ein Binärbaum. Ein Baum kann aber allgemein auch so aussehen:

                    root _ node
                   /              \
         left_c                     right_c
        /   |       \                 /           \
left_c  middle_c right_c      left_c      right_c

Ein Knoten braucht dabei immer nur die Referenz auf seine Nachfolger, was in der Klasse durch den Vektor realisiert wird. Da du nicht zwischen den einzelnen Knoten unterscheiden musst, langt es, dass du einfach alle Nachfolger eines Knoten in den Vektor steckst.
Wenn du etwas mit den Knoten anstellen willst, läufst du solange alle Knoten durch (Stichwort Rekursion) bist du an dem Knoten angelangt bist, mit dem du was machen willst (Überprüfung über Name).

Beispiel: Sagen wir du hast 6Knoten und einen Root-Knoten:

                    root _ node
                   /              \
            A                          B
        /       \                  /        \
      C         D                E           F

root_node hat nur jeweils eine Referenz auf A und B. A jeweils eine Referenz auf C und D und B auf E und F. Die Zeiger zu den Nachfolgern sind jeweils in den Vektoren der Knoten gespeichert. Sagen wir du willst bei Knoten B eine weitere Referenz auf einen neuen Knoten G einfügen. Dafür müssen wir eine neue Funktion einfügen:

bool node::insert_node_at(std::string node, node* new_node)
{
     if(this->name == node)
     {
           this->add_child(new_node);
           return true;
     }

     for( unsigned int i = 0; i < this->children.size(); i++ )
     {
           if(this->children.at(i)->insert_node_at(node, new_node))
               return true;
     }

     return false;
}

Aufgerufen wird sie nun so:

int main()
{
     //Zuvor wurde der Baum erstellt
     if(root_node->insert_node_at("B", new node("G"));
        cout << "Knoten wurde erfolgreich eingefügt";
     else
        cout << "Knoten konnte nicht eingefügt werden";
}

Du siehst, mithilfe rekursiver Funktionen, genügt es bei solchen Datenstrukturen, wenn man seinen Nachfolger kennt. Das verhält sich genauso bei Listen, BinBäumen, Stapeln, Graphen, etc.

EDIT: Code wieder ohne Gewähr auf Vollständigkeit und Richtigkeit
EDIT2: Rein aus Interesse, wo und was genau studierst du?

[Z!ppo]

Puh, also ich denke ich habs nu verstanden ^^
Das Problem war dass ich gar nich dran gedacht hab dass ja für jeden Knoten ein neues Objekt erstellt wird, was dann wieder nen eigenen Vektor hat, wie du ja gerade sehr schön erklärt hast
Langsam hab ichs glaub ich im Kopf

Originally Posted by xNopex

Rein aus Interesse, wo und was genau studierst du?

Ich studiere Bachelor Medieninformaik in Dresden (TU). Wollt eigentlich (weil das bis nun im 2. Semester noch ohne Probleme geht) auf reine Informatik umsteigen, weil ich mir die ganzen Programmiergeschichten eigentlich ziemlich geil vorstelle wenn mans drauf hat ^^ und genau da liegt das Problem