Двоичные деревья в схеме

Question

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

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

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

b. Определите процедуру (лист подсчета т), который возвращает число листьев в т

> (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)) 

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

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

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

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

Вот что я до сих пор:

;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)))))) 

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

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

Answer 3

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

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

(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)))))))) 

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