ArbolBinario.lsp

;;;;;;;;;;;;;;;;;;
;;;; Arboles binarios de busqueda

;; Constructor
(define (cons-arbol nodo rama-i rama-d)
    (list nodo rama-i rama-d))

;; Selectores
(define (nodo ab)
    (first ab))

(define (rama-i ab)
    (second ab))

(define (rama-d ab)
    (third ab))

;; El arbol vacio
(define el-arbol-vacio ())

;; predicado para reconocer un arbol binario vacio
(define (arbol-vacio? ab)
    (null? ab))

;;;;;;;

(define (adjunta x ab)
    (cond ((arbol-vacio? ab) (cons-arbol x el-arbol-vacio el-arbol-vacio))
	          ((= x (nodo ab)) ab)
		          ((< x (nodo ab)) (cons-arbol (nodo ab)
						                                            (adjunta x (rama-i ab))
											                                         (rama-d ab)))
			          ((> x (nodo ab)) (cons-arbol (nodo ab)
							                                            (rama-i ab)
												                                         (adjunta x (rama-d ab))))))

(define (pertenece? x ab)
    (cond ((arbol-vacio? ab) #f)
	          ((= x (nodo ab)) #t)
		          ((< x (nodo ab)) (pertenece? x (rama-i ab)))
			          (else (pertenece? x (rama-d ab)))))

(define (lista->arbol lista)
    (lista->arbol-aux lista el-arbol-vacio))

(define (lista->arbol-aux l arbol)
    (if (null? l)
            arbol
	          (lista->arbol-aux (cdr l) (adjunta (car l) arbol))))


(define (arbol->lista ab)
    (if (arbol-vacio? ab)
            ()
	          
	          (append (arbol->lista (rama-i ab))
			                (list (nodo ab))
					              (arbol->lista (rama-d ab)))))

(define (lista long talla) ;; construye una lista de longitud long de n?meros en el intervalo [0,talla)
  (if (= long 0)
          ()
	        (cons (random talla) (lista (- long 1) talla))))