Бинарные деревья в схеме

Question

Рассмотрим следующий BNF, определяющий деревья чисел. Обратите внимание, что дерево может быть либо листом, либо узлом 1 с одним поддеревом, либо узлом 2 с двумя поддеревьями.

tree ::= (’leaf number)
| (’node-1 tree)
| (’node-2 tree tree)

а. Напишите шаблон для рекурсивных процедур на этих деревьях.

б. Определите процедуру (счетчик листьев t), которая возвращает количество листьев в т

> (leaf-count ’(leaf 5))

1

> (leaf-count ’(node-2 (leaf 25) (leaf 17)))

2

> (leaf-count ’(node-1
(node-2 (leaf 4)
(node-2 (leaf 2) (leaf 3)))))

3

Вот что у меня есть:

;define what a leaf, node-1, and node-2 is
(define leaf list)
(define node-1 list)
(define node-2 list)

;procedure to decide if a list is a leaf or a node
(define (leaf? tree) (number? (car tree)))
(define (node? tree) (pair? (car tree)))

(define (leaf-count tree)
 (cond ((null? tree) 0)
        ((number? tree) 0)
        ((leaf? tree) 1)
        (else (+ (leaf-count (car tree))
                 (leaf-count (cdr tree))))))

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

(leaf-count '(leaf 5))

Я получаю следующее сообщение об ошибке:

car: ожидает аргумент типа пары; данный лист

Что означает это сообщение об ошибке? Я определяю лист как список. Но по какой-то причине он этого не видит и выдает мне это сообщение об ошибке.

Answer 1

Решать задания других людей - это действительно весело.

(define leaf-count
  (match-lambda 
   [(list 'leaf x)     1]
   [(list 'node-1 t)   (leaf-count t)]
   [(list 'node-2 l r) (+ (leaf-count l) (leaf-count r))]))

Answer 2

Вы указали лист, (leaf-count '(leaf 5)), так что это символ, а не переменная, которую вы определили ранее. Это причина ошибки, но не то, что вы должны исправить. Ваши три определения не имеют особого смысла, а ваши процедуры обнаружения листа или узла не соответствуют спецификации BNF.

Вот дерево из вашего собственного примера: ’(node-1 (node-2 (leaf 4) (node-2 (leaf 2) (leaf 3)))). Он указан так, что node-1, node-2 и leaf являются просто символами и не нуждаются в определении. Теперь напишите leaf? и node? функции, которые могли бы определять, что представляют собой различные элементы вышеприведенного дерева. Вот вам тест, в котором все вызовы функций должны возвращать true:

(define a-tree ’(node-1 (node-2 (leaf 4) (node-2 (leaf 2) (leaf 3)))))
(node? a-tree)
(node? (car (cdr a-tree)))
(leaf? (car (cdr (car (cdr a-tree)))))
(node? (car (cdr (cdr (car (cdr a-tree))))))
(leaf? (car (cdr (car (cdr (cdr (car (cdr a-tree))))))))

Как только это сработает, подсчет также не будет проблемой (хотя ваш текущий метод не сработает, я предлагаю написать функции left-поддерево и right-поддерево, чтобы помочь вам в этом).

Answer 3

Вот что у меня есть:

 ;define what a leaf, node-1, and node-2 is
(define leaf list)
(define node-1 list)
(define node-2 list)

;procedure to decide if a list is a leaf or a node
(define (leaf? tree) (number? (cadr tree)))
(define (node? tree) (pair? (cadr tree)))

(define (leaf-count tree)
 (cond ((null? tree) 0)
        ((number? tree) 0)
        ((leaf? tree) 1)
        (else (+ (leaf-count (car tree))
                 (leaf-count (cdr tree))))))

Я получил его для работы с незначительной корректировкой: измените условия, чтобы проверить кадры в списке, так как именно это содержит информацию. В этом случае машина списка - это просто метка того, что представляют собой данные (лист, узел и т. Д.). Не совсем. Я заставил его работать для самых основных тестовых случаев, но не для более сложных, таких как

(leaf-count '(node-2 (leaf 25) (leaf 17)))