Albero binario

di
RayD
il
7 risposte
R
RayD
Pochi posts
Iscritto da
gen, 2014
Messaggi:
41

Albero binario

Se io ho un albero binario completo o no.. come faccio diciamo a potare l albero lasciando solo i nodi a profondità minore di h.. passando h come parametro in c?

7 Risposte

  • S
    SVNiko
    Molto attivo
    Iscritto da
    set, 2014
    Messaggi:
    535

    Re: Albero binario

    Non ho capito bene che cosa vorresti fare.
    Hai un albero binario di profondità ad esenpio h=2, cioè:
    
                                    5
                            3              8
                        1      2        0     9
    vorresti che diventasse di h=1, cioè: 
    
                                    5
                            3              8
    E' così?
  • R
    RayD
    Pochi posts
    Iscritto da
    gen, 2014
    Messaggi:
    41

    Re: Albero binario

    Si avevo pensato ad usare una procedura che dealloca un albero in questo modo:
    visito l'albero in preordine, se un nodo ha profondità h-1 dealloco i sotto alberi figli.. se ne ha.
    solo mi sembra un po troppo eleborato come programma.. credo che ce sia una soluzione piu deretta e conincisa che mi sfugge
  • S
    SVNiko
    Molto attivo
    Iscritto da
    set, 2014
    Messaggi:
    535

    Re: Albero binario

    Io farei così:
    Costruisco una funzione che distrugge un intero albero.
    Poi visito l'albero che inorder, quando arrivo alla profondità desiderata, distruggo il sottoalbero sinistro, non faccio nulla alla radice, e distruggo il sottoalbero destro.
    Userei un contatore per controllare la profondità dell'albero. Il contatore può essere una variabile globale o meglio se passato alla funzione e allocato da una funzione wrapper.
  • R
    RayD
    Pochi posts
    Iscritto da
    gen, 2014
    Messaggi:
    41

    Re: Albero binario

    Pero come fai a permerti alla profondita desiderata?
    puoi postare il codice della procedura pota?
  • S
    SVNiko
    Molto attivo
    Iscritto da
    set, 2014
    Messaggi:
    535

    Re: Albero binario

    Prova a pubblicare quello che hai scritto e vediamo insieme come correggere.
  • R
    RayD
    Pochi posts
    Iscritto da
    gen, 2014
    Messaggi:
    41

    Re: Albero binario

    Ecco il codice: 
    
struct treeNode{
	int info;
	struct treeNode *sx;
	struct treeNode *dx;
	struct treeNode *pr;
	};
typedef struct treeNode TreeNode;
typedef TreeNode *TreeNodePtr;

void dealloca(TreeNodePtr *t){
	if(*t != NULL){
		dealloca(&(*t)->sx);
		dealloca(&(*t)->dx);
		}
	free(*t);
	}
int profondita(TreeNodePtr t,TreeNodePtr k){
	if(t == k) return 0;
	return 1+profondita(t,k->pr);
	}
void pota(TreeNodePtr *t,int h){
	if(*t == NULL) return;
	if(profondita(*t,(*t)->sx) > h)
		dealloca(&(*t)->sx);
	if(profondita(*t,(*t)->dx) > h)
		dealloca(&(*t)->dx);
	pota(&(*t)->sx,h);
	pota(&(*t)->dx,h);
	}
  • S
    SVNiko
    Molto attivo
    Iscritto da
    set, 2014
    Messaggi:
    535

    Re: Albero binario

    Io proverei con una funzione wrapper, che tiene il conto della profondità.
    Non l'ho messa sul compilatore, ma ragionevolmente dovrebbe funzionare.
    
void dealloca(TreeNodePtr *t) {
    if(*t != NULL) {
        dealloca(&(*t)->sx);
        dealloca(&(*t)->dx);
    }
    free(*t);
}

void pota(TeeNodePtr *t, int h) {
    int profondita = 0;
    potasottoalbero(&t, h, &profondità);
}

void potasottoalbero(TreeNodePtr *t, int h, int *profondita) {
    if((*profondita)==h) {
        dealloca(&(*t)->sx);
        dealloca(&(*t)->dx);
        return;
    }
    *profondita++;
    potasottoalbero(&(*t)->sx, h, profondita);
    *profondita--;
    potasottoalbero(&(*t)->dx, h, profondita);
}
Devi accedere o registrarti per scrivere nel forum
7 risposte