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

(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?)
Зад.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, използвайки само предишните две функции.
Зад.8+. Да се напише функция (valid-bst? t), която проверява дали дървото t е валидно двоично наредено дърво.
Зад.9. Да се напишат функции (parse-expression expr) и (tree-eval t) такива, че:
(parse-expression '(* (+ 3 4) 6)) -> връща дървото, съответстващо на този аритметичен израз, т.е. за този пример същото като
(define test
  (make-tree '*
            (make-tree '+
                       (make-leaf 3)
                       (make-leaf 4)) 
            (make-leaf 6)))
(tree-eval test) -> намира стойността на аритметичния израз по дървото, построено от горната функция (в случая: 42).
Допуснете, че изразът ще съдържа само операциите +,-,*,/.
Hint: Различавайте * от '*.

Последно модифициране: вторник, 22 ноември 2016, 10:17