Двоичное дерево поиска в схеме

Question

У меня есть функция схемы, где у меня есть список, и я пытаюсь поместить числа в двоичное дерево поиска по одному. Тем не менее, я продолжаю получать «неуказанное возвращаемое значение»

(define (insertB L) 
    (if (not (null? L)) 
    (begin (let() BST (insert (car L) BST)) 
    (insertB (cdr L)) 
    ) 
    ) 
) 

Я знаю, что моя функция вставки работает для одного номера. Но мне нужно, чтобы insertB работал для списка.

Answer 1

Можете ли вы обобщить параметр BST следующим образом?

(define (insertB L BST) 
    (if (not (null? L)) 
    (insertB (cdr L) (insert (car L) BST)) 
    BST 
) 
) 

Или эквивалент:

(define (insertB L BST) 
    (if (null? L) 
    BST 
    (insertB (cdr L) (insert (car L) BST)) 
) 
) 

Я думаю, что это легче понять. Это также более общее.

Answer 2

Попробуйте это:

(define (insertB BST L) 
    (if (null? L) 
     BST 
     (insertB (insert (car L) BST) 
       (cdr L)))) 

Это лучше, если мы проходим BST в качестве параметра, вместо того, чтобы использовать глобальное определение. Кроме этого, вы должны убедиться в возврате измененного дерева, когда мы закончим перемещение списка (базовый регистр). Также обратите внимание, как при каждом рекурсивном вызове мы получаем insert текущий элемент в дереве и передаем его вместе, и в то же время мы переходим к следующему элементу в списке. Если разрешены процедуры более высокого порядка, мы можем написать более простое, эквивалентное решение:

(define (insertB BST L) 
    (foldr insert BST L))