VPF::глубина списка и упорядоченность бинарного дерева

blackbanny

Дата 24.11.2010, 15:51 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 83
Регистрация: 18.11.2009

Репутация: нет
Всего: нет

вобщем есть такое задание:
 Определить функцию, вычисляющую глубину списка (самой глубокой ветви).
 Определить функцию для проверки упорядоченности бинарного дерева.

объясните пожалуйста мне про глубину списка(приведите примеры списков с разной глубиной) и хотя бы на словах про алгоритм проверки упорядоченности бинарного дерева(что такое упорядоченное бинарное дерево я знаю, только как на лиспе реализовать не пойму..)

VH_

Дата 25.11.2010, 10:57 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 182
Регистрация: 31.10.2006

Репутация: 10
Всего: 11

1)
По мотивам Хювёнен-Сеппянен "Мир Лиспа" т.1:

Код

(defun DEPTH (X) ; в оригинале ГЛУБИНА
 (cond
  ((atom X) 0) ; в оригинале 1
  (T (max (+ 1 (DEPTH (car X))) (DEPTH (cdr X))))))

Код

(defun F (tree)
 (cond
  ((null tree))
  ((apply
   '(lambda (node ltree rtree)
     (and
      (cond
       (ltree (< (car ltree) node))
       (T))
      (cond
       (rtree (> (car rtree) node))
       (T))
      (F ltree)
      (F rtree)))
    tree))))

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| LISP \| Следующая тема »