exam14.2.6

;; 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.

;; A binary-search-tree (short: BST) is a BT:
;; 1. false is always a BST;
;; 2. (make-node soc pn lft rgt) is a BST if
;;    a. lft and rgt are BSTs;
;;    b. all ssn numbers in lft are smaller than soc, and
;;    c. all ssn numbers in rgt are larger than soc.

;; A list-of-number/name is either
;; 1. empty or
;; 2. (cons (list ssn nom) lonn)
;; where ssn is a number, nom a symbol, and lonn is a list-of-number/name.



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

;; create-bst :  BST n s -> BST
;; to create a new BST by adding a new node with n s
(define (create-bst a-bt n s)
  (cond
    [(false? a-bt) (make-node n s false false)]
    [else
     (cond
       [(= n (node-ssn a-bt)) (error "change a new ssn")]
       [(< n (node-ssn a-bt))
        (make-node (node-ssn a-bt) (node-name a-bt)
                   (create-bst (node-left a-bt) n s)
                   (node-right a-bt))]
       [else
        (make-node (node-ssn a-bt) (node-name a-bt)
                   (node-left a-bt)
                   (create-bst (node-right a-bt) n s))])]))

;; test
;(create-bst false 66 'a)
;(create-bst (create-bst (create-bst (create-bst false 66 'c) 77 'a) 53 'b) 88 'd)

;;
(define treeA1
  (create-bst
   (create-bst
    (create-bst
     (create-bst
      (create-bst
       (create-bst
        (create-bst
         (create-bst
          (create-bst false 63 'a) 29 'b) 15 'c) 10 'd) 24 'e) 89 'f) 77 'g) 95 'h) 99 'i))

;;test
;; inorder : BT -> list-of-numbers
;; to produce a list of all the ssn in a-bt
(define (inorder a-bt)
  (cond
    [(false? a-bt) empty]
    [else
     (append
      (cons (node-ssn a-bt) empty)
      (inorder (node-left a-bt))
      (inorder (node-right a-bt)))]))

;; test
;(inorder treeA1)

;; create-bst-from-list : list-of-number/name -> BST
;; to produce a BST from a-lonn
(define (create-bst-from-list a-lonn)
  (cond
    [(empty? a-lonn) false]
    [else
      (create-bst  (create-bst-from-list (rest a-lonn)) (first (first a-lonn)) (second (first a-lonn)))]))
;; test
(define sample