metodo ricorsivo per l'inserimento in un albero binario di ricerca (BST)

[elajiii]

Salve a tutti,
trovo delle difficoltà nell'implementare, in modo funzionante, un metodo ricorsivo per l'inserimento all'interno di BST.

public void insertRicorsivo(nodoBST p,int val) 
{ 
  if(p==null) 
  p=new nodoBST(val); 
  else 
 {
   if(val<p.key) 
      insertRicorsivo(p.left,val); 
   else if(val>p.key) 
         insertRicorsivo(p.right,val); 
   else 
     return; 
  } 
}

In cosa sbaglio? Perché al momento dell'esecuzione non aggiunge gli elementi?
Grazie in anticipo!

[LeleFT]

Per una ragione molto semplice:

se l'albero passato è nullo, tu lo crei, ma non lo ritorni. Chiamare una new dentro ad un metodo fa sì che l'oggetto venga creato in memoria ed il riferimento venga assegnato alla variabile locale del metodo, ma non modifica il riferimento della funzione chiamante, che continuerà a vedere un riferimento a nulla.

Dovresti modificare la funzione in modo che restituisca al chiamante l'albero modificato (e cambiare, di conseguenza, le invocazioni al metodo, anche quelle ricorsive) oppure prevedere un metodo nell'oggetto nodoBST (i nomi delle classi dovrebbero iniziare con la maiuscola!) e richiamare quello per l'inserimento.


Ciao.

[elajiii]

grazie della risposta. Tu come lo modificheresti? Perchè se faccio così:

public void insertRicorsivo(nodoBST p,nodoBST prev,int val) 
{ 
  if(p!=null)
  {
    if(val<p.key)
      insertRicorsivo(p.left,prev=p,val); 
    else 
      if(val>p.key)
        insertRicorsivo(p.right,prev=p,val);
    else 
     return; 
  }
  else
  {
    if(prev==null)
      root=new nodoBST(val);
    else
    {
      if(val<prev.key)
        prev.left=new nodoBST(val);
      else 
        prev.right=new nodoBST(val);
    }
  }

..funziona! Ma non sembra il massimo dell'eleganza.

[LeleFT]

Non puoi modificare la classe nodoBST in modo che possegga due metodi di questo tipo?

public void setLeft(nodoBST nodo) {
   this.left = nodo;
}

public void setRight(nodoBST nodo) {
   this.right = nodo;
}

(magari sarebbe utile avere dei metodi appositi per prelevare il left ed il right, invece di avere accesso diretto ai campi d'istanza).

Poi dovrai modificare l'insertRicorsivo in modo che utilizzi questi due metodi e richiami se stessa solo se il nodo left/right non è nullo.

public void insertRicorsivo(nodoBST p,int val) 
{
   if(p!=null) {
      if(val<p.key) {
         if (p.left != null) {
            insertRicorsivo(p.left,val);
         } else {
            p.setLeft( new nodoBST(val) );
         }
      } else {
         if(val>p.key) {
            if (p.right != null) {
               insertRicorsivo(p.right,val);
            } else {
               p.setRight( new nodoBST(val) );
            }
         }
      }
   } else {
      // L'albero non può essere nullo
   }
}

Ciao.

[elajiii]

Grazie mille!