Advertisement
Guest User

Untitled

a guest
May 21st, 2016
124
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2. PROCEDURE Balanceado (VAR l: ListaString): Binario;
  3. (* Precondicion: NOT EsVaciaLista (l) y EstaOrdenadaLista (l).
  4.    Devuelve un arbol con un nodo por cada elemento de 'l'. El valor numerico del
  5.    nodo es 0 y el valor de texto es igual al elemento de 'l'.
  6.    El arbol resultado debe estar balanceado.  
  7.    Un arbol esta balanceado si en cada nodo que no es hoja, la cantidad
  8.    de elementos de su subarbol izquierdo es igual a, o 1 mas que, la cantidad
  9.    de elementos de su subarbol derecho.
  10.    Al finalizar debe haberse liberado toda la memoria asignada a 'l'.    
  11.    El tiempo de ejecucion es O(n . log n), siendo n = CantidadLista (l)
  12.    (ver letra). *)
  13. VAR
  14.     a: Binario;
  15.     l2: ListaString;
  16. BEGIN
  17.     IF CantidadLista(l) = 1 THEN
  18.         IrInicioLista(l);
  19.       a := CrearHoja(CrearInfo(0, ActualLista(l)));
  20.       RemoverDeLista(l);
  21.     ELSE
  22.         l2 := PartirLista(l);
  23.       IrInicioLista(l2);
  24.       a := CrearHoja(CrearInfo(0, ActualLista(l2)));
  25.       RemoverDeLista(l2);
  26.  
  27.       a^.izquierdo := Balanceado(l);
  28.       a^.izquierdo^.padre := a;
  29.  
  30.       IF CantidadLista(l2) > 0 THEN
  31.          a^.derecho := Balanceado(l2);
  32.          a^.derecho^.padre := a;
  33.       END;
  34.  
  35.     END;
  36.     RETURN a;
  37.    
  38. END Balanceado;
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement