Albero Binario: funzione che aggiunge un nodo

[_Achille]

Salve ragazzi.
Sto implementando una struttura ad albero binario in C++. Ho creato una classe Nodo che permette di gestire manulamente il valore, il nodo sinistro e il nodo destro.

Spoiler

namespace btree
{
    template <class T = int>
    class BinaryNode
    {
        friend std::ostream& operator<<(std::ostream& output, BinaryNode<T>& node);
        friend std::ostream& operator<<(std::ostream& output, BinaryNode<T>* node);

    public:
        constexpr BinaryNode(T v) noexcept
            : value(v),
            left(nullptr),
            right(nullptr),
            position(1),
            copyof_left(left),
            copyof_right(right)
        { }
        constexpr BinaryNode() noexcept
            : BinaryNode(0)
        { }
        ~BinaryNode();

        T& Value() noexcept;
        const T& Value() const noexcept;

        BinaryNode<T>* & Left() noexcept;
        const BinaryNode<T>* const& Left() const noexcept;
        BinaryNode<T>* & Right() noexcept;
        const BinaryNode<T>* const& Right() const noexcept;

    private:
        T value;
        BinaryNode<T>* left;
        BinaryNode<T>* right;

        unsigned position;
        BinaryNode<T>* copyof_left;
        BinaryNode<T>* copyof_right;
        void set_position() noexcept;
        }
    };
}

Quindi ora voglio creare una classe BinaryTree che semplifichi la gestione dei nodi con una funzione Insert, la cui firma è questa

template <class ...Instructions> void Insert(const BinaryNode<T>* node, bool arg, Instructions ...args)

Praticamente tramite una enumerazione globale si hanno Left e Right che fungono da istruzioni e valgono rispettivamente false e true.
Ad esempio chiamando Insert(new BinaryNode<int>(5), Left, Right); setto in nodo destro del nodo sinistro a partire dalla testa. Il problema è che non so utilizzare il variadic template per risolvere il problema. Sono quasi sicuro che servirà la ricorsione e che molto probabilmente il tipo di ritorno void diverrà BinaryNode<T>* const &...

Qualcuno sa darmi una mano? :thanks:

 

[DispatchCode]

Normalmente l'aggiunta di un nodo torna true/false. Ti basterebbe scorrere l'intero albero ed aggiungere il nodo con il criterio che stai utilizzando. Non ho ben capito che intendi "setto un nodo destro nel nodo sinistro"... forse intendevi che prendi sempre i figli di sinistra ed all'ultimo posizioni il nuovo sulla destra?
Comunque al di là di questo, normalmente la procedura è ricorsiva: si fa un controllo per sapere se il puntatore è nullo, e se lo è viene aggiunto qui il Nodo; in caso contrario ai raggiunge la posizione libera/desiderata.

 

[_Achille]

Normalmente l'aggiunta di un nodo torna true/false. Ti basterebbe scorrere l'intero albero ed aggiungere il nodo con il criterio che stai utilizzando. Non ho ben capito che intendi "setto un nodo destro nel nodo sinistro"... forse intendevi che prendi sempre i figli di sinistra ed all'ultimo posizioni il nuovo sulla destra?
Comunque al di là di questo, normalmente la procedura è ricorsiva: si fa un controllo per sapere se il puntatore è nullo, e se lo è viene aggiunto qui il Nodo; in caso contrario ai raggiunge la posizione libera/desiderata.

Ciao Dispatch.
Praticamente la funzione semplifica l’inserimento di figli.
Un insieme di chiamate:

BinaryTree<int> tree;
...
tree.Head()->Left()->Left()->Right() = new BinaryNode<int>(5);
//assumendo che i due Left siano diversi da nullptr

Diventerebbe

BinaryTree<int> tree;
...
tree.Insert(new BinaryNode<int>(5), Left, Left, Right);

Left e Right sono due enumerazioni che valgono 0 e 1.
La funzione accetta illimitati Left e Right a patto che ve ne sia almeno uno (quindi non si può aggiungere/rimpiazzare la testa). Per quello ha firma bool Insert(..., bool arg, Instructions ...args). Chiamate del tipo tree.Insert(new BinaryNode<int>()) non hanno quindi senso
--- i due messaggi sono stati uniti ---
Ho creato una funzione GetNode

template <class ...Instructions>
BinaryNode<T>* &GetNode(BinaryNode<T>* node, bool arg, Instructions ...args)
{
    if constexpr (0 == sizeof...(args))
    {
        if (arg == Left)
            return node->Left();
        else
            return node->Right();
    }
    else
    {
        if (arg == Left)
            return GetNode(node->Left(), args...);
        else
            return GetNode(node->Right(), args...);
    }
}

Poi viene chiamata da Insert

template <class ...Instructions>
bool Insert(BinaryNode<T>* node, bool arg, Instructions ...args)
{
    GetNode(head.get(), arg, args...) = node;
}

Però non so come ritornare un valore booleano... Ad esempio se GetNode trova un nodo nullptrp dovrebbe ritornare false.

 

[DispatchCode]

Purtroppo non sono da pc, li se non erro ho un sorgente in C di qualche tempo fa, che potrebbe ispirati.
Secondo me dovresti rivedere un po' i compiti che svolgono le tue funzioni.

Questo è un grafo, lo premetto, ed è in Java (non appena sarò al mio pc cercherò l'altro sorgente). Ma come logica dovresti svolgere operazioni di questo tipo:

https://github.com/DispatchCode/GraphSearchSimulation/blob/master/Graph.java

La insert dovrebbe occuparsi dell'inserimento, e non la GetNode().

 

[_Achille]

Purtroppo non sono da pc, li se non erro ho un sorgente in C di qualche tempo fa, che potrebbe ispirati.
Secondo me dovresti rivedere un po' i compiti che svolgono le tue funzioni.

Questo è un grafo, lo premetto, ed è in Java (non appena sarò al mio pc cercherò l'altro sorgente). Ma come logica dovresti svolgere operazioni di questo tipo:

https://github.com/DispatchCode/GraphSearchSimulation/blob/master/Graph.java

La insert dovrebbe occuparsi dell'inserimento, e non la GetNode().

Eh infatti è Insert che inserisce il nodo, GetNode trova il nodo a partire dalle istruzioni (Right e Left).
Ovviamente cambierò il nome a GetNode() visto che ha un nome da metodo pubblico