1 ;; The first three lines of this file were inserted by DrScheme. They record metadata
2 ;; about the language level of this file in a form that our tools can easily process.
3 #reader(lib "htdp-intermediate-reader.ss" "lang")((modname 14.2.1) (read-case-sensitive #t) (teachpacks ((lib "draw.ss" "teachpack" "htdp") (lib "arrow.ss" "teachpack" "htdp"))) (htdp-settings #(#t constructor repeating-decimal #f #t none #f ((lib "draw.ss" "teachpack" "htdp") (lib "arrow.ss" "teachpack" "htdp")))))
4 ;A binary-tree (BT) is either
5 ;1. false or
6 ;2. a structure (make-node s n l r)
7 ;where s is a number, n is a symbol,
8 ;and l and r are BTs.
9 ;
10 ;A node is a structure
11 ;(make-node s n l r) where
12 ;s is a number, n is a symbol,
13 ;and l and r are BTs.
14 
15 (define-struct node (ssn name left right))
16 ;
17 ;Template
18 ;fun-for-BT : BT -> ???
19 ;(define (fun-for-BT a-BT)
20 ;  (cond
21 ;    [(false? a-BT) ...]
22 ;    [else
23 ;     ... (node-ssn a-BT) ...
24 ;     ... (node-name a-BT) ...
25 ;     ... (fun-for-BT (node-left a-BT)) ...
26 ;     ... (fun-for-BT (node-right a-BT)) ...]))
27 ;
28 ;contains-bt : number BT -> boolean
29 ;If a-num is in a-BT, then returns true.
30 ;Otherwise, returns false.
31 
32 (define (contains-bt a-num a-BT)
33   (cond
34     [(false? a-BT) false]
35     [else
36      (or (= a-num (node-ssn a-BT))
37          (contains-bt a-num (node-left a-BT))
38          (contains-bt a-num (node-right a-BT)))]))
39 
40 (define BT64 (make-node 64 'Pete false false))
41 (define BT39 (make-node 39 'Matt false false))
42 (define BT27 (make-node 27 'Ron false false))
43 (define BT92 (make-node 92 'Jim false false))
44 (define BT87 (make-node 87 'Sam BT64 BT39))
45 (define BT24 (make-node 24 'Bob BT27 BT92))
46 (define BT15 (make-node 15 'Joe BT87 BT24))
47 
48 ;search-bt : number BT -> symbol/false
49 ;Find the node in a-BT with ssn n and return
50 ;the node's name.  Otherwise, return false.
51 
52 (define (search-bt a-num a-BT)
53   (cond
54     [(false? a-BT) false]
55     [else
56      (cond
57        [(= a-num (node-ssn a-BT)) (node-name a-BT)]
58        [(contains-bt a-num (node-left a-BT))
59         (search-bt a-num (node-left a-BT))]
60        [(contains-bt a-num (node-right a-BT))
61         (search-bt a-num (node-right a-BT))])]))
62 ;
63 ;BST Invariant
64 ;
65 ;A binary search tree is a proper subclass of binary
66 ;trees.  The following are BSTs:
67 ;
68 ;1. false and
69 ;2. (make-node soc name left right) where
70 ;a. left and right are BSTs,
71 ;b. (node-ssn left) is less than soc,
72 ;c. (node-ssn right) is greater than soc.
73 ;
74 ;A list-of-numbers is either
75 ;1. empty or
76 ;2. (cons n lon) where n is a number and lon is a list-of-numbers
77 ;(alternatively written as (list n1 n2 ...))
78 
79 ;inorder2 : BT -> list-of-numbers
80 ;Given a-BT, extract all the ssn from each node
81 ;to form a list-of-numbers
82 ;and sort the resulting list.
83 
84 (define (inorder2 a-BT)
85   (cond
86     [(false? a-BT) (list)]
87     [else (sort-list (extract a-BT))]))
88 
89 ;extract : BT -> list-of-numbers
90 ;Given a-BT, extract all the ssn values of
91 ;each node and put them in a list.
92 ;    
93 (define (extract a-BT)
94   (cond
95     [(false? a-BT) (list)]
96     [else 
97      (append (list (node-ssn a-BT))
98              (extract (node-left a-BT))
99              (extract (node-right a-BT)))]))
100 
101 ;sort-list : list-of-numbers -> list-of-numbers.
102 ;
103 ;Given a-list, sort the list and return
104 ;as a new list-of-numbers.  Do this
105 ;by inserting the first number
106 ;in the proper position in the
107 ;sorted remainder of the list. (insertion-sort)
108 
109 (define (sort-list a-list)
110   (cond
111     [(empty? a-list) (list)]
112     [else (insert (first a-list) (sort-list (rest a-list)))]))
113 
114 ;insert : number list-of-numbers -> list-of-numbers
115 ;Given a-number and a-lon, insert a-number in the
116 ;proper position in a-lon to produce a list-of-numbers
117 ;in ascending order.
118 
119 (define (insert a-number a-lon)
120   (cond
121     [(empty? a-lon) (list a-number)]
122     [else
123      (cond
124        [(<= a-number (first a-lon)) (append (list a-number)
125                                             a-lon)]
126        [(> a-number (first a-lon)) (append (list (first a-lon))
127                                            (insert a-number (rest a-lon)))])]))
128 
129 
130 ;search-bst : number BST -> symbol/false
131 ;Given a-BST, find the node with ssn a-number
132 ;and return the node's name.  Otherwise, return false.
133 ;Start with the node's ssn.  If a-number matches
134 ;the ssn, return the name of the node.
135 ;If a-number is larger than the ssn, repeat the search
136 ;on the right node. If a-number is less than the ssn,
137 ;repeat the search on the left node.  If the node
138 ;is false, return false.
139 
140 (define (search-bst a-number a-BST)
141  (cond
142    [(false? a-BST) false]
143    [else
144     (cond
145       [(= a-number (node-ssn a-BST)) (node-name a-BST)]
146       [(> a-number (node-ssn a-BST)) (search-bst a-number (node-right a-BST))]
147       [(< a-number (node-ssn a-BST)) (search-bst a-number (node-left a-BST))])]))
148 
149 ;(define BST06 (make-node 6 'Pete false false))
150 ;(define BST18 (make-node 18 'Matt false false))
151 ;(define BST31 (make-node 31 'Ron false false))
152 ;(define BST43 (make-node 43 'Jim false false))
153 ;(define BST57 (make-node 57 'Sam false false))
154 ;(define BST69 (make-node 69 'Bob false false))
155 ;(define BST81 (make-node 81 'Joe false false))
156 ;(define BST93 (make-node 93 'Bill false false))
157 ;(define BST12 (make-node 12 'Don BST06 BST18))
158 ;(define BST37 (make-node 37 'Carl BST31 BST43))
159 ;(define BST63 (make-node 63 'Hank BST57 BST69))
160 ;(define BST87 (make-node 87 'Frank BST81 BST93))
161 ;(define BST25 (make-node 25 'Will BST12 BST37))
162 ;(define BST75 (make-node 75 'Greg BST63 BST87))
163 ;(define BST50 (make-node 50 'Lars BST25 BST75))
164 
165 (define BST10 (make-node 10 'Pete false false))
166 (define BST24 (make-node 24 'Matt false false))
167 (define BST99 (make-node 99 'Ron false false))
168 (define BST15 (make-node 15 'Jim BST10 BST24))
169 (define BST77 (make-node 77 'Sam false false))
170 (define BST95 (make-node 95 'Bob false BST99))
171 (define BST29 (make-node 29 'Joe BST15 false))
172 (define BST89 (make-node 89 'Bill BST77 BST95))
173 (define BST63 (make-node 63 'Don BST29 BST89))
174 
175 ;
176 ;create-bst : BST number symbol -> BST
177 ;Creates a new BST from B, N, and S.  This
178 ;new BST replaces one false node with
179 ;(make-node N S false false).
180 ;(Note: other nodes in the former BST B
181 ;       must link to this new node)
182 
183 (define (create-bst B N S)
184   (cond
185     [(false? B) (make-node N S false false)]
186     [else
187      (cond
188        [(< N (node-ssn B))
189         (make-node (node-ssn B)
190                    (node-name B)
191                    (create-bst (node-left B) N S)
192                    (node-right B))]
193        [(> N (node-ssn B))
194         (make-node (node-ssn B)
195                    (node-name B)
196                    (node-left B)
197                    (create-bst (node-right B) N S))]
198        [(= N (node-ssn B))
199         (error 'create-bst "cannot duplicate index")])]))
200 
201 ;To create tree A using only create-bst:
202 
203 (create-bst
204  (create-bst
205   (create-bst
206    (create-bst
207     (create-bst
208      (create-bst
209       (create-bst
210        (create-bst
211         (create-bst false 63 'Don)
212         29 'Mike)
213        89 'John)
214       15 'Will)
215      10 'Mitchell)
216     24 'Pete)
217    77 'Larry)
218   95 'Frank)
219  99 'Lars)
220 
221 ;Data Definition
222 ;
223 ;A list-of-names/numbers (lonn) is either
224 ;1. empty or
225 ;2. (cons (list ssn name) lonn) where ssn is a number,
226 ;name is a symbol, and lonn is a list-of-names/numbers (lonn).
227 ;
228 ;(alternatively written as (list (list ssn1 name1)
229 ;                                (list ssn2 name2) ...))
230 ;               
231 ;create-bst-from-list : lonn -> BST
232 ;
233 ;Given a-lonn, create a BST from the
234 ;list-of-names/numbers.
235 
236 (define (create-bst-from-list a-lonn)
237   (cond
238     [(empty? a-lonn) false]
239     [else (create-bst (create-bst-from-list (rest a-lonn))
240                       (first (first a-lonn))
241                       (first (rest (first a-lonn))))]))
242 
243 (define sample
244   '((99 o)
245     (77 l)
246     (24 i)
247     (10 h)
248     (95 g)
249     (15 d)
250     (89 c)
251     (29 b)
252     (63 a)))