89 lines
1.7 KiB
Plaintext
89 lines
1.7 KiB
Plaintext
;;Miguel Muniz
|
|
|
|
;; 1)
|
|
|
|
(define (subst x y L)
|
|
;;(newline)
|
|
;;(display L)
|
|
(cond ((null? L) L)
|
|
(cond (eq? (car L) x) ; if head of list is equal to x
|
|
(cons y (subst x y (cdr L)))) ;
|
|
(else (cons (car L) (subst x y (cdr L))))))
|
|
|
|
|
|
> (subst 'c 'k '(c o c o n u t))
|
|
(k o k o n u t)
|
|
|
|
;; 2)
|
|
|
|
(define (all-different? L)
|
|
(cond ((null? L) #t)
|
|
((member (car L) (cdr L)) #f)
|
|
(else (all-different? (cdr L)))))
|
|
|
|
(define (member x L))
|
|
(cond ((null? L) #f)
|
|
((eq? x (car L)) #t)
|
|
(else (member x (cdr L)))))
|
|
|
|
;; 3)
|
|
|
|
;; tree
|
|
(define T
|
|
'(13
|
|
(5
|
|
(1 () ())
|
|
(8 ()
|
|
(9 () ())))
|
|
(22
|
|
(17 () ())
|
|
(25 () ()))))
|
|
|
|
;; other functions
|
|
(define (left T)
|
|
(cond (= (length T) 1)
|
|
(car (cdr T))
|
|
))
|
|
|
|
(define (right T)
|
|
(cond (= (length T) 1)
|
|
(car (cdr (cdr T)))
|
|
))
|
|
|
|
(define (val T)
|
|
(car T))
|
|
|
|
;; a)
|
|
|
|
(define (n-nodes T))
|
|
(cond ((null? T) 0) ; if empty
|
|
(else (+ (n-nodes (left T)) (n-nodes (right T)) 1))))
|
|
|
|
;; b)
|
|
(define (n-leaves T))
|
|
(cond ((null? T) 0)
|
|
((= n-nodes T) 1) 1) ;; leaf
|
|
(else (+ (n-leaves (left T)) (n-leaves (right T))))))
|
|
|
|
;; c)
|
|
(define (height T)
|
|
(cond ((null? T) 0)
|
|
((> (n-leaves (left T)) (n-leaves (right T)))
|
|
(+ (height (left T)) 1))
|
|
((<= (n-leaves (left T)) (n-leaves (right T)))
|
|
(+ (height (right T)) 1))))
|
|
|
|
;; d)
|
|
(define (postorder T))
|
|
(cond ((null? T) '())
|
|
((null? (cdr T)) (list (car T)))
|
|
(else (append (postorder (car T)) (postorder (cdr T))))))
|
|
|
|
|
|
;; 4)
|
|
|
|
(define (flatten L)
|
|
(cond ((null? L) '())
|
|
((null? (cdr L)) (list (car L)))
|
|
(else (append (car L) (flatten (cdr L))))))
|