[C++] Albero binario - inserimento

di
beginner32
il
7 risposte
B
beginner32
Utente Attivo
Iscritto da
dic, 2016
Messaggi:
76

[C++] Albero binario - inserimento

Salve a tutti.
Ho un problema nella realizzazione di una struttura ad albero binario semplice , non di ricerca. Il problema è il seguente: Dopo aver creato la struttura dati Nodo e costruito dei metodi pubblici per settare i collegamenti , ora mi sono bloccato sulla creazione dell' albero vero e proprio. Mi spiego meglio, banalmente sono in grado di costruire un albero vuoto oppure un albero che , preso un nodo in input, lo setta come radice mantenendo i propri collegamenti. Vorrei consigli per capire come procedere sia nell inserimento che nella costruzione di un albero senza dover creare da me prima i singoli nodi,poi linkarli tra loro e successivamente settarne uno come radice.
Questo è uno stralcio 

template <class T>
Class treeNode
{
public:
  treeNode();
  treeNode(T Val);
  
  void setValue(T val);
  void setDad(T); 
  /*non so se sia più corretto passare un valore,creare un nodo con tale valore all interno del metodo oppure passare direttamente un puntatore a nodo */
  void setLeft(T);
  void setRight(T);
  
  T getInfo();
  treeNode<T>* getDad(); //uguale per i figli
  
  
  private:
  
  T info_;
  treeNode<T> * dad_;
  treeNode<T> * left_;
  treeNode<T> * right_;
}



template <class T>
class binarytree
{

Public:

	binaryTree();
	binaryTree(int size) ; //costruttore di un albero avente size nodi , disposti in maniera "casuale" con valori "casuali";
	~binaryTree();
	
	
	void insert(); 
	...
	...
	



private: 
TreeNode<T>* root_;
Int size;
Int Height;
}

7 Risposte

  • M
    migliorabile
    Super Famoso
    Iscritto da
    apr, 2013
    Messaggi:
    5847

    Re: [C++] Albero binario - inserimento

    La potenza della programmazione ad oggetti, sta proprio qui'!

    Il tuo oggetto, che il tuo programma usera', NON E' il nodo dell'albero, ma l'INTERO ALBERO.

    E' RESPONSABILITA' dell'oggetto ALBERO sapere come e' IMPLEMENTATO e fare le allocazioni del caso.

    In particolare, tu devi IDENTIFICARE quali sono le operazioni che devi fare in termini di INTERO albero, solo DOPO deciderai come IMPLEMENTARE le operazioni.


    In questo caso, la cosa e' abbastanza semplice:

    1) devi creare l'ALBERO
    2) devi inserire un ELEMENTO nell'albero (che NON E' il NODO, il nodo e' solo una POSSIBILE implementazaione)
    3) potresti voler controllare la presenza di un ELEMENTO (ripeto, NON un nodo, ma il VALORE memorizzato nel nodo)
    4) potresti voler CANCELLARE un ELEMENTO dall'albero (di nuovo, NON il nodo, perche' l'utilizzatore del tuo albero NON DEVE SAPERE come e' fatto l'albero)
    5) devi saper come DISTRUGGERE l'albero, in modo corretto (cioe' rimuovere tutti i nodi ivi contenuti)
  • B
    beginner32
    Utente Attivo
    Iscritto da
    dic, 2016
    Messaggi:
    76

    Re: [C++] Albero binario - inserimento

    Mi si è accesa la lampadina! Grazie mille
  • B
    beginner32
    Utente Attivo
    Iscritto da
    dic, 2016
    Messaggi:
    76

    Re: [C++] Albero binario - inserimento

    Per risolvere l 'inserimento , ho optato per un inserimento tipico di un albero binario di ricerca. Ma non essendo un albero di ricerca, in fase di cancellazione posso sempre cancellare l'intero sottoalbero radicato nel nodo vittima ?
  • M
    migliorabile
    Super Famoso
    Iscritto da
    apr, 2013
    Messaggi:
    5847

    Re: [C++] Albero binario - inserimento

    beginner32 ha scritto:

    Per risolvere l 'inserimento , ho optato per un inserimento tipico di un albero binario di ricerca. Ma non essendo un albero di ricerca, in fase di cancellazione posso sempre cancellare l'intero sottoalbero radicato nel nodo vittima ?
    E bravo furbo, cosi' se per caso vuoi cancellare il nodo radice, cancelli l'intero albero?

    Per forza che hai dovuto optare per un inserimento tipico di un albero binario di ricerca, per il semplice fatto che NON ESISTE una differenza tra un albero binario semplice ed uno di ricerca!!!

    Caso mai, la differenza e' tra un albero binario semplice ed uno bilanciato in cui, dopo ogni inserimento o cancellazione, ribilanci l'albero!!!
  • B
    beginner32
    Utente Attivo
    Iscritto da
    dic, 2016
    Messaggi:
    76

    Re: [C++] Albero binario - inserimento

    migliorabile ha scritto:

    E bravo furbo, cosi' se per caso vuoi cancellare il nodo radice, cancelli l'intero albero?
    Esattamente anche se potrebbe andar bene come metodo ausiliario, in realtà avrei comunque bisogno di un metodo che elimini soltanto un nodo. C'ero quasi, funzionava bene tranne nel caso in cui il nodo da cancellare era la radice stessa. Al che ho abbandonato e cancellato(purtroppo ) quella soluzione.
  • M
    migliorabile
    Super Famoso
    Iscritto da
    apr, 2013
    Messaggi:
    5847

    Re: [C++] Albero binario - inserimento

    Ed allora STUDIA: i metodi per cancellare un nodo QUALUNQUE da un albero sono SEMPLICE!

    Ma NON BANALI
  • B
    beginner32
    Utente Attivo
    Iscritto da
    dic, 2016
    Messaggi:
    76

    Re: [C++] Albero binario - inserimento

    Seguirò il tuo consiglio,dopotutto è la ragione per cui mi trovo ad affrontare questo mini- problema.
Devi accedere o registrarti per scrivere nel forum
7 risposte