;; 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.
;; examples
;(make-node 15 'd false (make-node 24 'i false false))
;; Draw a tree:
(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)))))
;; 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 treeA)
