; The below abstraction for binary trees is implemented with ; a function in order to force you to use selectors to inspect ; tree data in the interpreter. (define (make-bintree datum left right) (lambda (msg) (cond ((= msg 0) datum) ((= msg 1) left) ((= msg 2) right)))) (define (datum bintree) (bintree 0)) (define (left bintree) (bintree 1)) (define (right bintree) (bintree 2)) (define tet 'toasterhead) (define (empty-tree? tree) (eq? tree 'toasterhead)) (define (leaf? bintree) (and (not (empty-tree? bintree)) (empty-tree? (left bintree)) (empty-tree? (right bintree)))) (define bst (make-bintree 15 (make-bintree 6 (make-bintree 2 tet tet) tet) (make-bintree 22 (make-bintree 17 (make-bintree 16 tet tet) (make-bintree 19 tet tet)) (make-bintree 24 tet tet))))
0. Draw a picture of bst.
1. Write the function contains? which takes a binary search tree of numbers and a datum as its input and returns #t if the datum is in the tree, #f otherwise.
> (contains? bst 17) #t > (contains? bst 18) #f
2. Write the function inorder which takes a binary search tree as its input and returns a list of the data in ascending order.
> (inorder bst) (2 6 15 16 17 19 22 24)
3. Write the function count-nodes which takes a binary tree (does not have to be a binary search tree) as its input and returns the number of nodes in the tree.
> (count-nodes bst) 8
4. Write the function square-tree which takes a binary tree that contains numbers as its input and returns a binary tree with the same structure and the numbers squared.
> (datum (square-tree bst)) 225 > (datum (left (square-tree bst))) 36 > (datum (left (left (right (square-tree bst))))) 256