Arbol Binario Scheme

Para realizar esta implementación, me base en códigos de Scheme publicados en la página :  http://paradigmas.firebirds.com.ar/

 ;Ejercicio de Recorrer Arboles Binarios en INORDEN


; Ejemplo de USO
; (inorden '(Papi(HijoIzquierdo (A (E () ()) (F () ()))(B (g () ()) (h () ()))) (HijoDerecho (C () ()) (D () ()))))
; O para definir solamente el arbol.
; arbol? '(Papi(HijoIzquierdo () ()) (HijoDerecho () ()))
; Para tener en cuenta -> DEBE DE MANTERSE LA RELACIÓN DE LISTAS.




;Útiles

;Define el == y el !=

(define != (lambda (N1 N2) (not (= N1 N2))))
(define == (lambda (N1 N2) (= N1 N2)))

; Define si no es nulo
(define notnull? (lambda (E) (not (null? E))))


;Long -> Cantidad de elementos de una lista

(define long (lambda (L)
(if (null? L) 0 (+ 1 (long (cdr L))))))
;Concatena Dos Listas
(define concatenar (lambda(L1 L2)
(if(null? L1) L2 (cons (car L1) (concatenar (cdr L1)L2)))))

;Definición de los atributos del árbol

(define raiz (lambda (A) (car A)))

(define izq (lambda (A) (cadr A)))

(define der (lambda (A) (caddr A)))

(define hoja? (lambda (A) (if (and (null? (izq A)) (null? (der A))) #t #f)))

;Definición de Nodo

(define nodo? (lambda (C) (or (number? C) (symbol? C))))

;Definición del árbol

(define arbol? (lambda (A)
(cond ((null? A) #t)
((nodo? A) #f)
((!= (long A) 3) #f)
(else (and (nodo? (car A))
(arbol? (cadr A))
(arbol? (caddr A)))))))


; Inorden
(define inorden(lambda(A)
(if (not (arbol? A))#f
(if (null? A)'()
(if (and (nodo? A) (null? (cadr A)) (null? (caddr A)))
(car A)
(concatenar (concatenar (inorden(cadr A))
(list(car A))) (inorden(caddr A))))))))

 

Para poder ocuparlo simplemente : 

(inorden '(Papi(HijoIzquierdo (A (E () ()) (F () ()))(B (g () ()) (h () ()))) (HijoDerecho (C () ()) (D () ()))))

Lo que nos da como resultado :

(list ‘E ‘A ‘F ‘HijoIzquierdo ‘g ‘B ‘h ‘Papi ‘C ‘HijoDerecho ‘D)

Read More >Arbol Binario Scheme

Permutaciones en Scheme

Este programa en Scheme calcula todas las permutaciones de una lista dada.

;; Calcula todas las permutaciiones de una lista

;;Leyenda ->
;;Para el manejo de listas tenemos
;;car -> Lista que resulta al incluir un objero en una lista.
;;cdr -> Lista que resulta al quitarle el primer elemento a una lista
;;pair? -> Si el objeto es de tipo "Par Punteado" devuelve tru, en otro caso, devuelve false.
;;select ->
;;map (Seguido por proc) -> Se le aplica proc a cada elemento de la lista
(define (perm xs)
(if (pair? xs)
(select (car xs) '() (cdr xs))
'(())))

;;Selecciona X como primer elemento de la lista
;;Lo agrega a las permutaaciones de la lista que va quedando representada por la lista de los elementos antes de X.

(define (select x revprefix postfix)
(mapconsapp x (perm (revapp revprefix postfix))
(if (pair? postfix)
(select (car postfix)
(cons x revprefix)
(cdr postfix))
'())))

;; Hace un map de X en la lista de listas xss y concatena el resto.

(define (mapconsapp x xss rest)
(if (pair? xss)
(cons (cons x (car xss)) (mapconsapp x (cdr xss) rest))
rest))

;; Voltea Xs y concatena el resto.
(define (revapp xs rest)
(if (pair? xs)
(revapp (cdr xs) (cons (car xs) rest))
rest))

Para utilizarla simplemente la llamamos desde nuestro interprete de Scheme ( En mi caso DrScheme) de la siguiente manera;

 > (perm ‘(1 2 3 4))
(list
 (list 1 2 3 4)
 (list 1 2 4 3)
 (list 1 3 2 4)
 (list 1 3 4 2)
 (list 1 4 2 3)
 (list 1 4 3 2)
 (list 2 1 3 4)
 (list 2 1 4 3)
 (list 2 3 1 4)
 (list 2 3 4 1)
 (list 2 4 1 3)
 (list 2 4 3 1)
 (list 3 1 2 4)
 (list 3 1 4 2)
 (list 3 2 1 4)
 (list 3 2 4 1)
 (list 3 4 1 2)
 (list 3 4 2 1)
 (list 4 1 2 3)
 (list 4 1 3 2)
 (list 4 2 1 3)
 (list 4 2 3 1)
 (list 4 3 1 2)
 (list 4 3 2 1))

 

Espero que les sirva. A mi me sirvió bastante …. … Read More >Permutaciones en Scheme