Albero Binario: funzione che aggiunge un nodo

_Achille

Utente Èlite
3,067
725
CPU
Intel i5-6600K @4.6 GHz
Dissipatore
Cryorig H5
Scheda Madre
ASRock Z170 Extreme 6
HDD
WesternDigital 1TB & Crucial MX200 250GB
RAM
Corsair Ven 16GB DDR4 2133MHz
GPU
Sapphire RX 580 Nitro+
Monitor
Dell S2418H
PSU
RM550X
Case
NZXT S340
Periferiche
Anne Pro 2, Razer Abyssus
OS
Windows 10 Pro
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.
C++:
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
C++:
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:
 
Ultima modifica:

DispatchCode

Moderatore
Staff Forum
Utente Èlite
2,210
1,846
CPU
Intel I9-10900KF 3.75GHz 10x 125W
Dissipatore
Gigabyte Aorus Waterforce X360 ARGB
Scheda Madre
Asus 1200 TUF Z590-Plus Gaming ATX DDR4
HDD
1TB NVMe PCI 3.0 x4, 1TB 7200rpm 64MB SATA3
RAM
DDR4 32GB 3600MHz CL18 ARGB
GPU
Nvidia RTX 3080 10GB DDR6
Audio
Integrata 7.1 HD audio
Monitor
LG 34GN850
PSU
Gigabyte P850PM
Case
Phanteks Enthoo Evolv X ARGB
Periferiche
MSI Vigor GK30, mouse Logitech
Net
FTTH Aruba, 1Gb (effettivi: ~950Mb / ~480Mb)
OS
Windows 10 64bit / OpenSUSE Tumbleweed
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.
 
  • Mi piace
Reazioni: _Achille

_Achille

Utente Èlite
3,067
725
CPU
Intel i5-6600K @4.6 GHz
Dissipatore
Cryorig H5
Scheda Madre
ASRock Z170 Extreme 6
HDD
WesternDigital 1TB & Crucial MX200 250GB
RAM
Corsair Ven 16GB DDR4 2133MHz
GPU
Sapphire RX 580 Nitro+
Monitor
Dell S2418H
PSU
RM550X
Case
NZXT S340
Periferiche
Anne Pro 2, Razer Abyssus
OS
Windows 10 Pro
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:
C++:
BinaryTree<int> tree;
...
tree.Head()->Left()->Left()->Right() = new BinaryNode<int>(5);
//assumendo che i due Left siano diversi da nullptr
Diventerebbe
C++:
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
Post unito automaticamente:

Ho creato una funzione GetNode
C++:
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
C++:
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.
 
Ultima modifica:

DispatchCode

Moderatore
Staff Forum
Utente Èlite
2,210
1,846
CPU
Intel I9-10900KF 3.75GHz 10x 125W
Dissipatore
Gigabyte Aorus Waterforce X360 ARGB
Scheda Madre
Asus 1200 TUF Z590-Plus Gaming ATX DDR4
HDD
1TB NVMe PCI 3.0 x4, 1TB 7200rpm 64MB SATA3
RAM
DDR4 32GB 3600MHz CL18 ARGB
GPU
Nvidia RTX 3080 10GB DDR6
Audio
Integrata 7.1 HD audio
Monitor
LG 34GN850
PSU
Gigabyte P850PM
Case
Phanteks Enthoo Evolv X ARGB
Periferiche
MSI Vigor GK30, mouse Logitech
Net
FTTH Aruba, 1Gb (effettivi: ~950Mb / ~480Mb)
OS
Windows 10 64bit / OpenSUSE Tumbleweed
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

Utente Èlite
3,067
725
CPU
Intel i5-6600K @4.6 GHz
Dissipatore
Cryorig H5
Scheda Madre
ASRock Z170 Extreme 6
HDD
WesternDigital 1TB & Crucial MX200 250GB
RAM
Corsair Ven 16GB DDR4 2133MHz
GPU
Sapphire RX 580 Nitro+
Monitor
Dell S2418H
PSU
RM550X
Case
NZXT S340
Periferiche
Anne Pro 2, Razer Abyssus
OS
Windows 10 Pro
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
 

Entra

oppure Accedi utilizzando
Discord Ufficiale Entra ora!