; COSC 152
; Fall 2006
; Dennis Brylow
;
; Lecture 7 Demo
; Binary Tree using our own representation.

; constructors

(define TREE 'tree)

(define make-tree
  (lambda (datum left right)
    (if (and (number? datum)
             (tree? left)
             (tree? right))
        (list TREE datum left right)
        'error)
    )
  )

(define make-tree-null
  (lambda () (list TREE)))


; predicates

(define tree-null?
  (lambda (t)
    (and (not (null? t))
         (eq? (car t) TREE)
         (null? (cdr t)))
    )
  )
 
(define tree?
  (lambda (t)
    (and  (not (null? t))
          (eq? (car t) TREE)
          (or
           (and
            (= (length t) 4)
            (number? (cadr t))
            (tree? (caddr t))
            (tree? (cadddr t)))
           (null? (cdr t))))
    )
  )
                 

; accessors


(define tree-datum
  (lambda (t)
    (cond
     ((not (tree? t)) 'error-non-tree)
     ((tree-null? t) 'error-null-tree)
     (else (cadr t)))
    )
  )

(define tree-left
  (lambda (t)
    (cond
     ((not (tree? t)) 'error-non-tree)
     ((tree-null? t) 'error-null-tree)
     (else (caddr t)))
    )
  )

(define tree-right
  (lambda (t)
    (cond
     ((not (tree? t)) 'error-non-tree)
     ((tree-null? t) 'error-null-tree)
     (else (cadddr t)))
    )
  )

; Usefulness

(define add-tree
  (lambda (num t)
    (cond
      ((not (tree? t)) 'error)
      ((tree-null? t) (make-tree num t t))
      (else (if (< num (tree-datum t))
                ;left
                (make-tree (tree-datum t) 
                           (add-tree num (tree-left t))
                           (tree-right t))
                ;right
                (make-tree (tree-datum t)
                           (tree-left t)
                           (add-tree num (tree-right t))))))
    )
  )
                    
(define search-tree
  (lambda (num t)
    (cond
      ((not (tree? t)) 'error)
      ((tree-null? t) #f)
      ((= num (tree-datum t)) #t)
      ((< num (tree-datum t)) (search-tree num (tree-left t)))
      (else (search-tree num (tree-right t))))
    )
  )