Determinare la dimensione dell'intero albero binario tramite ricorsione

Question

Ho le classi BinaryTreeNode (int value) con i relativi child sinistro e destro e BinaryTree (int rootVal) con BinaryTreeNode root con rootVal come valore. ho sviluppato un codice per calcolare il numero di nodi dell'albero (in classe BinaryTreeNode), ma non funziona a causa di un NullPointerException:

public int size(){ 
    if(this == null) { // base case 
     return 0; 
    } else { 
     return 1 + left.size() + right.size(); 
    } 
} 

Tuttavia un'altra soluzione che ho trovato, con una strategia simile, opere :

Ho capito perché il mio codice genera un'eccezione (è perché left/right farebbe riferimento a null). Ma vorrei capire perché la seconda soluzione funziona quasi con lo stesso principio. Grazie in anticipo!

Answer 1

Nel vostro primo esempio si cerca di trovare la dimensione prima di controllare per null:

primo si chiama

left.size() 

e poi dentro il metodo size() di controllare per vedere se l'oggetto hai appena chiamato il metodo è null

if(this == null) { // base case 
    return 0; 
... 

quindi se left è null, si ottiene l'NPE prima di entrare nel metodo size().

La cosa più importante da ricordare, è che this può mai essere null. Se lo fosse, non si potrebbe essere in esecuzione un metodo su di esso in primo luogo. Quindi non stavi effettivamente terminando la tua ricorsione su un caso null come pensavi di essere.

Nella seconda si controlla la null prima:

se refnode.sinistra è null qui

return 1 + size(refNode.left) + size(refNode.right); 

il metodo size() fa un pre-check

if(refNode == null) { // base case 
    return 0; 
... 

e sicuro ritorna 0.

si potrebbe rendere il vostro primo metodo di lavoro mettendo esplicitamente il nulla-check prima su ogni ramo:

public int size(){ 
    return 1 
     + left == null ? 0 : left.size() // check for null first 
     + right == null ? 0 : right.size(); // check for null first 
} 

Answer 2

this non può mai essere null all'interno della classe corrente. Riceverai un NPE perché un nodo con left == null o right == null non sarà in grado di chiamare il codice size(), perché il puntatore non fa riferimento a nulla.

Forse il codice dovrebbe essere più difensivo e verificare se i bambini sono nulli prima di tentare di recuperare la loro dimensione:

public int size() { 
    int total = 1; 
    if (left != null) 
     total += left.size(); 
    if (right != null) 
     total += right.size(); 
    return total; 
} 

Answer 3

Il caso base è organizzata in modo sbagliato; il controllo di null nell'istanza corrente non ha senso. Il metodo dovrebbe essere riscritto come segue.

public int size(){ 
    int sizeLeft = 0; 
    if (this.left != null) 
     sizeLeft = left.size(); 
    int sizeRight = 0; 
    if (this.right != null) 
     sizeRight = right.size(); 
    return 1 + sizeLeft + sizeRight; 
}