exam14.2.2

288阅读　0评论2011-11-18　maunix
分类：LINUX

  1. ;; mht created on Nov 17, 2011

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

  10. ;; examples
  11. (make-node
  12.  15 'd false (make-node 24 'i false false))

  14. ;; Draw two trees:
  15. (define treeA
  16.   (make-node 63 'a
  17.            (make-node 29 'b
  18.                       (make-node 15 'c
  19.                                  (make-node 10 'd false false)
  20.                                  (make-node 24 'e false false))
  21.                       false)
  22.            (make-node 89 'f
  23.                       (make-node 77 'g false false)
  24.                       (make-node 95 'h false
  25.                                  (make-node 99 'i false false)))))

  27. ;; contains-bt : number a-bt -> boolean
  28. ;; to determines whether n occurs in a-bt
  29. (define (contains-bt n a-bt)
  30.   (cond
  31.     [(false? a-bt) false]
  32.     [else
  33.      (cond
  34.        [(= n (node-ssn a-bt)) true]
  35.        [(contains-bt n (node-left a-bt)) true]
  36.        [(contains-bt n (node-right a-bt)) true]
  37.        [else false])]))

  39. ;; test
  40. ;(contains-bt 63 treeA)
  41. ;(contains-bt 99 treeA)
  42. ;(not (contains-bt 2 treeA))

  44. ;; search-bt : number BT -> symbol
  45. (define (search-bt n a-bt)
  46.   (cond
  47.     [(false? a-bt) false]
  48.     [else (cond
  49.             [(= n (node-ssn a-bt)) (node-name a-bt)]
  50.             [(contains-bt n (node-left a-bt)) (search-bt n (node-left a-bt))]
  51.             [(contains-bt n (node-right a-bt)) (search-bt n (node-right a-bt))]
  52.             [else false])]))

  54. ;; test
  55. (symbol=? 'a (search-bt 63 treeA))
  56. (symbol=?
上一篇：exam14.2.1
下一篇：exam14.2.3