Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- PROCEDURE Balanceado (VAR l: ListaString): Binario;
- (* Precondicion: NOT EsVaciaLista (l) y EstaOrdenadaLista (l).
- Devuelve un arbol con un nodo por cada elemento de 'l'. El valor numerico del
- nodo es 0 y el valor de texto es igual al elemento de 'l'.
- El arbol resultado debe estar balanceado.
- Un arbol esta balanceado si en cada nodo que no es hoja, la cantidad
- de elementos de su subarbol izquierdo es igual a, o 1 mas que, la cantidad
- de elementos de su subarbol derecho.
- Al finalizar debe haberse liberado toda la memoria asignada a 'l'.
- El tiempo de ejecucion es O(n . log n), siendo n = CantidadLista (l)
- (ver letra). *)
- VAR
- a: Binario;
- l2: ListaString;
- BEGIN
- IF CantidadLista(l) = 1 THEN
- IrInicioLista(l);
- a := CrearHoja(CrearInfo(0, ActualLista(l)));
- RemoverDeLista(l);
- ELSE
- l2 := PartirLista(l);
- IrInicioLista(l2);
- a := CrearHoja(CrearInfo(0, ActualLista(l2)));
- RemoverDeLista(l2);
- a^.izquierdo := Balanceado(l);
- a^.izquierdo^.padre := a;
- IF CantidadLista(l2) > 0 THEN
- a^.derecho := Balanceado(l2);
- a^.derecho^.padre := a;
- END;
- END;
- RETURN a;
- END Balanceado;
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement