;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;; Trees ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; (define-struct branch (value next)) (define-struct fork (value left right)) ;; A Tree is one of: ;; - Symbol ;; - (make-branch Symbol Tree) ;; - (make-fork Symbol Tree Tree) ;; Examples (define t1 'a) (define t2 (make-branch 'foo t1)) (define t3 (make-fork 'a t1 t2)) (define t4 (make-fork 'dog t3 t2)) ; -------------------------------------------------------- ;; DESIGN height, which given a Tree, returns its height ;; height : Tree -> Natural (non-negative integer) ;; given t, return its height ;; A Natural is a non-negative integer ;; height : Tree -> Natural ;; What is th height of the given tree? (define (height t) (cond [(symbol? t) 0] [(branch? t) (add1 (height (branch-next t)))] [(fork? t) (add1 (max (height (fork-left t)) (height (fork-right t))))])) (check-expect (height t1) 0) (check-expect (height t2) 1) (check-expect (height t3) 2) (check-expect (height t4) 3) ; -------------------------------------------------------- ;; DESIGN tree=? ;; tree=? : Tree Tree -> Boolean ;; Is t1 equal to t2? (define (tree=? t1 t2) (cond [(and (symbol? t1) (symbol? t2)) (symbol=? t1 t2)] [(and (symbol? t1) (branch? t2)) false] [(and (symbol? t1) (fork? t2)) false] [(and (branch? t1) (symbol? t2)) false] [(and (branch? t1) (branch? t2)) (and (symbol=? (branch-value t1) (branch-value t2)) (tree=? (branch-next t1) (branch-next t2)))] [(and (branch? t1) (fork? t2)) false] [(and (fork? t1) (symbol? t2)) false] [(and (fork? t1) (branch? t2)) false] [(and (fork? t1) (fork? t2)) (and (symbol=? (fork-value t1) (fork-value t2)) (tree=? (fork-left t1) (fork-left t2)) (tree=? (fork-right t1) (fork-right t2)))])) (check-expect (tree=? t1 t1) true) (check-expect (tree=? t1 t2) false) (check-expect (tree=? t3 t4) false) (check-expect (tree=? t4 t4) true)