Hailperin, Chapter 8

Slide, Trees

Demo

> (car '((a b) (c d) (e f)))
> (cdr '((a b) (c d) (e f)))
> (caar '((a b) (c d) (e f)))
> (cadr '((a b) (c d) (e f)))
> (cdar '((a b) (c d) (e f)))
> (cddr '((a b) (c d) (e f)))
> (append '(a b c) '(d e f))
> (list 'a 'b 'c)
> (list '(a b c) '(d e f))

Slide, The definition of a tree

Slide, my-tree

(define my-tree '(4 (2 (1 () ()) (3 () ())) (6 (5 () ()) (7 () ()))))

;(4
; (2
;  (1 () ())
;  (3 () ()))
; (6
;  (5 () ())
;  (7 () ())))

Demo

> (make-empty-tree)
> (make-nonempty-tree 4 () ())
> my-tree
> (make-nonempty-tree 99 () my-tree)
> (root my-tree)
> (left-subtree my-tree)
> (right-subtree my-tree)

Write make-empty-tree

(define make-empty-tree
  (lambda ()
    '()))

Write make-nonempty-tree

(define make-nonempty-tree
  (lambda (root left-subtree right-subtree)
    (list root left-subtree right-subtree)))

Write empty-tree?

(define empty-tree?
  null?)

Write root

(define root
  car)

Write left-subtree

(define left-subtree
  cadr)

Write right-subtree

(define right-subtree
  caddr)

Slide, Definition of binary search tree (BST)

Demo

> my-tree
> (in? 6 my-tree)
> (in? 99 my-tree)

Write in?

(define in?
  (lambda (value tree)
    (cond
      ((empty-tree? tree) #f)
      ((= value (root tree)) #t)
      ((< value (root tree))
       (in? value (left-subtree tree)))
      (else ; the value must be greater than the root
       (in? value (right-subtree tree))))))

Slides, Preorder traversal

> (preorder my-tree)

Write preorder with append

(define preorder ;with append
  (lambda (tree)
    (if (empty-tree? tree)
        '()
        (cons (root tree)
              (append (preorder (left-subtree tree))
                      (preorder (right-subtree tree)))))))

preorder-onto is more efficient

> (preorder-onto my-tree '(a b c))

Write preorder with a single call to preorder-onto

(define preorder ;without append
  (lambda (tree)
    (preorder-onto tree '())))

Slide, preorder-onto

Write preorder-onto

(define preorder-onto
  (lambda (tree lst) ;Returns the preorder of tree appended to lst
    (if (empty-tree? tree)
        lst
        (cons (root tree)
              (preorder-onto (left-subtree tree)
                             (preorder-onto (right-subtree tree)
                                            lst))))))

Slide, inorder traversal

> (inorder my-tree)

Write inorder with append

(define inorder ;with append
  (lambda (tree)
    (if (empty-tree? tree)
        '()
        (append (inorder (left-subtree tree))
                (cons (root tree) 
                      (inorder (right-subtree tree)))))))

It is an exercise for the student to write inorder-onto

Demo

> (number? '(a b c))
> (number? 'a)
> (number? 7)

Slide, Definition of an expression tree, my-expression

(define my-expression
  '(1 + (2 * (3 - 5))))
 
Demo

> (constant? 7)
> (constant? my-expression)

Write constant?
 
(define constant?
  number?)

Demo

> (operator my-expression)
> (left-operand my-expression)
> (right-operand my-expression)

Write operator, left-operand, right-operand

(define operator
  cadr)

(define left-operand
  car)

(define right-operand
  caddr)

Demo

> +
> '+
> *
> '*
> (look-up-value '+)
> (look-up-value '*)
> (look-up-value '-)
> (look-up-value '/)
> (define my-symbol '@)
> my-symbol
> (equal? my-symbol '@)
> (equal? my-symbol '+)

Write look-up-value

(define look-up-value
  (lambda (name)
    (cond ((equal? name '+)
           +)
          ((equal? name '*)
           *)
          ((equal? name '-)
           -)
          ((equal? name '/)
           /)
          (else (error "Unrecognized name" name)))))

Demo

> (evaluate my-expression)

Write evaluate

(define evaluate
  (lambda (expr)
    (if (constant? expr)
        expr
        ((look-up-value (operator expr))
         (evaluate (left-operand expr))
         (evaluate (right-operand expr))))))