Attraversare in modo alterato attraverso l'albero per trovare la dimensione

Question

Ho bisogno di trovare il numero di elementi in un albero usando un algoritmo iterativo, ma sto trovando il codice concettualmente molto difficile da scrivere.

Il mio approccio è quello di iniziare dal nodo radice e visitare i nodi figlio, quindi i figli di questi nodi figlio e così via.

Questo è il codice che ho scritto, che lavora per un piccolo albero, ma non è una soluzione reale perché avevo bisogno di aggiungere un ulteriore blocco per ciascun livello di profondità:

// Start the counter at 1 because the root node counts 
int size = 1; 

for(ITree child1 : root) { 
    size++; 
    for(ITree child2 : child1) { 
     size++; 
     for(ITree child3 : child2) { 
      size++; 
      for(ITree child4 : child3) { 
       size++; 
       for(ITree child5 : child4) { 
        size++; 
       } 
      } 
     } 
    } 
} 
return size; 

Answer 1

Concettualmente , mantieni uno stack (LinkedList, ecc.). Per ogni bambino (ora, il tuo bambino esegue il ciclo), aggiungi alla pila. Continua a scorrere attraverso lo stack finché non è finalmente vuoto.

Questo non è testato, ma questo dovrebbe fare esattamente quello che stai cercando. Sto solo usando java.io.File al posto del "itree", in quanto è qualcosa che posso compilare contro:

int sizeOfTree(File root){ 
    // Start the counter at 1 because the root node counts 

    int size = 1; 

    LinkedList<File> stack = new LinkedList<File>(); 
    stack.add(root); 

    while(!stack.isEmpty()){ 
     File f = stack.remove(); 
     for(File child : f.listFiles()){ 
      size++; 
      stack.add(child); 
     } 
    } 

    return size; 
} 

Answer 2

Utilizzando una struttura dati ricorsiva

Non è praticamente possibile per attraversare in modo iterativo un data ricorsiva struttura, come un albero con i puntatori - questo è dovuto al fatto che gli oggetti "nascondono" i loro elementi di dati sottostanti.

Utilizzando una struttura dati diversa

Tutti gli alberi possono essere memorizzati/implementati da lineare, strutture di dati di matrice, dove gli indici possono essere calcolati utilizzando la matematica esponenziale:

Ad esempio, un albero [0 , 1, 2, 3, null, 4, null] descriverebbe un albero con 0 alla radice, dove 0 aveva figli diretti 1 e 2. E poi 1 ha lasciato figlio "3" e 2 ha lasciato figlio "4" .

Quindi, se si archivia l'albero in questo modo, il numero di elementi è, naturalmente, il numero di elementi non nulli nella matrice.

Metti più semplicemente: Archivia l'albero in una struttura lineare e puoi conoscere la lunghezza in qualsiasi momento senza dover fare alcun tipo di algoritmo di fantasia.

Answer 3

La parola chiave per l'attività è la ricorsione. Tree è una struttura ricorsiva classica, quindi dovresti scrivere un metodo ricorsivo che accetti i nodi root, conta le dimensioni di questo nodo e quindi chiama se stesso per tutti i bambini. Ecco pseudo-codice:

public int getSize(ITree root) { 
    return getSize(root, 0); 
} 

private int getSize(ITree node, int size) { 
    size++; 
    for(ITree child : node.children()) { 
     size += getSize(child, size) 
    } 
    return size; 
}