;; 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. ;; (empty? BT) produce false (do not compare) ;; (and (left BT) (right BT)) compare right and left nodes and produce two recursivities ;; (left BT only) compare left node and produce recursivity ;; (right only) compare right node and produce recursivity ;; else compare and stop the recursivity (define (search-bt n a-bt) (cond [(empty? a-bt) false] [(and (not (equal? (node-left a-bt) false)) (not (equal? (node-right a-bt) false))) (cond [(equal? n (node-soc a-bt)) (node-pn a-bt)] [(boolean? (search-bt n (node-left a-bt))) (search-bt n (node-right a-bt))] [else (search-bt n (node-left a-bt))])] [(not (equal? (node-left a-bt) false)) (cond [(equal? n (node-soc a-bt)) (node-pn a-bt)] [else (search-bt n (node-left a-bt))])] [(not (equal? (node-right a-bt) false)) (cond [(equal? n (node-soc a-bt)) (node-pn a-bt)] [else (search-bt n (node-right a-bt))])] [else (cond [(equal? n (node-soc a-bt)) (node-pn a-bt)] [else false])])) (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)