disiodj

Alberi_Qualsiasi_N-ari

Jan 15th, 2016
313
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. ESERCIZI PER ALBERI QUALSIASI
  2.  
  3. CONTA-NODI(t)---------------CHIEDI SE GIUSTO--------------
  4.     if(t==null)
  5.         return 0;
  6.     if(t.left!=NULL)   
  7.         L= 1+CONTA-NODI(t.left);
  8.     if(t.right!=NULL)
  9.         r= 1+CONTA-NODI(t.right);
  10.     return 1+l+r; //avevi sbagliato con t.parent
  11.    
  12. ----------------------------------------------------------------------------------------
  13.  
  14. CERCA(T,k)
  15.     if(T==null)
  16.         return NULL;   
  17.     if(T.info==k)
  18.         return T;
  19.     l=CERCA(t.left)
  20.     if(l!=NULL)
  21.         return l;
  22.     r = CERCA(T.right)
  23.     if(r!=NULL)
  24.         return r;
  25.     return NULL
  26. }
  27.  
  28. -------------------------------------------------------------------------
  29.  
  30. BINARIO(T)
  31.     return BINARIO-RADICE(t.root)
  32.    
  33. BINARIO-RADICE(T){
  34. if(t==NULL)
  35.     return true;
  36. return BINARIO-RIC(T.left, 1);
  37. }
  38.  
  39. BINARIO-RIC(T, i)
  40.     if(t==null)
  41.         return TRUE;
  42.     if(i<0)
  43.         return FALSE
  44.     ritorno_right = BINARIO-RIC(T.right, i-1)
  45.     if(!ritorno_right)
  46.         return FALSE;
  47.     ritorno_left = BINARIO-RIC(T.left, 1)
  48.     if(!ritorno_left)
  49.         return FALSE;
  50.     return TRUE;
  51.  
  52. ----------------------------------------------------------------------------------
  53.    
  54. GRADO-MASSIMO(T)
  55.     return GRADO-MASSIMO-RIC(T.root)
  56.    
  57. GRADO-MASSIMO-RIC(T)
  58. if(T==NULL)
  59.     return 0;
  60. cont = 1+GRADO-MASSIMO-RIC(T.right)
  61. figli = GRADO-MASSIMO-RIC(T.left)
  62. return Max(cont , figli);
  63.  
  64. ---------------------------------------------------------------------------------
  65.  
  66. COPIA_ALBERO(t)
  67.     n = CONTA_NODI(t.root)
  68.     /* nuovonodo è un array di dimensione n, dove nuovonodo[i] è un riferimento al nodo del nuovo albero che rappresenta la copia del       nodo dell’albero t con indice i */
  69.     for i = 0 to nuovonodo.length{
  70.         /* creo un nuovo nodo nuovonodo[i] */
  71.         nuovonodo[i].info = i
  72.         nuovonodo[i].parent = NULL
  73.         nuovonodo[i].left = NULL
  74.         nuovonodo[i].right = NULL
  75.     }
  76.     /* tout è un nuovo albero */
  77.     tout.root = NULL
  78.     /* inizializzazione (non indispensabile) */
  79.     if (t.root != NULL)
  80.         tout.root = nuovonodo[t.root.info]
  81.     COPIA(t.root, nuovonodo)
  82.     return tout
  83.  
  84. CONTA_NODI(n)
  85.     if (n == NULL)
  86.         return 0
  87.     return 1 + CONTA_NODI(n.right) + CONTA_NODI(n.left)
  88.  
  89. COPIA(n, nuovonodo)
  90.     if (n == NULL)
  91.          return
  92.     if (n.parent != NULL)
  93.         nuovonodo[n.info].parent = nuovonodo[n.parent.info]
  94.     if (n.left != NULL)
  95.         nuovonodo[n.info].left = nuovonodo[n.left.info]
  96.     if (n.right != NULL)
  97.         nuovonodo[n.info].right = nuovonodo[n.right.info]
  98.     COPIA(n.left, nuovonodo)
  99.     COPIA(n.right, nuovonodo)
  100. ------------------------------------------------------------------------
RAW Paste Data