[Java] Verifica se l'albero binario è triangolare

Messaggioda absinth » 01/08/2017, 06:36

Ciao a tutti! Ho un dubbio riguardo a un algoritmo che ho appena scritto. Mi sembra troppo breve rispetto alle alternative della soluzione quindi forse ho sbagliato ma non trovo l'errore.
Forse i confronti con null non vanno bene?. E' da un sacco che non studio java
La mia idea è che se un albero binario è triangolare, allora lo sono anche i sui sotto-alberi. A quanto pare risulta O(n).

La consegna è :
Immagine

La mia soluzione:
Codice:
static <T> boolean isTriangular(BinaryTree<T> a)
{
   return isTriangularPos(a.root());
}

static <T> boolean isTriangularPos(Position<T> v)
{
   if(v.hasLeft()&&v.hasRight())
   {
      if (v.left().isExternal()||v.right().isExternal())
         return v.left().isExternal()==v.right().isExternal();
      return isTriangularPos(v.left())&&isTriangularPos(v.right());
   }
   return v.hasLeft()==v.hasRight();
}
absinth
Junior Member
Junior Member
 
Messaggio: 18 di 184
Iscritto il: 20/06/2017, 17:21
Località: Venezia

Re: [Java] Verifica se l'albero binario è triangolare

Messaggioda apatriarca » 01/08/2017, 10:18

Non ho mai sentito parlare di albero triangolari. Intendi dire un albero completo (con \(2^N\) nodi e completamente bilanciato?\). Se è così allora la tua idea non funziona perché i due figli possono essere completi, ma avere un numero diverso di nodi. Quello che stai effettivamente testando è in pratica che ogni nodo è un foglia o un nodo interno con due figli. Devi insomma tenere anche traccia della profondità massima raggiunta nei due sottoalberi.
apatriarca
Moderatore
Moderatore
 
Messaggio: 4754 di 10435
Iscritto il: 08/12/2008, 20:37
Località: Madrid

Re: [Java] Verifica se l'albero binario è triangolare

Messaggioda absinth » 01/08/2017, 11:21

L'albero binario triangolare ha $2^{h+1}-1$ nodi dove $h$ è l'altezza e ha questa struttura:
Immagine

A quanto pare l'hai capito bene ma non riesco a trovare l'errore cioè seguendo il tuo ragionamento un albero di questo tipo:
Immagine
dovrebbe dare TRUE?

Allora è strano perché al primo ciclo uno dei due figli è una foglia mentre l'altro no quindi nell'IF interno
return v.left().isExternal()==v.right().isExternal() mi darà FALSE.

se no allora per favore puoi farmi vedere o spiegare un esempio di non triangolare che verifica le condizioni?
absinth
Junior Member
Junior Member
 
Messaggio: 19 di 184
Iscritto il: 20/06/2017, 17:21
Località: Venezia

Re: [Java] Verifica se l'albero binario è triangolare

Messaggioda apatriarca » 01/08/2017, 11:24

Si, devi andare un po' più profondo per vederlo per via del secondo test che fai. Considera un albero con il sottoalbero sinistro triangolare di profondità 4 e quello destro di profondità 2.
apatriarca
Moderatore
Moderatore
 
Messaggio: 4755 di 10435
Iscritto il: 08/12/2008, 20:37
Località: Madrid

Re: [Java] Verifica se l'albero binario è triangolare

Messaggioda absinth » 01/08/2017, 12:55

ah già devo per forza tener conto della profondità, grazie mille
absinth
Junior Member
Junior Member
 
Messaggio: 20 di 184
Iscritto il: 20/06/2017, 17:21
Località: Venezia


Torna a Informatica

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite