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))))))

Mapping Trees by Dan Lynch
is licensed under a Creative Commons Attribution-Noncommercial-Share Alike 3.0 United States License
Based on a work at www.3daet.com
Permissions beyond the scope of this license may be available at http://www.3daet.com