;; --------------------------------------------------------------------------------------------------- ;; PROBLEM: growing a binary search tree (BST), starting from a leaf, one step at a time (define-struct leaf ()) (define-struct branch (key info left right)) ;; A BST is one of: ;; -- (make-leaf) ;; -- (make-branch Natural String BST BST) ;; ------------------------------------------------------- ;; CONSTRAINT: in (make-branch n s t1 t2) ;; all numbers in t1 are __smaller__ than n and ;; all numbers in t2 are _greater_ to n ;; ------------------------------------------------------- (define LF (make-leaf)) ;; grow a BST from scratch ;; Key (Nat) Info (String) BST -> BST ;; placey key and info at proper place into given bst (define (grow a-key an-info a-bst) (cond [(leaf? a-bst) (make-branch a-key an-info LF LF)] [(branch? a-bst) (local ((define k (branch-key a-bst))) (cond [(= k a-key) (make-branch k an-info (branch-left a-bst) (branch-right a-bst))] [(< k a-key) ...] [(> k a-key) ...] (branch-info a-bst) (grow a-key an-info (branch-left a-bst)) (grow a-key an-info (branch-right a-bst)) ])) (check-expect (grow 10 "info" LF) (make-branch 10 "info" LF LF)) (check-expect (grow 11 "eleven" (make-branch 10 "info" LF LF)) (make-branch 10 "info" LF (make-branch 11 "eleven" LF LF))) (check-expect (grow 11 "happy" (make-branch 10 "info" LF (make-branch 11 "eleven" LF LF))) (make-branch 10 "info" LF (make-branch 11 "happy" LF LF))) (check-expect (grow 8 "halloween" (make-branch 10 "info" LF (make-branch 11 "eleven" LF LF))) (make-branch 10 "info" (make-branch 8 "halloween" LF LF) (make-branch 11 "eleven" LF LF))) ;; --------------------------------------------------------------------------------------------------- ;; PROBLEM: design the function 'navigate'. It consumes a binary tree and a list of directions ;; ('left, 'right). It extracts the sub-tree at the specified places, that is, for a 'growth', ;; it goes straight (because there is no choice), for a 'fork', it follows the next direction, ;; and if there are no more directions, it returns the given tree. ;; structure type definition (define-struct leaf ()) (define-struct growth (next)) (define-struct fork (left right)) ;; data definitions ;; Tree is one of: ;; -- (make-leaf) ;; -- (make-growth Tree) ;; -- (make-fork Tree Tree) ;; Direction is one of: ;; -- 'left ;; -- 'right ;; data examples (define LF (make-leaf)) (define t1 (make-growth LF)) (define t2 (make-fork t1 t1)) (define t3 (make-growth t2)) ;; Tree [List-of Direction] -> Tree ;; navigate a tree, following a list of directions (define (navigate t lod) (cond [(and (leaf? t) (empty? lod)) ...] [(and (leaf? t) (cons? lod)) ...] [(and (growth? t) (empty? lod)) ...] [(and (growth? t) (cons? lod)) (... (first lod) (navigate (growth-next t) (rest lod)) (navigate (growth-next t) lod) (navigate t (rest lod)) ...)] [(and (fork? t) (empty? lod)) ...] [(and (fork? t) (cons? lod)) ... (if (symbol=? (first lod) 'left) (navigate (fork-left t) (rest lod)) (navigate (fork-right t) (rest lod)))]))