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