exam14.2.2

;; mht created on Nov 17, 2011

;; data definition :
(define-struct node (ssn name left right))
;; A binary-tree (short : BT) is either
;; 1. false; or
;; 2. (make-node soc pn lft rgt)
;; shere soc is a number, pn js a symbol, and lft and rgt are BTs.

;; examples
(make-node
 15 'd false (make-node 24 'i false false))

;; Draw two trees:
(define treeA
  (make-node 63 'a
           (make-node 29 'b
                      (make-node 15 'c
                                 (make-node 10 'd false false)
                                 (make-node 24 'e false false))
                      false)
           (make-node 89 'f
                      (make-node 77 'g false false)
                      (make-node 95 'h false
                                 (make-node 99 'i false false)))))

;; contains-bt : number a-bt -> boolean
;; to determines whether n occurs in a-bt
(define (contains-bt n a-bt)
  (cond
    [(false? a-bt) false]
    [else
     (cond
       [(= n (node-ssn a-bt)) true]
       [(contains-bt n (node-left a-bt)) true]
       [(contains-bt n (node-right a-bt)) true]
       [else false])]))

;; test
;(contains-bt 63 treeA)
;(contains-bt 99 treeA)
;(not (contains-bt 2 treeA))

;; search-bt : number BT -> symbol
(define (search-bt n a-bt)
  (cond
    [(false? a-bt) false]
    [else (cond
            [(= n (node-ssn a-bt)) (node-name a-bt)]
            [(contains-bt n (node-left a-bt)) (search-bt n (node-left a-bt))]
            [(contains-bt n (node-right a-bt)) (search-bt n (node-right a-bt))]
            [else false])]))

;; test
(symbol=? 'a (search-bt 63 treeA))
(symbol=?