Hierarchical Data and Trees

;; Trees as nested lists
(define tree '(1 (2 3) (4 (5 6))))

(define (count-leaves t)
  (cond ((null? t) 0)
        ((not (pair? t)) 1)
        (else (+ (count-leaves (car t)) (count-leaves (cdr t))))))
(count-leaves tree)             ; 6

(define (tree-map f t)
  (cond ((null? t) '())
        ((pair? t) (cons (tree-map f (car t)) (tree-map f (cdr t))))
        (else (f t))))
(tree-map square tree)          ; (1 (4 9) (16 (25 36)))

;; Binary search trees with records
(define-record-type node
  (make-node key left right)
  node?
  (key node-key)
  (left node-left)
  (right node-right))

(define (bst-insert tree k)
  (cond ((not tree) (make-node k #f #f))
        ((< k (node-key tree)) (make-node (node-key tree) (bst-insert (node-left tree) k) (node-right tree)))
        ((> k (node-key tree)) (make-node (node-key tree) (node-left tree) (bst-insert (node-right tree) k)))
        (else tree)))

(define (bst->list tree)
  (if (not tree)
      '()
      (append (bst->list (node-left tree)) (list (node-key tree)) (bst->list (node-right tree)))))

(bst->list (fold-left* bst-insert #f '(5 3 8 1 4)))   ; (1 3 4 5 8) using fold-left* from Module 11

;; Sequences as conventional interfaces (
…