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

Deja un comentario

This site uses Akismet to reduce spam. Learn how your comment data is processed.