Come costruire un albero non binario con o senza ricorsione?

Question

Ho un gerarchica dei dati che va come questo:

+----------------------+-------+ 
| name     | depth | 
+----------------------+-------+ 
| ELECTRONICS   |  0 | 
| TELEVISIONS   |  1 | 
| TUBE     |  2 | 
| LCD     |  2 | 
| PLASMA    |  2 | 
| PORTABLE ELECTRONICS |  1 | 
| MP3 PLAYERS   |  2 | 
| FLASH    |  3 | 
| CD PLAYERS   |  2 | 
| 2 WAY RADIOS   |  2 | 
+----------------------+-------+ 

TUBE, LCD e Plasma sono figli di televisori. FLASH è figlio di Lettori MP3. LETTORI MP3, LETTORI CD e RADIO A 2 VIE sono i figli di ELETTRONICA PORTATILE. Ottieni il trapano.

Ora, ho un nodo struttura che contiene il suo ID e i suoi figli, e così via, come per costruire un albero. Come questo:

struct Node 
{ 
    int id; 
    list<Node*> children; 
} 

Ogni elemento è identificato da un ID, che è il numero di riga (ELETTRONICA = 0, televisori = 1, e così via), quindi è facile per scoprire chi sono i figli di un nodo.

Questo è l'albero che sto cercando di costruire. Questo albero non è binario, come puoi vedere. Quindi applicare la ricorsione non sembra un'idea facile. Correggimi se sbaglio.

Quindi, come posso eseguire questo? Aiuto!

Answer 1

Utilizzare invece i puntatori ai nodi, altrimenti si duplicheranno i dati nell'albero in ciascun livello.

Vorrei anche suggerire di usare un enum invece di int id, rende il codice un po 'più chiaro.

non c'è alcun problema nell'utilizzare la ricorsione con un albero non binario, è sufficiente invece di chiamare left/right (o simile) nella chiamata di funzione ricorsiva in ciascuno nello list<Node*>.

Answer 2

Non c'è alcuna limitazione che l'albero debba essere binario per costruirlo in modo ricorsivo. Potrebbe essere sia creato sia con metodo ricorsivo e non ricorsivo.

Per me, vorrei costruire l'albero in modo top-down, cioè creare il nodo genitore prima dei bambini. Vorrei ordinare i dati di input in qualche modo per rendere il consumo lineare. Per aggiungere un nuovo nodo, basta dare la profondità come parametro e diminuire (mentre si scende dalla radice) fino a raggiungere lo 0, che è dove dovrebbe essere il nodo. Naturalmente, è richiesta l'informazione del percorso genitore per il nodo.

Answer 3

Qualcosa di simile a questo:

int main() 
{ 
    Node flash(FLASH_ID); 
    Node mp3(MP3_ID); 

    mp3.children.push_back(flash); 
    // repeat 
} 

Answer 4

È possibile utilizzare più di un puntatore di collegamento. cioè

struct node 
{ 
int id; 
node *first_child; 
node *second child; 
node *third_child; 
} 

In te caso il massimo è 3. È possibile puntare i nodi con i diversi figli e accedervi. Nel caso in cui ci siano meno di 3 figli, puoi renderlo NULL.