[C, alberi binari, liste] problema

[71104]

realizzare una funzione (una sola!) che presi in input un albero binario e una lista verifica che l'altezza dell'albero sia minore della lunghezza della lista.
questo era un eserciuìzio di un esonero di un corso di Programmazione 2; voi come fareste?
naturalmente il fatto che sia esplicitamente specificato di usare una sola funzione lascia intendere che per calcolare l'altezza dell'albero si debba usare un algoritmo iterativo.
come al solito, io la soluzione la so già ma pongo ugualmente la sfida 1) per vedere come se la cava cionci (spero che accetti la sfida), e 2) per confrontare le vostre soluzioni con la mia; ah, e anche 3) per avere una maggiore certezza di non aver scritto troppe cazzate a quell'esonero

[cionci]

Perchè non può essere ricorsivo
Comunque ho visto solo ora...domani ci provo...

[71104]

Originariamente inviato da cionci

Perchè non può essere ricorsivo

ok, può anche essere ricorsivo, ma deve comunque essere una sola funzione; e cmq il prof. l'ha anche detto che possibilmente doveva essere iterativo (considera che in genere gli algoritmi iterativi sono preferibili a quelli ricorsivi).

[Manugal]

Ma guarda un pò.........

Anch'io avevo il compito B oggi sai? L'ho fatto un pò alla mia maniera infatti non so se è giusto spero di averlo passato l'ho fatti tutti.

Io mandato una lista e un albero in input e poi ho fatto lo scorrimento dell'albero ricorsivamente sul sottoalbero sinistro e destro e ho aumentato un contatore chiamato cntalbero. Poi ho iniziato a scorrere gli elementi della lista e anche lì ho usato un contatore chiamato cntlista. Alla fine ho semplicemente confrontato i contatori e il più piccolo ha restituito VERO.

[71104]

Originariamente inviato da Manugal

Ma guarda un pò.........

Anch'io avevo il compito B oggi sai? L'ho fatto un pò alla mia maniera infatti non so se è giusto spero di averlo passato l'ho fatti tutti.

LOL
li ho fatti tutti anche io ma penso di aver toppato il bonus (vabbè, niente bonus x me ).

cmq mezzo Dipartimento di Informatica della Sapienza viene qui su HwUpgrade... mi sembra che fosse Andrea Cosentino l'altro che si era iscritto qualche mese fa; tu chi sei?

[cionci]

L'albero è bilanciato ?

[cionci]

Lo suppongo non bilanciato e che sia memorizzato nella struttura classica con figlioSX e figlioDX...

[cionci]

Fatto:

struct list {
	int info;
	struct list *next;
};

typedef struct list lista;


struct alb {
	int info;
	struct alb *sx;
	struct alb *dx;
};

typedef struct alb albero;

struct list_alb {
	albero *corrente;
	int visitato;
	int alt;
	struct list_alb *sx;
	struct list_alb *dx;
	struct list_alb *prev;
};

typedef struct list_alb lista_alb;

/*ritorna 1 se è minore, 0 altrimenti*/
int confronta(albero *a, lista *l)
{
	int lun_lista = 1;
	int lun_albero = 1;
	lista_alb *la;
	lista_alb *cur;
	lista_alb *tmp;

	if(!a && l) return 1;
	if(a && !l) return 0;

	while(l->next)
	{
		l = l->next;
		lun_lista++;
	}

	cur = la = (lista_alb *)malloc(sizeof(lista_alb));
	cur->prev = cur->dx = cur->sx = NULL;

	cur->corrente = a;
	cur->alt = 1;
	cur->visitato = 0;

	do {

		if((!cur->corrente->dx && !cur->corrente->sx) || cur->visitato == 2)
		{
			cur->visitato = 2;
			if(cur->alt > lun_albero)
				lun_albero = cur->alt;
			
			if(cur->prev) 
			{
				tmp = cur;
				cur = cur->prev;
				cur->visitato++;
                free(tmp);
			}
			continue;
		}

		switch(cur->visitato)
		{
		case 0:
			if(cur->corrente->sx)
			{
				tmp = (lista_alb *)malloc(sizeof(lista_alb));
				tmp->alt = cur->alt + 1;
				tmp->visitato = 0;
				tmp->prev = cur;
				tmp->corrente = cur->corrente->sx;
				tmp->sx = tmp->dx = NULL;
				cur->sx = tmp;
			}
			if(cur->corrente->dx)
			{
				tmp = (lista_alb *)malloc(sizeof(lista_alb));
				tmp->alt = cur->alt + 1;
				tmp->visitato = 0;
				tmp->prev = cur;
				tmp->corrente = cur->corrente->dx;
				tmp->sx = tmp->dx = NULL;
				cur->dx = tmp;
			}
			if(!cur->corrente->dx)
			{
				cur->visitato++;
				cur = cur->sx;
			}
			else
				cur = cur->dx;
			break;
		case 1:
			if(cur->sx) cur = cur->sx;
			else cur->visitato++;
			break;
		}

	} while(la->visitato < 2);
	free(la);
	return (lun_albero < lun_lista) ? 1 : 0;
}

[71104]

Originariamente inviato da cionci

Fatto:[...]

vedo che hai usato dei nodi d'appoggio che sono una fusione tra quelli dell'albero e quelli della lista; inoltre vedo che questi nodi contengono un flag (visitato) che risolve il problema dell'assenza dello stack durante la visita dell'albero (cioè permette di fare un algoritmo iterativo anziché ricorsivo); complimenti, ottima soluzione!
io ho fatto diversamente: per rimediare all'assenza dello stack durante la visita dell'albero ho usato una variabile d'appoggio (chiamiamola "provenienza") che ogni volta che il nodo corrente si setta su un'altra posizione, mi indica da dove "proviene" il nodo corrente, cioè se la posizione precedente a quella corrente era il padre, il figlio sx o il figlio dx del nodo corrente; ho fatto tutto dentro un ciclo, più o meno così:

typedef struct _TNODE {  // tree node
    int data;
    struct _TNODE *p, *l, *r;
} TNODE, *PTNODE;

//...

int h = 0;  // altezza dell'albero
int i = 0;  // contatore altezza
PTNODE n = ...; //n viene inizializzato alla radice dell'albero
while (n) {
	switch (provenienza) {
	case 0:  // n prima era il padre
		if (n->l) {
			provenienza = 0;
			n = n->l;
			if (++i > h) h = i;
			break;
		}
		else {
			provenienza = 1;
		}
	case 1:  // n prima era il figlio sinistro
		if (n->r) {
			provenienza = 0;
			n = n->r;
			if (++i > h) h = i;
			break;
		}
		else {
			provenienza = 2;
		}
	case 2:  // n prima era il figlio destro
		if (n->p) {
			if (n == n->p->l) {
				provenienza = 1;
			}
			else {
				provenienza = 2;
			}
			n = n->p;
			i--;
		}
		break;
	}
}

ho usato alberi doppiamente linkati (cioè ogni nodo conosce anche il padre) altrimenti non ne uscivo fuori ^^' il prof. ha detto che andava bene.

PS: cmq si, l'albero non doveva essere supposto bilanciato (altrimenti era na cazzata bastava scendere su tutti i left o su tutti i right e contare finché non trovavi NULL in pratica diventava il conteggio di due liste).

[cionci]

Se era doppiamente linkato era più facile...infatti ho costruito proprio quella struttura per permettermi di andare avanti ed indietro nell'albero...