 Mapping Trees eharetea

Applying functions to trees recursively.

Applying functions to trees recursively.

Date Created:Friday October 03rd, 2008 06:35 PM
Date Modified:Tuesday October 14th, 2008 10:52 PM

```;; SQUARES ALL ELEMENTS OF A TREE

(define make-tree cons)
(define datum car)
(define children cdr)
(define square (lambda (x) (* x x)))

(define (square-tree tree)
(make-tree
(square (datum tree))
(square-forest (children tree))
)
)

(define (square-forest forest)
(if (null? forest)
'()
(cons
(square-tree (car forest))
(square-forest (cdr forest))
)
)
)```

```;; THIS ALLOWS A MORE MODULAR APPROACH IN THAT
;; YOU CAN PASS IN ANY FUNCTION TO BE APPLIED

(define make-tree cons)
(define datum car)
(define children cdr)

(define (fn-tree fn tree)
(make-tree
(fn (datum tree))
(fn-forest fn (children tree))
)
)

(define (fn-forest fn forest)
(if (null? forest)
'()
(cons
(fn-tree fn (car forest))
(fn-forest fn (cdr forest))
)
)
)```

```;; COUNTS LEAVES OF A TREE

(define (count-leaves tree)
(if (null? (children tree))
1
(apply + (map count-leaves (children tree)))))
```

```;; THIS IS USED TO RETURN THE MAXIMUM AMOUNT
;; OF CHILDREN OF ANY TREE OR SUB-TREE

(define make-tree cons)
(define children cdr)
(define datum car)

(define (max-span tree)
(max (length (children tree)) (max-span-forest (children tree)))
)

(define (max-span-forest children)
(if (null? children)
0
(max (max-span (car children)) (max-span-forest (cdr children)))
)
)

;; USING ACCUMULATE
(define (spanmax tree)
(accumulate max (length (children tree)) (map spanmax (children tree))))

(define my-tree (make-tree 5 (list (make-tree 3 '()) (make-tree 5 '()) (make-tree 4 '()))))
```

```;; returns the maximum value of a tree
;; The zero in the base case of max-of-forest
;; assumes that we are taking the maximum of
;; the set of positive integers

(define datum car)
(define children cdr)

(define (max-of-tree tree)
(max (datum tree) (max-of-forest (children tree)))
)

(define (max-of-forest children)
(if (null? children)
0
(max (max-of-tree (car children)) (max-of-forest (cdr children)))))

;; RETURNS THE MAXIMUM VALUE OF THE SUM OF A PATH OF A TREE

(define (maxpath tree)
(if (null? (children tree))
(datum tree)
(+ (datum tree)
(maxpath-forest (children tree)))))
(define (maxpath-forest forest)
(if (null? (cdr forest))
(maxpath (car forest))
(maxpath-forest (cdr forest)))))

;; USING MAP

(define (maxpath tree)
(if (null? (children tree))
(datum tree)
(+ (datum tree)
(apply max (map maxpath (children tree))))))``` 