;; The first three lines of this file were inserted by DrScheme. They record metadata ;; about the language level of this file in a form that our tools can easily process. #reader(lib "htdp-beginner-abbr-reader.ss" "lang")((modname 14.2.2) (read-case-sensitive #t) (teachpacks ()) (htdp-settings #(#t constructor repeating-decimal #f #t none #f ()))) (define-struct node (soc pn left right)) (define A-Tree (make-node 63 'b (make-node 29 'a (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))))) (define B-Tree (make-node 63 'i (make-node 29 'h (make-node 15 'g (make-node 10 'f false false) (make-node 24 'e false false)) false) (make-node 89 'd (make-node 33 'c false false) (make-node 95 'b false (make-node 99 'a false false))))) ;; Exercise 14.2.2. Develop search-bt. The function consumes a number n and a BT. ;; If the tree contains a node structure whose soc field is n, the function produces ;; the value of the pn field in that node. Otherwise, the function produces false. ;; search-bt : number BT -> symbol or false ;; Use number n and a BT to compute, if the tree contains a node structure whose soc field is n, ;; the function produces the value of the pn field in that node. Otherwise, the function produces false. ; Data Definition ; (or (empty? TB) (equal? TB false)) ; (= n (node-soc TB)) (node-pn TB) ; else ; (boolean? (search-bt n (node-left TB))) ; else (search-bt n (node-left TB)) (define (search-bt n TB) (cond [(or (empty? TB) (equal? TB false)) false] [(= n (node-soc TB)) (node-pn TB)] [else (cond [(boolean? (search-bt n (node-left TB))) (search-bt n (node-right TB))] [else (search-bt n (node-left TB))])])) (equal? (search-bt 99 B-Tree) 'a) (equal? (search-bt 29 A-Tree) 'a) (equal? (search-bt 77 A-Tree) 'g) (equal? (search-bt 63 A-Tree) 'b) (equal? (search-bt 200 A-Tree) false) (equal? (search-bt 63 B-Tree) 'i) (equal? (search-bt 95 A-Tree) 'h) (equal? (search-bt 15 A-Tree) 'c)