Функционално програмиране (И) 2018/2019

За удобство и консистентност ще използваме следните "стандартни" функции за работа с дървета:

(define (tree? t)
  (or (null? t)
      (and (list? t)
           (= (length t) 3))
           (tree? (cadr t))
           (tree? (caddr t))))
(define empty-tree '())
(define (make-tree root left right) (list root left right))      ; не искаме просто (define make-tree list) - защо?
(define (make-leaf root) (make-tree root empty-tree empty-tree)) ; за удобство
(define root-tree car)
(define left-tree cadr)
(define right-tree caddr)
(define empty-tree? null?)


(define t
  (make-tree 10
             (make-tree 7
                        (make-leaf 10)
                        (make-leaf 2))
             (make-tree 3
                        (make-tree 4
                                   (make-leaf 1)
                                   (make-leaf 2))
                        empty-tree)))

Зад.1. Да се напише функция (tree-sum t), която намира сумата на всички елементи на дървото t.

Зад.2. Да се напише функция (tree-max t), която намира максималния елемент на дървото t.
Упътване: в racket съществуват стойностите -inf.0 и +inf.0, use them wisely.

Зад.3. Да се напише функция (tree-level k t), която връща списък от всички стойности във възли на дълбочина k (тоест разстояние k от корена).

Зад.4. Да се напише функция (all-levels t), която връща списък от всички нива на дървото t, започвайки от нулевото надолу.

Зад.5. Да се напише функция (tree-map f t), която map-ва функцията f на всички стойности в дървото t.

Зад.6. Да се напише функция (tree->list t), която връща списък от всички елементи на дървото, получени при обхождане ляво-корен-дясно.

Зад.7. Да се напише функция (bst-insert val t), която вмъква стойността val в двоичното наредено дърво t.

Зад.8. Да се напише функция (tree-sort lst), която сортира списъка lst, използвайки само предишните две функции.

Зад.9. Да се напише функция (valid-bst? t), която проверява дали дървото t е валидно двоично наредено дърво.