Засоби та принципи програмування на Ліспі

(DEFUN INSL (lst tree)

((NULL lst) tree)

(SETQ tree (insel (car lst) tree))

(INSL (CDR lst) tree) )

Наступні дві функції виконують обхід дерева: PUD (Print Up-Down) — обхід згори вниз, PLR (Print Left-Right) — обхід зліва направо.

(DEFUN PUD (tree) (DEFUN PLR (tree)

((NULL tree)) ((NULL tree))

(PRIN1 (CAR tree)) (SPACES 3) (PLR (CADR tree))

(PUD (CADR tree)) (PRIN1 (CAR tree)) (SPACES 3)

(PUD (CDDR tree)) ) (PLR (CDDR tree)) )

Функція REVT (Reverse Tree) обертає дерево: кожне праве піддерево стає лівим піддеревом і навпаки.

(DEFUN REVT (tree)

((NULL tree) NIL)

(CONS (CAR tree) (CONS (REVT (CDDR tree)) (REVT (CADR tree)))) )

Розглянемо приклади:

$ (SETQ a (INSL ‘(5 1 7 3 9 2 4 8 10) NIL))$ (SETQ b (REVT a))

$ (PLR a)$ (PLR b)

1 2 3 4 5 7 8 9 10 T 10 9 8 7 5 4 3 2 1

Функція HEIGHT обчислює висоту дерева. Вважатимемо, що висота порожнього дерева дорівнює 0. Висота непорожнього дерева дорівнює максимумові між висотами лівого та правого піддерев плюс одиниця. (HEIGHT a) = 4, де a взято з попереднього прикладу.

(DEFUN HEIGHT (tree)

((NULL tree) 0)

(MAX (ADD1 (HEIGHT (CADR tree)))

(ADD1 (HEIGHT (CDDR tree)))) )

6. Робота з файлами

По замовченню за пристрій потокового вводу (CIS - Current Input Stream) береться консоль.