Программа на Лиспе для проверки, является ли двоичное дерево бинарным деревом поиска

Question

Напишите программу на Лиспе, чтобы проверить, является ли двоичное дерево бинарным деревом поиска.

Левое поддерево узла имеет ключ, меньший или равный ключу его родительского узла. Правое поддерево узла имеет ключ больше, чем ключ его родительского узла.

Список может использоваться для представления структуры двоичного дерева следующим образом: '(8 (3 (1 () ()) (6 (4 () ())( 7 () ()))) (10 (()) (14 (13) ()))) где это вернет true.

Я пытаюсь написать бинарный рекурсивный подход, но я новичок и понятия не имею, куда идти дальше.

(defun isBST (L)
   (cond 
         ((null (first L)) t)
         ((and (not (null (caadr L)) ) (< (first L) (caadr L)) )  nil)
         ((and (not (null (caaddr L))) (> (car L) (caaddr L)))  nil)
         ((and (not (isBST (cadr L))) (not (isBST (caddr L)))) ))
  )

Answer 1

Вот схема схемы, которая может вам помочь.

(define (is-bst l)
  (define (loop node proc)
    (if (null? node)
        #t
        (and (proc (car node))
             (loop (cadr node)
                   (curry > (car node)))
             (loop (caddr node)
                   (curry < (car node))))))
  (loop l (const #t)))

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

(is-bst '(8 (3 (1 () ())
               (6 (4 () ())
                  (7 () ())))
            (10 ()
                (14 (13 () ())
                    ()))))

;; #t

Сделайте недействительным один из узлов, чтобы is-bst обнаружил не bst.

(is-bst '(8 (3 (1 () ())
               (6 (4 () ())
                  (7 () ())))
            (10 ()
                (2 (13 () ()) ;; 14 changed to 2; invalid tree
                   ()))))

;; #f

Чтобы сделать небольшое улучшение, обратите внимание, что мы позвонили (car node) три раза в процедуре выше. Этого следует избегать с использованием let.

(define (is-bst l)
  (define (loop node proc)
    (if (null? node)
        #t
        (let ((value (car node)))
          (and (proc value)
               (loop (cadr node)
                     (curry > value))
               (loop (caddr node)
                     (curry < value))))))
  (loop l (const #t)))

---

Другим интересным способом является использование потоков , которые могут быть легко реализованы с использованием основных процедур. Мы могли бы написать общую traverse процедуру для обхода наших деревьев.

(define (traverse bst)
  (if (null? bst)
      empty-stream
      (stream-append (traverse (cadr bst))
                     (stream (car bst))
                     (traverse (caddr bst)))))

(define tree
  '(8 (3 (1 () ())
               (6 (4 () ())
                  (7 () ())))
            (10 ()
                (14 (13 () ())
                    ()))))

(stream->list (traverse tree))
;; '(1 3 4 6 7 8 10 13 14)

Теперь мы пишем is-bst, чтобы просто проверить, что значения выводятся в порядке возрастания.

(define (is-bst l)
  (define (loop x s)
    (if (stream-empty? s)
        #t
        (let ((y (stream-first s)))
          (and (< x y)
               (loop y (stream-rest s))))))
  (loop -inf.0
        (traverse l)))


(is-bst tree)
; #t

(is-bst '(1 (2 () ())
            (3 () ())))
; #f

Поскольку используется поток, значения выходят лениво. Если раннее #f найдено, итерация потока останавливается, и вычисление заканчивается.

Answer 2

Вы можете выразить свои определения в коде, чтобы сделать вашу жизнь проще.

Узел представлен в виде списка трех вещей: ключ, левое поддерево и правое поддерево.

(defun node-key (node)
  (first node))

(defun node-left-subtree (node)
  (second node))

(defun node-right-subtree (node)
  (third node))

Чтобы дерево было бинарным деревом поиска, должны быть выполнены четыре условия, если оба поддерева не пусты:

• левое поддерево должно быть бинарным деревом поиска
• правильное поддерево должно быть бинарным деревом поиска
• самый большой ключ левого поддерева (если имеется) должен быть меньше корневого ключа
• наименьший ключ правого поддерева (если имеется) должен быть больше корневого ключа

Примечание: соглашение об именах в Лиспе заключается в том, чтобы писать все строчными буквами, с частями слов, разделенными черточками. Предикат, я. е. функция, которая используется для получения значения истинности, оканчивается на p. Предикат для двоичного дерева поиска может называться bst-p или binary-search-tree-p. Функция для получения наибольшего ключа bst может называться bst-largest-key.

Чтобы получить самый большой (наименьший) ключ BST, вам нужно выполнить рекурсию только на правом (левом) поддереве.