ElectroYou

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

La consegna è :

Codice: Seleziona tutto

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();
}


Apposto, risolto

Beh, potresti postare la soluzione.
Magari può essere interessante per altri utenti.

AjeieBrazov ha scritto:Beh, potresti postare la soluzione.

Volentieri ma in realtà non l'ho risolto, ho solo trovato l'errore.
Ho appena riprovato e ho costruito un altro metodo, che non ha il problema di prima ovvero tiene conto delle altezze.
Voglio verificare che le radici dei due sotto-alberi considerati, presi in maniera ricorsiva partendo dalle foglie, abbiano la stessa altezza o detto in altre parole verifico che le altezze de fratelli siano uguali, condizione necessaria per un albero triangolare. Verifico anche che i fratelli ci siano entrambi o non ci siano proprio.
Non ho controllato i casi degeneri (1, 3 nodi, albero vuoto) perché non ho tempo.
Se tutto va bene alla fine restituisco l'altezza dell'albero, che non può essere maggiore/uguale al numero totale di nodi (size()), condizione che sfrutto per identificare quando l'albero non è triangolo.
Size() ha prestazioni temporali
Se qualcuno dà un occhiata mi fa una grande cortesia.

Codice: Seleziona tutto

static <T> boolean isTriangular(BinaryTree<T> a)
{
   return depth(a.root(),a.size())>a.size();
}

static <T> int depth (Position<T> v, int s)
{
   int left = 0;
   int right = 0;
   int dim=s;
   if(v.hasLeft()&&v.hasRight())
   {
      left=1+depth(v.left(),dim);
      right=1+depth(v.right(),dim);
      if(left==right)
         return left;
      return dim;                       //altezze diverse, non triangolare
   }
   if(v.hasLeft()==v.hasRight())   //entrambe false, una foglia
      return 0;
   return dim;                 //un nodo che ha un solo figlio, non triangolare
}