Albero Binario: funzione che aggiunge un nodo

_Achille

Utente Attivo
2,961
676
Hardware Utente
CPU
Intel i5-6600K @4.6 GHz
Dissipatore
Cryorig H5
Scheda Madre
ASRock Z170 Extreme 6
Hard Disk
WesternDigital 1TB & Crucial MX200 250GB
RAM
Corsair Ven 16GB DDR4 2133MHz
Scheda Video
Sapphire RX 580 Nitro+
Monitor
Dell S2418H
Alimentatore
RM550X
Case
NZXT S340
Periferiche
Cooler Master XT; Razer Abyssus
Sistema Operativo
Windows 10 Pro
#1
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:
566
321
Hardware Utente
CPU
Intel i7 6700HQ, 2.60Ghz, 4 core 8 threads
Scheda Madre
Asustek
Hard Disk
Hitachi 7200 rpm, 1TB
RAM
16GB DDR4 (2 slot su 4)
Scheda Video
Nvidia Geforce GTX 960M, 4GB
Scheda Audio
Realtek
Sistema Operativo
Windows 10 64bit
#2
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: _Achille

_Achille

Utente Attivo
2,961
676
Hardware Utente
CPU
Intel i5-6600K @4.6 GHz
Dissipatore
Cryorig H5
Scheda Madre
ASRock Z170 Extreme 6
Hard Disk
WesternDigital 1TB & Crucial MX200 250GB
RAM
Corsair Ven 16GB DDR4 2133MHz
Scheda Video
Sapphire RX 580 Nitro+
Monitor
Dell S2418H
Alimentatore
RM550X
Case
NZXT S340
Periferiche
Cooler Master XT; Razer Abyssus
Sistema Operativo
Windows 10 Pro
#3
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
[automerge]1535989561[/automerge]
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:
566
321
Hardware Utente
CPU
Intel i7 6700HQ, 2.60Ghz, 4 core 8 threads
Scheda Madre
Asustek
Hard Disk
Hitachi 7200 rpm, 1TB
RAM
16GB DDR4 (2 slot su 4)
Scheda Video
Nvidia Geforce GTX 960M, 4GB
Scheda Audio
Realtek
Sistema Operativo
Windows 10 64bit
#4
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 Attivo
2,961
676
Hardware Utente
CPU
Intel i5-6600K @4.6 GHz
Dissipatore
Cryorig H5
Scheda Madre
ASRock Z170 Extreme 6
Hard Disk
WesternDigital 1TB & Crucial MX200 250GB
RAM
Corsair Ven 16GB DDR4 2133MHz
Scheda Video
Sapphire RX 580 Nitro+
Monitor
Dell S2418H
Alimentatore
RM550X
Case
NZXT S340
Periferiche
Cooler Master XT; Razer Abyssus
Sistema Operativo
Windows 10 Pro
#5
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
 

Discussioni Simili


Entra