Basis eines Trees

Lacht bitte nicht, aber ich hab noch nie sowas wie nen Tree gebraucht.
Jetzt steh ich hier ein wenig verlassen und weiss nicht wie ich es beginnen soll :D.
Okay, der Baum hat einen Stamm und Äste und am Ende die Blätter.
Ast wäre jetzt bei mir einfach die Klasse Node.
Nur wenn ich sowas mache:

class Quadnode
{
public:
    Quadnode()
    {
        m_nodes = new Quadnode*[4];
        m_nodes[0] = new Quadnode();
        m_nodes[1] = new Quadnode();
        m_nodes[2] = new Quadnode();
        m_nodes[3] = new Quadnode();
    }

    inline Quadnode* operator[](int index)
    {
        return m_nodes[index];
    }

protected:
   Quadnode** m_nodes;
};

Okay, dann hab ich logischerweise irgendwann einen Stack Overflow.
Wie begrenze ich das ganze sinnvoll?
Was ich will ist ein QuadTree mit insgesamt 32 Unterteilungen. Ich denke das ist genug.
Also 8 Äste mit je 4 Blättern.
Das oberste Element ist der ganze Bildschirm, dessen Äste sollen dann den Bildschirm immer weiter aufteilen.
Ich renn hier irgendwie dauernd gegen eine Wand, ich seh den Ansatz nicht.

drakon

Stackoverflows sind natürlich ein mögliches Problem bei solchen rekursiven Strukturen, aber häufig nicht wirklich, weil die Höhe ja lediglich logarithmisch wächst, was nicht sehr schnell ist.

Dass, was du da baust ist prinzipiell ein Quadtree. Wenn du das bei google suchst findest du so einige Implementierungen davon.

Google hat leider bisher nichts wirklich brauchbares ergeben. Meistens nur Fragen zu speziellen Teilen mit aus dem Zusammenhang gerissenen Snippets.
Und nein, ich meine nicht etwas für den Guttenberg Pattern, sondern einfach ein Tutorial Richtung reiner Quadtree ohne Terraindaten dabei etc. Die meisten die man findet werden gleich auf Terraindaten spezialisiert. Mir fehlt hier aber der Ansatz für C++. Leider. War mit Pointern noch nie besonders gut.

hustbaer

Du darfst die Kind-Knoten nicht im Konstruktor anlegen, sondern erst bei Bedarf erzeugen.
So kannst du auch die Tiefe begrenzen.

BTW: Ein Array von 4 Zeigern dynamisch anzulegen halte ich für sinnlos.

Du könntest dem Knoten eine Höhe im Konstruktor mitgeben. Den Kindern übergibst du dann Höhe-1. Bei 0 ist ein Blatt erreicht.

Michael E.

manni66 schrieb:

Du könntest dem Knoten eine Höhe im Konstruktor mitgeben. Den Kindern übergibst du dann Höhe-1. Bei 0 ist ein Blatt erreicht.

Man könnte auch die Kinder zählen, wenn es nur um die Entscheidung geht, ob es ein Blatt ist

Michael E. schrieb:

manni66 schrieb:

Du könntest dem Knoten eine Höhe im Konstruktor mitgeben. Den Kindern übergibst du dann Höhe-1. Bei 0 ist ein Blatt erreicht.

Man könnte auch die Kinder zählen, wenn es nur um die Entscheidung geht, ob es ein Blatt ist

Während man den Baum gerade aufbaut? Das möchte ich sehen

Michael E.

manni66 schrieb:

Michael E. schrieb:

Man könnte auch die Kinder zählen, wenn es nur um die Entscheidung geht, ob es ein Blatt ist

Während man den Baum gerade aufbaut? Das möchte ich sehen

Tut mir Leid, ich verstehe deine Frage nicht.

Eisflamme

Hi,

Wie schon gesagt. Du legst bei einem Baum die Strukturen nicht an, um sie später zu nutzen, sondern Du legst sie an, sobald Du sie nutzt.

Je nachdem, was in den Baum reinsoll, erzeugst Du alles halt im ctor, z.B. im ctor.

Hast Du beispielsweise einen Binärbaum für mathematische Operationen, so übergibst Du dem ctor einen string. Der ctor verarbeitet diesen und bildet daraus zwei Teilstrings und erstellt darauf basierend die zwei Unterknoten. 2+3+4+3 wird dann z.B. zu 2+3 und 4+3. Und die Wurzel hält dann den op+. Mit Polymorphie für verschiedene Operatoren erzeugt man den Baum dann halt als freie Funktion oder lässt den Wurzelknoten nur als Dummy da stehen.

Wenn Du mehr als ein Kind hast, solltest Du das entweder fixieren oder über vector machen, ich würde nie eine **-Variante verwenden.