9-22-22.rkt

;; CIS352 -- Fall 2022
#lang racket

;; An S-expression or "structured" expression
;; is a list-like piece of data
(define x '(this is (an (s) expression)))

;; we define the tree? data type
;;
;; algebraic data types are called "algebraic" because they are
;; built using sum (ors/cond) and product (ands/list) types.
;; We can use cond to express this--soon in the course we will
;; see how "match" can encapsulate this more succinctly.
(define (tree? t)
  (cond
    [(equal? t 'empty) #t]
    [(and (list? t)
          (= (length t) 4)
          (equal? (first t) 'node)
          (number? (second t))
          (tree? (third t))
          (tree? (fourth t)))
     #t]
    [else #f]))

(define empty-tree 'empty)

(define (evaluate e)
  (pretty-print e))


;; check if the tree is empty
(define (empty? e)
  (equal? e 'empty))

;; for next three: assume '(node ...)
;; (node 2 empty empty)
(define (node-data t)
  (second t))

(define (left-subtree t)
  (third t))

(define (right-subtree t)
  (fourth t))

;; walk over the tree e, turn it into a list of its elements
(define/contract (tree->list t)
  (-> tree? any/c)
  ;; what possibilities are there for t?
  ;; - 'empty
  ;; - '(node n0 t0 t1) where t0 and t1 are trees  
  (if (empty? t)
      '()
      (let* ([data (node-data t)]
             [left (left-subtree t)]
             [right (right-subtree t)]
             ;; left elements as a list
             [left-elements (tree->list left)]
             [right-elements (tree->list right)])
        (append (list data) left-elements right-elements))))

(define (tree->string t)
  'todo)

(define (tree-insert t e)
  'todo)