Поиск узлов на глубине N в дереве с ракеткой
Я написал фрагмент кода, который возвращает узлы, находящиеся на глубине N дерева. Корень считается на глубине 1.
#lang racket
(define (depth n tree) (
cond [(= n 1) (car tree)]
[(> n 1) (
cond [(and (null? (cadr tree)) (null? (caddr tree)))
(null)]
[(and (not (null? (cadr tree))) (null? (caddr tree)))
(cons (depth (- n 1) (cadr tree)) null)]
[(and (null? (cadr tree)) (not (null? (caddr tree))))
(cons (depth (- n 1) (caddr tree)) null)]
[(and (not (null? (cadr tree))) (not (null? (caddr tree))))
(cons (depth (- n 1) (cadr tree)) (depth (- n 1) (caddr tree)))]
)]
)
)
Что отлично работает для глубины 1, 2 и 3.
(define sampleTree
`(A
(B
(D () ())
(E () ())
)
(C
()
(F
(G () ())
()
)
)
)
)
(depth 1 sampleTree)
(depth 2 sampleTree)
(depth 3 sampleTree)
дает
'A
'(B . C)
'((D . E) F)
Но по какой-то причине это не работает для глубины 4.
(depth 4 sampleTree)
application: not a procedure;
expected a procedure that can be applied to arguments
given: '()
Честно говоря, я понятия не имею, почему это происходит. Кажется, что null в первой ветви > n 1 применяется к чему-то.
Приветствуется любая помощь в отладке этого кода.
Что такое null в Racket? Это функция? Что происходит, когда вы пытаетесь вызвать нефункцию, как если бы она была функцией?
Извините за отступ, исправил по DrRacket. Я подумал, что null — это то, как я могу вернуть пустой список, я не хотел называть это функцией. Но теперь понял! Большое спасибо!
Это переформатирование не совсем то, на что я надеялся. Я думаю, он не очень хорошо обрабатывает открывающую скобку, находящуюся в строке, отличной от первого элемента s-expr. Ответ Питера имеет более типичное форматирование.
![Учебная записка [Medium] Leetcode#22 Generate Parentheses](https://i.imgur.com/Hl2feR7b.png)
Ответы 2
Проблема в (null). null привязан к значению '(). Заключив его в круглые скобки, мы пытаемся применить его как процедуру.
> null
'()
> (null)
application: not a procedure;
expected a procedure that can be applied to arguments
given: '()
[,bt for context]
Могу ли я предложить следующее форматирование кода:
(define (depth n tree)
(cond
[(= n 1) (car tree)]
[(> n 1)
(cond
[(and (null? (cadr tree)) (null? (caddr tree))) '()]
[(and (not (null? (cadr tree))) (null? (caddr tree)))
(cons (depth (- n 1) (cadr tree)) null)]
[(and (null? (cadr tree)) (not (null? (caddr tree))))
(cons (depth (- n 1) (caddr tree)) null)]
[(and (not (null? (cadr tree))) (not (null? (caddr tree))))
(cons (depth (- n 1) (cadr tree)) (depth (- n 1) (caddr tree)))])]))
Вы также можете спросить себя, какой тип значения должен возвращать depth. В выводе вашего примера 'A — это символ, '(B . C) — пара, а '((D . E) F) — правильный список (с парой в качестве первого элемента).
Как указал Питер, ваш результат со всеми неправильными парами, вероятно, не тот, что вам нужен - правильный список значений имеет больше смысла. Вот версия, которая дает это, используя list и append вместо cons:
#lang racket/base
(require racket/list) ; For first, second, etc.
;;; Use functions to access parts of the tree structure to be clearer about what's being looked at
;;; and to make it easier to change to a struct or other more efficient implementation.
(define (node-value node)
(first node))
(define (node-left-child node)
(second node))
(define (node-right-child node)
(third node))
(define (depth desired-depth head)
(cond
((= desired-depth 1)
(list (node-value head)))
((> desired-depth 1)
(append (if (null? (node-left-child head)) '() (depth (- desired-depth 1) (node-left-child head)))
(if (null? (node-right-child head)) '() (depth (- desired-depth 1) (node-right-child head)))))))
(define sampleTree
'(A
(B
(D () ())
(E () ()))
(C
()
(F
(G () ())
()))))
(depth 1 sampleTree) ; '(A)
(depth 2 sampleTree) ; '(B C)
(depth 3 sampleTree) ; '(D E F)
(depth 4 sampleTree) ; '(G)
Последовательный отступ и более стандартное форматирование сделали бы это намного легче для чтения. Если вы используете DrRacket, у него есть команда Reindent All в меню Racket, которая может помочь.