Baumstruktur in C++ < C/C++ < Programmiersprachen < Praxis < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:16 Fr 22.05.2009 | | Autor: | Wimme |
Hallo!
Die Frage ist etwas peinlich, aber irgendwie bin ich völlig raus aus dem Thema. Also ich möchte eine Baumstruktur in C++ schreiben. Ein Knoten kann dabei theoretisch zieeemlich viele Nachfolgeknoten haben, aber typischerweise werden es wohl ca. 30 sein.
Wie macht man sowas am Besten?
Ich denke mal, ich muss ein struct ELEMENT für ein Knotenelement anlegen. Da schreib ich rein, was son Knoten alles speichern muss.
Dann schreib ich eine Klasse namens "NODE" oder so, und dort kommt dann rein
class NODE {
ELEMENT Data;
list<ELEMENT> nachfolger;
}
Brauch ich dann überhaupt noch eine Klasse TREE?
Oder ich mache halt eine Klasse NODE wo reinkommt, was ein Knoten speichert und die Liste der Nachfolger und eine Klasse TREE, die einfach nur die Wurzel macht und Funktionen bereitstellt.
Ist es klug, die Nachfolger mit der Library list zu speichern? Oder wie macht man das schön und effizient?
Herzlichen Dank,
Wimme
PS. Ein Link zu einem Tutorial wo eine Baumstruktur mit beliebig vielen Nachfolgern implementiert, wär auch klasse!
Die Struktur soll möglichst einfach zu bedienen sein, aber fast noch wichtiger ist Effizienz.
|
|
| |
|
Also ich mache sowas immer mit einem Zeiger auf - falls vorhanden - ein "Elternelement".
Ob Du das in ein struct oder class einbaust, ist wurscht.
Beispiel:
class cElement
{
public:
cElement * parent;
cElement();
~cElement();
};
Jetzt kann ich in parent die Adresse des in der Hierarchie darüberstehenden cElement speichern. Der "ganz oben stehende" Knoten erhält als parent NULL.
Und somit kann ich mich beliebig nach oben "durchhangeln".
Ist das in etwa das, was Du haben möchtest?
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:52 Fr 22.05.2009 | | Autor: | Wimme |
Hallo!
Aber dann kann ich mich doch eben nur nach oben durchhangeln, ich müsste aber wohl auch und vor allem im Baum absteigen können. Das hieße doch ich muss mir irgendwie die Kinder merken.
|
|
|
| |
|
Du musst ja Deine einzelnen Elemente sowieso irgendwo speichern... Am einfachsten wahrscheinlich in einem Zeigerarray.
Wenn ich nun ein Element habe, und will dessen "Kinder" wissen, dann gehe ich das Array durch und vergleiche den Wert parent mit der Adresse des Elements. Dieser Vergleich ist auch bei großen Arrays für den Rechner kein Aufwand und geht daher rasend schnell.
Eine grundsätzlich andere Herangehensweise wäre es, wenn Du Dir in der Klasse ein dynamisches Array baust, in das Du mit entsprechenden set/get-Methoden die Kinder eintragen kannst. Das mag intuitiver sein, ist aber bei großen Datenmengen sicherlich nicht so flott, weil bei jeder Veränderung der Arraygröße im Speicher hin- und herkopiert werden muss. - Hm... O.K. schnellschuss, denn das muss man auch bei einem einzigen großen dynamischen Array 
Ich denke beide Vorgehensweisen haben ihren Vor- und Nachteil.
|
|
|
|
