Bäume

Habe gerade mit der Implementierung des Binären Suchbaums begonnen. Nun stellt sich mir aber eine Designfrage.

Folgendes, die Grundstruktur sind im wesentlichen so aus:

template<typename T>
class BinaryTree
{
    private:
                    struct Node
                    {
                        T data;
                        Node *parent, *left, *right;

                        Node(const T& data, Node *p, Node *l, Node *r) 
                             : data(data), parent(p), left(l), right(r) {}
                    };

                    Node root;

    public:
                    BinaryTree(const T& data) : root(data,0,0,0) {}

                    template<typename S>
                    static void preOrder(S& os, Node *n)
                    {
                        os << n->data;
                        if(n->left  != 0) preOrder(os, n->left);
                        if(n->right != 0) preOrder(os, n->right);
                    }
};

preOrder ist dazu da um den Baum in einer bestimmten Weise zu durchlaufen. Nun kann der Client preOrder einen Knoten übergeben, ab dem der Durchlauf beginnen soll. Es sollte aber doch besser so sein, dass man preOrder einen Baum übergibt und hier stellt sich mir die Frage, wie ich den Baum aufbauen soll.

Es gibt zwei Möglichkeiten:
1. So wie sie ist, also ein Baum mit lauter Knoten
2. Man kann den Baum ja auch so betrachten, dass jeder Knoten wiederum einen Baum darstellt. Dann würde mein Baum nicht aus lauter Knoten bestehen, sondern aus lauter Teilbäumen.

Dies würde die Struktur bissl ändern und so könnte ich preOrder auch einen (Teil)Baum entgegennehmen lassen.

Welche Implementierung ist zu bevorzugen, welche gestaltet die Implementierung schwieriger Bäume einfacher ?

bgdnoy

Du könntest auf Binary Tree verzichten, und nur mehr mit "Nodes" arbeiten.
Also die beiden in eine Klasse vermengen.
Bietet sich imo an, weil Bäume natürlicherweise rekursiv definiert sind.
Da wäre die "Wrapper-Klasse" BinaryTree wahrscheinlich zu viel des Guten.

volkard

bgdnoy schrieb:

Du könntest auf Binary Tree verzichten, und nur mehr mit "Nodes" arbeiten.
Also die beiden in eine Klasse vermengen.

schlechte idee programmiertechnisch.

bgdnoy schrieb:

Bietet sich imo an, weil Bäume natürlicherweise rekursiv definiert sind.

ein baum ist ein zusammenhängender wald. wo ist ddas natürlicherweise rekursiv?

bgdnoy schrieb:

Da wäre die "Wrapper-Klasse" BinaryTree wahrscheinlich zu viel des Guten.

die ist schon gut da.

Node* root; ist wohl feiner als Node root;

Zeus

Der Ctor vom BinaryTree sollte unabhänig von den Daten sein.

volkard schrieb:

Node* root; ist wohl feiner als Node root;

Ich wollte mir somit das erste new Sparen, aber mit dem Pointer könnte ich auch einen leeren Baum haben und da leere Bäume auch möglich sind, werde ich daraus einen Pointer machen.

Zeus schrieb:

Der Ctor vom BinaryTree sollte unabhänig von den Daten sein.

Hmmmm, was spricht dagegen der Wurzel direkt nen Wert zu spendieren?
Da die Liste ja auch nun leer sein kann, könnte ich noch einen weiteren C'tor dafür hinzufügen.

Das einzige was dagegen sprechen würde, ist das es sowas nicht in der STL gibt Aber die STL ist ja auch nicht das Maß aller Dinge.

Zeus

Weil es dann schwer ist sowas zu machen?

template<class Key, class Data>
BinaryTree
{
...
};

BinaryTree<int, BinaryTree<int, node> > cascade_index;

bgdnoy

volkard schrieb:

schlechte idee programmiertechnisch.

Ich glaub's dir mal, aber warum eigentlich?

Einen binären Baum definiere ich als als ein Tupel (2-Tupel) von Dingen,
wobei ein Ding entweder irgendwas unteilbares ist, oder ein wieder ein Baum
(, oder halt das "Nichts-Objekt", wenn man so will).

ein baum ist ein zusammenhängender wald.

<ironic> War das nicht umgekehrt?

volkard

bgdnoy schrieb:

volkard schrieb:

schlechte idee programmiertechnisch.

Ich glaub's dir mal, aber warum eigentlich?

wegen der freiheit.
- die methoden so anzubieten, wie der benutzer es am besten hätte. ohne dran denken zu müssen, daß da was rekursiv ist. beispiel wenn der baum an der wurzel wächst: b=b->insert(17); statt b.insert(17)
- die methoden so zu implementieren, wie du willst. siehe folgenden code.
- die Node-Sachen private halten, kann vor fehlern schützen.

template<typename T> 
class BinaryTree 
{ 
    private: 
                    struct Node 
                    { 
                        T data; 
                        Node *parent, *left, *right; 

                        Node(const T& data, Node *p, Node *l, Node *r) 
                             : data(data), parent(p), left(l), right(r) {} 
                         template<typename S>
                         static void preOrder(S& os, Node *n) 
                         {//hier sehe ich nen rekursiven baum
                             os << n->data; 
                             if(n->left  != 0) preOrder(os, n->left); 
                             if(n->right != 0) preOrder(os, n->right); 
                         } 
                    }; 

                    Node* root; 

    public: 
                    BinaryTree(const T& data) : root(0) {} 
                    template<typename S>
                    void preOrder(S& os)
                    {//mal nur weiterreichen in die rekirsive welt
                       preOrder(os,root);
                    }
                    T const* min()
                    {//hier mag ich mal iterativ bleiben
                       T* result=0;
                       for(Node* p=root;p!=0;p=p->left)
                          result=&p->data;
                       return result;
                    }
};

Zeus schrieb:

Weil es dann schwer ist sowas zu machen?

template<class Key, class Data>
BinaryTree
{
...
};

BinaryTree<int, BinaryTree<int, node> > cascade_index;

BinaryTree<int, string> mm; // fill it ...
BinaryTree<int, BinaryTree<int, string> > dd(3,mm);

?

Ich werde ehe beide Optionen anbieten, insofern sollte dies kein Problem darstellen.

Zum Hauptproblem:
Ich habe preOrder static gemacht und bequem andere Bäume diesem zu übergeben, aber was hat dann preOrder in BinaryTree verloren. Frei Funktion sind dafür viel besser. Daher siehts momentan so aus:

namespace BinaryTree
{
    class BinarySearchTree { };
    class OtherTree { };

    template<typename S>
    void preOrder(S& os, Node *n) { }

    // Other elementary BinaryTree-Functions ...

}

So würde eine Node* dem preOrder auch gut tun, da alle BinaryTree's nach den "Node-Prinzip" aufgebaut sind.

Ist dies vom Design nun besser ?

volkard

template<typename S,typename N>
    void preOrder(S& os, N *n) { }

die ganzen Node-Typen haben ja andere zusatzattribute.

aber da biste erstmal recht frei, und es ist wohl besser, du probierst ein paar variationen aus, als daß du uns hier was glaubst, wir sind uns selber nicht einig und zum großteil stl-verblendet, tendieren zum übermäßogen konsum unpassender abgefreakter sprachmittel, können schnittstellen und funktionsumfang einfach nicht schlank halten, haben angst vor zeigern und werfen zu viele exceptions.

KasF schrieb:

namespace BinaryTree
{
    class BinarySearchTree { };
    class OtherTree { };

    template<typename S>
    void preOrder(S& os, Node *n) { }

    // Other elementary BinaryTree-Functions ...
    
}

Das ist ja auch nicht das Eelbe vom Ei, so muss ich ja nen Node* zb root rausgeben. Momentan siehts so wie bei Volkard aus, ein preOrder private und eins public, das ist imho das beste Design momentan.

Werde aber dennoch versuchen was Container-Iterator-Algorithmen-Ähnliches Konzept zu basteln ...