tree - 在 Scheme 的二叉树的所有节点上过滤相同的索引？

Question

这开始是对 SICP 练习 2.29 的误解，并成为个人的好奇心。看起来很简单我感到很尴尬我很难找到适用于所有情况的解决方案。显然我知道如何计算树上的节点以及如何将每个节点中的值枚举到一个列表中，但是这两种算法都无法帮助我过滤每个节点中的相同索引。

给定任何表示为嵌套列表的二叉树，其中每个节点包含一个或两个整数，应该有一个函数返回每个节点中第一个值的列表和一个返回每个节点中第二个值的函数(保持请记住，并非所有节点都有第二个值)。

到目前为止，这是一个简单的测试用例:

(define (first-values tree)
  (cond ((null? tree) '())
        ((not (pair? tree)) (list tree))
        (else (cons (car (first-values (car tree))) 
                    (first-values (car (cdr tree)))))))

(define (second-values tree)
  (cond ((null? tree) '())
        ((not (pair? tree)) (list tree))
        (else (cons (cdr (second-values (car tree)))
                    (second-values (car (cdr tree)))))))

(define (make-tree left right)
  (list left right))

(define test (make-tree 
              (make-tree 2 5) 
              (make-tree (make-tree 4 10) (make-tree 6 20))))

test
(first-values test)
(second-values test)

结果:

((2 5) ((4 10) (6 20)))
(2 4 6 20)
((5) (10) () 20)

如您所见，第一个函数不会过滤子列表中的值，而第二个函数会留下我需要使用枚举函数过滤掉的无关子列表。我真的尝试了我能想到的所有汽车和 cdr 变体，这是我最接近的。它清楚地表明我仍然不完全理解使用列表结构，即使它不是更简单示例的问题。

(供引用，我使用的是 R5RS)

Answer 1

经过一番摆弄，我最终得到了这个。希望对您有所帮助!

(define (first-values tree)
  (cond ((null? tree) '())
        ((not (pair? (car tree))) (list (car tree)))
        (else (append (first-values (car tree))
                      (first-values (cdr tree))))))

(define (second-values tree)
  (cond ((null? tree) '())
        ((not (pair? (car tree))) (cdr tree))
        (else (append (second-values (car tree))
                      (second-values (cdr tree))))))

使用您的测试数据:

(first-values test)
=> '(2 4 6)

(second-values test)
=> '(5 10 20)