[java]albero binario completo

[Uccio87]

Salve,
vorrei creare un metodo che mi dice se il mio albero è completo.
completo: ogni nodo deve avere 2figli.
io l'ho svolto così:

  public boolean isComplete() 
  {
      return isComplete(root) > -2;
  }

  private int isComplete(Node nd) 
  {
  if (nd == null) 
  {
        return -2;
  }
  int c = (int) Math.pow(2,height(nd));
  int foglie = numFoglie();
  
  return c-foglie;
  }

ma vorrei svolgerlo in modo da non percorre l'intero albero 2 volte, una volta per trovare l'altezza(height(nd)) e l'altra per trovare il numero di foglie(numFoglie())

Potete darmi qualche indicazione?

[Mr.Bloom]

Non ho capito bene il tuo algoritmo.
tuttavia, ammesso che tu possa usare la ricorsione, che ne dici del seguente codice ?

static boolean isComplete(Node nd){

   if(nd == null) 
     return true;

  if(nd.getNumChildren() != 2) 
     return false;

  return isComplete(nd.getFirstChild()) && isComplete(nd.getSecondChild());

}

[Uccio87]

un albero è completo quando ogni suo nodo ha esattamente due figli.
es:

                       5
                  6          7
               8     9   10   11

non completo:

                       5
                  6          7
                     9   10   11

l'algoritmo da me sviluppato, dato che per essere completo un albero deve aver 2^altezza albero uguali al numero di foglie

esempio 1: 2^2 == 4(foglie) completo
esempio 2: 2^2 != 3(foglie) non completo

[SolidSnake4]

Quello che dice Uccio87 è questo:

Un albero vuoto (null) è completo

Un albero non vuoto è completo se:

1) i sottoalberi sx e dx sono completi
2) ed hanno la stessa altezza

Sulla base di questo Mr.Bloom il tuo esempio continua a funzionare ?

Inoltre il metodo isComplete deve usare un solo metodo ricorsivo, in modo da calcolare allo stesso tempo altezza dell'albero o del sottoalbero esaminato

Io farei così comunque in risposta ad Uccio87

public boolean isComplete() {
   return isComplete(root) > -2;
}

public boolean isComplete(Node nd) {
  int hl, hr;
  if (nd == null) return -1; // l'albero vuoto (== null) è completo

  hl = isComplete(nd.left);
  hr = isComplete(nd.right);

  if (hl != hr) return -2; // Se uno dei sotto alberi è null l'albero non è completo, e termino di esplorare l'albero
  else return 1 + Math.max(hl, hr); // Se l'altezza del sottoalbero sinistro è uguale all'altezza del sottoalbero di destra restituisco restituisco l'altezza dell'albero
}

Che ne dite ?

[LeleFT]

Originariamente inviato da SolidSnake4
Che ne dite ?

Che, magari, dovresti usare i tag CODE per il codice, altrimenti diventaq tutto ingarbugliato, perdendo formattazione ed indentazione.

Ho aggiunto io i tag al tuo post.


Ciao.

[SolidSnake4]

Ah pardon, andavo di fretta e non ho usato i tag giusti