Проверка упорядоченности двоичного дерева

@PetrovP · Регистрация: 17.12.2015

Author24 — интернет-сервис помощи студентам

Дано S-выражение, представляющее дерево вида "(РебенокЛевый Родитель РебенокПравый)" с числами в качестве вершин. Определить функцию для проверки упорядоченности бинарного дерева, т.е. возвращающая Т, если дерево упорядочено, Nil -нет.

Например, если дано '(((nil 1 nil) 5 (nil 7 nil)) 10 (nil 15 (nil 16 nil))), ответом будет "Т".

@Catstail · 17.12.2015, 15:54

Lisp

(defun is-ordered (tree)
  (cond ((null tree) t)
        (t (let ((v      (cadr tree))
                 (l-tree (car tree))
                 (r-tree (caddr tree)))
             (cond ((and l-tree r-tree) 
                    (and (>= v (cadr l-tree))
                         (<= v (cadr r-tree))
                         (is-ordered l-tree)
                         (is-ordered r-tree)))
                   (l-tree (and (>= v (cadr l-tree)) (is-ordered l-tree)))
                   (r-tree (and (<= v (cadr r-tree)) (is-ordered r-tree)))
                   (t t)))))) 
 
==> is-ordered
 
(is-ordered '(((nil 1 nil) 5 (nil 7 nil)) 10 (nil 15 (nil 1 nil))))
 
==> NIL
 
(is-ordered '(((nil 1 nil) 5 (nil 7 nil)) 10 (nil 15 (nil 16 nil))))
 
==> T

@PetrovP 2 / 2 / 0 Регистрация: 17.12.2015 Сообщений: 20
		1
	Проверка упорядоченности двоичного дерева 17.12.2015, 13:30. Показов 1036. Ответов 1 Метки нет (Все метки) Дано S-выражение, представляющее дерево вида "(РебенокЛевый Родитель РебенокПравый)" с числами в качестве вершин. Определить функцию для проверки упорядоченности бинарного дерева, т.е. возвращающая Т, если дерево упорядочено, Nil -нет. Например, если дано '(((nil 1 nil) 5 (nil 7 nil)) 10 (nil 15 (nil 16 nil))), ответом будет "Т". 0

	17.12.2015, 15:54

Опции темы