;--------- BST procedures fromm HW7, some slightly modified ------------- (define BST-node list) (define (BST-leafnode n) ; make a new leaf node (BST-node n (empty-BST) (empty-BST))) ; Accessors for part of a node (define BST-element car) (define BST-left cadr) (define BST-right caddr) ; empty tree functions (define (empty-BST) '()) ; make one (define empty-BST? null?) ; test one (define (BST? obj) ; Is this object a BST? (or (empty-BST? obj) (and (tree? obj) (let ([inorder-list (BST-inorder obj)]) (and (set? inorder-list) (sorted? inorder-list)))))) (define (BST-insert num bst) (cond [(empty-BST? bst) (BST-leafnode num)] [(not (integer? num)) (error 'BST-insert "attempt to insert non-integer into BST")] [(= num (BST-element bst)) bst] [(< num (BST-element bst)) (BST-node (BST-element bst) (BST-insert num (BST-left bst)) (BST-right bst))] [else (BST-node (BST-element bst) (BST-left bst) (BST-insert num (BST-right bst)))])) (define (BST-preorder bst) (if (empty-BST? bst) '() (append (list (BST-element bst)) (BST-preorder (BST-left bst)) (BST-preorder (BST-right bst))))) (define (BST-inorder bst) (if (empty-BST? bst) '() (append (BST-inorder (BST-left bst)) (list (BST-element bst)) (BST-inorder (BST-right bst))))) (define (BST-contains? bst num) (cond [(empty-BST? bst) #f] [(= (BST-element bst) num) #t] [(< (BST-element bst) num) (BST-contains? (BST-right bst) num)] [else (BST-contains? (BST-left bst) num)])) (define (BST-height bst) (if (empty-BST? bst) -1 (+ 1 (max (BST-height (BST-left bst)) (BST-height (BST-right bst))))))