[C] Funzione Albero Binario Completo

[Ancosen]

Con questa consegna:

Si definisca una funzione C che restituisce 1 se l'albero in input è completo, 0 altrimenti. Un albero binario è completo se ogni nodo ha 0 o 2 figli e tutte le foglie sono al piu’ su due livelli successivi, con quelle sul livello massimo tutte a sinistra. In altre parole un albero binario e’ completo se per ogni nodo i suoi sottoalberi sinistro e destro hanno la stessa altezza, il sinistro e’ pieno e il destro completo oppure il sottoalbero di sinistra, completo, e’ di 1 piu’ alto di quello di destra, che deve essere pieno. La funzione ha il seguente prototipo: int completo(treePtr tPtr)

Io avevo pensato a questo visto che credo un po' tutto dipenda dall'altezza dell'albero in questione.

#include<stdio.h>
#include<stdlib.h>

struct treenode
{
struct treenode *lPtr;
int data;
struct treenode *rPtr;
};
typedef struct treenode TreeNode;
typedef TreeNode *treePtr;

int completo(treePtr tPtr);
int alt(treePtr tPtr);
int max (int x, int y);

int alt(TreePtr tPtr) {
if (!tPtr ) return -1;
return max(alt(tPtr->lPtr),alt(tPtr->rPtr)) +1;
}

int max (int x, int y) {
if (x<y) return y;
else return x;
}

int completo(treePtr tPtr)
{
if (alt(tPtr->lPtr) == alt(tPtr->rPtr))
return 1;
return 0;
}

La mia domanda è se la funzione implementata può essere migliorata e se manca qualcosa d'importante. Grazie mille!

[Cr4m3]

Oddio anke tu alle prese con gli homework?

[71104]

LOL ma quanti ce ne sono che vengono dalla Sapienza???

[Ancosen]

Up... Semo tanti della Sapienza!

[Cr4m3]

:P se fossero un po piu chiari sti esercizi non ce ne sarebbe manco uno

[Ancosen]

Si, in effetti Gorla con la consegna che ha dato, non ci fa capire una mazza...

[sirus]

non li ho ancora fatti sono ancora un pivello delle superiori ma l'anno prossimo faccio anche io

[Cr4m3]

si sta meglio senza conosce gli alberi :P

[sirus]

però potrei tentarci lo stesso, intanto me la cavo benino

[sirus]

Originariamente inviato da Cr4m3

si sta meglio senza conosce gli alberi :P

purtroppo possono venire buoni
anche fino allo scorso anno pensavo che si vivesse anche senza allocazione dinamica della memoria o senza le liste e annessi e connessi ma in realtà sono comodissimi

[Cr4m3]

io con le liste, ci convivo abb bene, con l'allocazione dinamica un po meno pero non litighiamo spesso, con gli alberi prorpio non c'è feeling

[cionci]

Non gestisci questo caso: "e tutte le foglie sono al piu’ su due livelli successivi, con quelle sul livello massimo tutte a sinistra"

int completo(treePtr tPtr)
{
if (alt(tPtr->lPtr) == alt(tPtr->rPtr))
return 1;
return 0;
}

Secondo questo ragionamento contorto un albero del genere è completo:

     A
    / \
   B  C
  / \
 D  E

[sirus]

in effetti è vero ma...mistero

[cionci]

Comunque è facile: per essere completo le altezze o sono uguali o quella di sinistra è amggiore di uno di quella di destra...almeno così ho capito io...

[sirus]

beh anche per me che non ho ancora fatto queste cose (solo in teoria) non sembra un problema così complesso

[cionci]

C'è anche un altro errore... In alt devi controllare che le altezze siano uguali...perchè ogni nodo deve avere 0 o 2 figli...

int alt(TreePtr tPtr) {
   int ris1, ris2;
   if (!tPtr ) return 0;

   ris1 = alt(tPtr->lPtr);
   ris2 = alt(tPtr->rPtr);

   if(ris1 != ris2 || ris1 == -1 || ris2 == -1)
      return -1;

   return ris1 + 1; /*ritorno l'altezza aumentata di 1*/
}

In completo devi fare queste altre modifiche:

int completo(treePtr tPtr)
{
   int ris1, ris2;
   if (!tPtr ) return 1; /*un albero vuoto è completo ? diciamo di sì*/

   ris1 = alt(tPtr->lPtr);
   ris2 = alt(tPtr->rPtr);
   
   if ((ris1 == (ris2 + 1) || ris1 == ris2) && ris1 != -1 && ris2 != -1)
      return 1;

  return 0;
}