Упорядоченное дерево

@orangefridge · Регистрация: 12.12.2015

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

Здравствуйте! Прошу помощи в решении следующей задачи:
Определите функцию (ordered Tree), проверяющую является бинарное дерево Tree упорядоченным деревом целых чисел, т. е. число, стоящее в любой вершине дерева, больше любого элемента в левом поддереве и меньше любого элемента в правом поддереве. Указание. Можно использовать вспомогательные функции (ordered_left X Tree) и (ordered_right X Tree), которые проверяют, что X меньше (больше) всех чисел в вершинах левого (правого) поддерева дерева Tree и дерево Tree - упорядочено.

Lisp
1
2
3
4
5
6
7
8
9
10
11
(defun f (list)
    (setq l '>)
    (setq m '<)
    (cond ((funcall l(cadr(car (car list)))(cadr(car list))) nil );2>4
       ((funcall l(cadr(car list))(cadr(caddr(car list))) ) nil );4>8
       ((funcall l(cadr(caddr list))(cadr(caddr(caddr list)) )) nil ); 9>10
        ((funcall l(cadr(car (caddr list)))(cadr(caddr list)) ) nil);8>9
      ((funcall l(cadr(car list))(cadr list) ) nil);4>7
        ((funcall m(cadr list)(cadr(caddr list)) ) T)));7<9
 
(print (f '(((nil 7 nil) 4 (nil 5 nil)) 7 ((nil 8 nil) 9 (nil 117 nil)))))

Как изменить программу, чтобы можно было проверить дерево с большим или меньшим количеством уровней?

@Catstail · 30.11.2018, 14:27

Дерево хранится так: (Значение Левое-поддерево Правое-поддерево)

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
(defun is-ordered(tree)
 (cond ((null tree) t)
       ((and (null (cadr tree)) (null (caddr tree))) t)
       ((null (cadr tree)) (and (> (caaddr tree) (car tree)) (is-ordered (caddr tree))))
       ((null (caddr tree)) (and (< (caadr tree) (car tree)) (is-ordered (cadr tree))))
       (t (and (> (caaddr tree) (car tree))
              (< (caadr tree) (car tree))
              (is-ordered (caddr tree))
              (is-ordered (cadr tree))))))
 
==> IS-ORDERED
 
(is-ordered '(5 (3 nil nil) (9 nil nil)))
==> T
 
(is-ordered '(5 (3 (4 nil nil) nil) (9 nil nil)))
==> NIL
 
(is-ordered '(5 (3 (2 nil nil) nil) (9 nil nil)))
==> T

Новые блоги и статьи Все статьи Все блоги /
Установка Qt Creator для C и C++: ставим среду, CMake и MinGW без фреймворка Qt 8Observer8 05.04.2026 Среду разработки Qt Creator можно установить без фреймворка Qt. Есть отдельный репозиторий для этой среды: https:/ / github. com/ qt-creator/ qt-creator, где можно скачать установщик, на вкладке Releases:. . .	AkelPad-скрипты, структуры, и немного лирики.. testuser2 05.04.2026 Такая программа, как AkelPad существует уже давно, и также давно существуют скрипты под нее. Тем не менее, прога живет, периодически что-то не спеша дополняется, улучшается. Что меня в первую очередь. . .	Отображение реквизитов в документе по условию и контроль их заполнения Maks 04.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеСпецтехники", разработанного в конфигурации КА2. Данный документ берёт данные из другого нетипового документа. . .	Фото всей Земли с борта корабля Orion миссии Artemis II kumehtar 04.04.2026 Это первое подобное фото сделанное человеком за 50 лет. Снимок называют новым вариантом легендарной фотографии «The Blue Marble» 1972 года, сделанной с борта корабля «Аполлон-17». Новое фото. . .
Вывод диалогового окна перед закрытием, если документ не проведён Maks 04.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: реализовать программный контроль на предмет проведения документа. . .	Программный контроль заполнения реквизитов табличной части документа Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: 1. Реализовать контроль заполнения реквизита. . .	wmic не является внутренней или внешней командой Maks 02.04.2026 Решение: DISM / Online / Add-Capability / CapabilityName:WMIC~~~~ Отсюда: https:/ / winitpro. ru/ index. php/ 2025/ 02/ 14/ komanda-wmic-ne-naydena/	Программная установка даты и запрет ее изменения Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: при создании документов установить период списания автоматически. . .

Упорядоченное дерево

Решение