Albero di ricerca binaria ricorsiva x = modifica (x)

Question

Ecco un'immagine di cosa deve fare il mio codice.

Before Call: 
      +----+ 
      | -9 | 
      +----+ 
     / \ 
     /  \ 
     +----+  +----+ 
     | 3 |  | 15 | 
     +----+  +----+ 
    /  / \ 
    /  /  \ 
+----+  +----+  +----+ 
| 0 |  | 12 |  | 24 | 
+----+  +----+  +----+ 
     / \ 
     /  \ 
     +----+  +----+ 
     | 6 |  | -3 | 
     +----+  +----+ 

After Call: 
      +----+ 
      | -9 | 
      +----+ 
     / \ 
     /  \ 
     +----+  +----+ 
     | 6 |  | 30 | 
     +----+  +----+ 
    /  / \ 
    /  /  \ 
+----+  +----+  +----+ 
| 0 |  | 24 |  | 48 | 
+----+  +----+  +----+ 
     / \ 
     /  \ 
     +----+  +----+ 
     | 12 |  | -3 | 
     +----+  +----+ 

Fondamentalmente questo problema richiede che raddoppio valori di tutti i dati maggiore di 0 in un albero binario di interi. Il mio codice qui sotto fa questo per alcuni valori ma si arresta presto. Non sono sicuro di come sistemarlo ricorsivamente. Ecco come appare il mio output per l'albero sopra riportato.

 overallRoot 
     _[-9]_______________ 
     /     \ 
    _[6]     _____[30] 
/    /  \ 
[0]    _[12]   [24] 
       / \ 
       [6]  [-3] 
public void doublePositives() { 
    doublePositives(overallRoot); 
} 

private IntTreeNode doublePositives(IntTreeNode root) { 
    if(root != null) { 
     if(root.data > 0) { 
      root.data = 2* root.data; 
     }else { 
      root.left = doublePositives(root.left); 
      root.right= doublePositives(root.right); 
     } 
    } 
    return root; 
} 

Answer 1

È ancora necessario attraversare l'albero se si raddoppia un nodo. Lascia cadere il else in modo da poter sempre attraversare. Inoltre, ho rimosso le assegnazioni perché non si modifica la struttura ad albero:

if(root != null) { 
    if(root.data > 0) { 
     root.data = 2 * root.data; 
    } 
    doublePositives(root.left); 
    doublePositives(root.right); 
} 

Answer 2

Non si eseguono le chiamate ricorsive quando la radice è positiva.

Si eseguono solo le chiamate ricorsive quando la radice è negativa. Per risolvere questo basta rimuovere il resto.

private IntTreeNode doublePositives(IntTreeNode root) { 
    if(root != null) { 
     if(root.data > 0) { 
      root.data = 2* root.data; 
     } 
     root.left = doublePositives(root.left); 
     root.right= doublePositives(root.right); 
    } 
    return root; 
} 

Answer 3

Sembra un problema di logica - si vuole solo valori doppi di bambini di nodi negativi:

if(root.data > 0) { 
     root.data = 2* root.data; 
    }else { 
     root.left = doublePositives(root.left); 
     root.right= doublePositives(root.right); 
    } 

Se il il valore root è positivo - non si arriva mai a root.left & root.right. Qualcosa di simile a questo sarebbe meglio:

if(root.data > 0) { 
     root.data = 2* root.data; 
    } 
    root.left = doublePositives(root.left); 
    root.right= doublePositives(root.right); 

Answer 4

Prova questa: si stavano facendo errore nel istruzione condizionale. Questo dovrebbe essere stato scritto in questo modo. Se root ha i dati è positivo, rendilo doppio, roger that! e fuori! Nel passaggio successivo, procedere per i nodi figlio sinistro e destro.

Inoltre prendere nota di ciò, non è necessario restituire nulla (diverso da nullità) nella funzione ricorsiva doublePositives().

public void iWillDoit() { 
     doublePositives(Root); 
    } 

    private void doublePositives(IntTreeNode root) { 
     if(root != null) { 
      if(root.data > 0) 
      { 
       root.data = 2* root.data; 
      } 
      doublePositives(root.left); 
      doublePositives(root.right);  
     } 
    }