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