eharetea

Binary trees, binary search trees, and algorithms for searching these trees.

Binary trees, binary search trees, and algorithms for searching these trees.

Date Created:Friday October 10th, 2008 06:35 PM
Date Modified:Friday October 10th, 2008 06:38 PM

(define (make-tree datum left right) (list datum left right))
(define left-branch cadr)
(define right-branch caddr)
(define datum car)

(define (all? pred tree val)
   (or (null? tree)
       (and
           (all? pred (right-branch tree) val)
           (all? pred (left-branch tree) val)
           (pred (datum tree) val)
       )
   )
)

(define my-tree (make-tree 5 (make-tree 8 '() '()) (make-tree 12 '() '())))
(define my-tree2 (make-tree 5 (make-tree 12 '() '()) (make-tree 8 '() '())))
;; this is the only bst
(define my-tree3 (make-tree 10 (make-tree 8 '() '()) (make-tree 12 '() '())))

;; TESTS FOR BINARY SEARCH TREES
(define (bst? tree)
  (or
   (null? tree)
   (and
    (all? > (right-branch tree) (datum tree))
    (all? < (left-branch tree) (datum tree))
    (bst? (right-branch tree))
    (bst? (left-branch tree))
   )
  )
)

Binary Trees by Dan Lynch
is licensed under a Creative Commons Attribution-Noncommercial-Share Alike 3.0 United States License
Based on a work at www.3daet.com
Permissions beyond the scope of this license may be available at http://www.3daet.com