3. Eleganter Baum-Entwurf

Eleganter Baum-Entwurf

  • S

    Hallo!

    Ich habe ein kleines Problem. Ich möchte eine Baumstruktur erstellen.
    Diese ergibt sich aus meinen Objekten: ein A hat mehrere Bs, ein B hat
    mehrere Cs. Im Prinzip, wäre es sinnvoll, wenn man einfach Zeigerarrays
    auf die verbundenen Objekte anlegt (A hat ein B-Array usw.).
    Nun möchte ich aber in dem entstehenden Baum ein wenig rumforsten und
    traversieren, kopieren, umhängen...
    Da fehlt ein Elternzeiger - also rein damit: B zeig jetzt auch auf den
    Elternknoten A. Leider heißen die Funktionen in jeder Ebene anders: B hat
    ein A *getA() und ein C *getC(int i). Also habe ich mir gedacht, leite ich
    alle baumfähigen Klassen von TreeNode ab, damit ich einheitlich mit
    getParent() und mit getChild(int i) sprechen kann. Diese verweisen
    lediglich auf die "Original-Funktionen".
    Was mich etwas stört, ist, daß getParent() und getChild() immer "typlos"
    daherkommen, und ich im Zweifelsfall erst ein A,B,C zurechtcasten muß.

    So richtig glücklich bin ich damit noch nicht. Ich möchte diese Typlosigkeit
    besser verbergen. Kann mir vielleicht ein Iterator weiterhelfen?
    Der untenstehende Code ist nur so als Skizze gedacht. Das werden dann
    später sicher dynamische Arrays mit Smart-Pointern und Klasseninformationen
    (evtl. QT,Boost oder sowas). Die Bäume sollen serialisiert werden usw.

    Ich wäre für Verbesserungsvorschläge/Kritik sehr dankbar.

    Viele Grüße,
    Ulf

    class TreeNode // Basisklasse von A,B und C
{
public:
	virtual TreeNode *getParent() = 0;          // wird durch 
	virtual TreeNode *getChild(int index) = 0;  // Zeiger auf Papa
};

class A : public TreeNode  // "Wurzel"
{
public:
	B *getB(int index) { return b_vector[index]; }
	TreeNode *getParent() { return NULL; }		// NULL, weil Wurzel
	TreeNode *getChild(int index) { return getB(index); } // weiterleiten
protected:
	vector<B*> b_vector; // children
};

class B : public TreeNode // "mittlere Ebene"
{
public:
	A *getA() { return a; } // parent
	C *getC(int index) { return c_vector[index]; } // children
	TreeNode *getParent() { return getA(); }			  // weiterleiten
	TreeNode *getChild(int index) { return getC(index); } // weiterleiten
protected:
	A* a;				 // parent
	vector<C*> c_vector; // children
};

class C : public TreeNode  // "Blätter"
{
	B *getB() { return b; } // parent
	TreeNode *getParent() { return getB(); }	 // weiterleiten
	TreeNode *getChild(int index) { return NULL; } // NULL, weil Blatt
protected:
	B* b; // parent
};
    0
  • C

    So eine gemeinsame Basisklasse ist nur dann wirklich zu gebrauchen, wenn du die Objekte (Wurzel, Äste, Blätter) gleichartig behandeln willst - willst du das? Bei deiner dreischichtigen Struktur ist es wahrscheinlich sicherer, doch diekt mit den spezifischen Get.-Methoden zu arbeiten.

    alternativ würde mir noch ein Einsatz mit Templates einfallen:

    template<typename p,typename c> class node
{
public:
  virtual p* getParent() = 0;
  virtual c* getChild(int) = 0;
};

class A;
class B;
class C;

class A : public node<void,B>
{
public:
  void* getParant() {return 0;}
  B* getChild(int i) {return m_bs[i];}
private:
  vector<B*> m_bs;
};

class B : public node<A,C>
{...};

class C : public node<B,void>
{...};

    (Achtung: ungetestet)

    0
  • T

    warum unterscheidest du die blätter im voraus in wurzel, knoten und blatt? was ist, wenn sich der baum ändert, dann müsstest du die entsprechenden elemente umbauen.

    für nen baum reicht im grunde eine sehr einfache struktur

    template<typename Type>
class Node
{
private:
 Type payload;
 Node *parent;
 std::vector<Node*> children;
public:
 // getter & setter
}

    die wurzel definiert sich dadurch, dass sie keinen parent hat, die blätter durch nicht vorhandene kinder.

    0
  • S

    Das habe ich vielleicht etwas unglücklich dargestellt.

    Der Baum im Beispiel hat nur drei Ebenen (Wurzel,"Äste",Blätter).
    Im Prinzip darf der Baum beliebig viele Ebenen haben, auf jeder Ebene
    ist dann aber genau ein Typ.
    Es geht auch nicht um genau einen Baum. Es soll verschiedene Bäume
    mit dem gleichen Aufbau geben (1 Elternteil, viele Kinder).
    Leider gehen Templates nicht, da eben auf jeder Ebene ein anderer
    Typ vorhanden ist.
    Ein "namentliches" Ansprechen mit getA() scheitert an der Beliebigkeit
    der Bäume. Das muß bei allen Bäumen dieser Art etwa gleich gehen, damit
    man auf so einem Baum dann Standardfunktionen (einfügen, kopieren)
    definieren kann.
    Die Idee von thordk hatte ich auch schon: eine Art Container, der pro
    Knoten einen Verweis/Zeiger auf das eigentliche Datenobjekt beinhaltet.
    Da fand ich es günstiger, wenn A tatsächlich Zeiger auf B hat und nicht
    die Baumstruktur nur in den Nodes ist, die ihrerseits auf A und B zeigen.

    Daher mein Entwurf...

    0
  • S

    Hallo,

    das mit den Templates klingt interessant.
    Aber folgendes dürfte z.B. für eine Funktion getRoot() nicht gehen:

    while(ptr!=NULL) ptr=ptr->getParent();

    ... dafür brauche ich die Gleichmacherei zur Baumverwaltung (oder?).
    Für die Datenverwaltung hätte ich lieber die Typsicherheit.

    Daher kam ja meine Idee mit dem Iterator. Der darf gleichmachen und
    rumforsten. Der Benutzer braucht/darf das nicht. Aber ich weiß nicht,
    ob das geht...

    Gruß,
    Ulf

    0
Anmelden zum Antworten