我正在尝试从具有双重递归的方法返回一个列表(BST,二叉搜索树)。我正在尝试按如下方式实现它:
(define (mapBST BST someFunct)
(cond
[(null? BST)
'()]
[else (cons (car BST) (someFunct (car (cdr BST)))) (mapBST (car (cdr (cdr BST))) someFunct) (mapBST (car (cdr (cdr (cdr BST)))) someFunct) ]
)
)
这是用这段代码调用的
(define bst
'( 3 "3"
( 1 "1"
()
( 2 "2" () ())
)
( 5 "5" () () )
)
)
(mapBST bst string->number)
我也试过这段代码,但它返回了 ((() ()) ())
:
[else (printf (car (cdr BST))) (cons (mapBST (car (cdr (cdr BST))) someFunct) (mapBST (car (cdr (cdr (cdr BST)))) someFunct)) ]
结果应返回相同的 BST,但使用数字而不是字符串作为值。
最佳答案
在您的 else 表达式中,您没有正确地重建二叉搜索树,这就是您得到一个空列表的原因。将您的 else
案例更改为
...
[else
(cons (car BST)
(cons (someFunct (car (cdr BST)))
(cons (mapBST (car (cdr (cdr BST))) someFunct)
(cons (mapBST (car (cdr (cdr (cdr BST)))) someFunct) empty))))]
...
或
...
[else
(list (car BST)
(someFunct (car (cdr BST)))
(mapBST (car (cdr (cdr BST))) someFunct)
(mapBST (car (cdr (cdr (cdr BST)))) someFunct))]
...
将解决您的问题(两个选项产生相同的列表,因为 (cons 1 (cons 2 empty))
等同于 (list 1 2)
)。
这是 mapBST
的完整更新:
(define (mapBST proc BST)
(cond
[(null? BST) empty]
[else
(list (car BST)
(proc (cadr BST))
(mapBST proc (caddr BST))
(mapBST proc (cadddr BST)))]))
例如,
(define BST '(3 "3" (1 "1" () (2 "2" () ())) (5 "5" () ())))
(mapBST string->number BST)
=> '(3 3 (1 1 () (2 2 () ())) (5 5 () ()))
关于recursion - 使用 Racket 递归返回列表,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/43465299/