Albero binario

7 Risposte

• S

  SVNiko

  Molto attivo

  Iscritto da

  set, 2014

  Messaggi:

  535

  Re: Albero binario

  12 nov 2014, 18:13

  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ì?
• /

  Anonimizzato13936

  Utente anonimizzato

  Re: Albero binario

  12 nov 2014, 18:55

  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

  12 nov 2014, 19:26

  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.
• /

  Anonimizzato13936

  Utente anonimizzato

  Re: Albero binario

  14 nov 2014, 12:19

  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

  14 nov 2014, 14:55

  Prova a pubblicare quello che hai scritto e vediamo insieme come correggere.
• /

  Anonimizzato13936

  Utente anonimizzato

  Re: Albero binario

  15 nov 2014, 10:05

  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

  15 nov 2014, 10:47

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