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

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)

如您所见，第一个函数不会过滤子列表中的值，第二个函数会留下我需要使用枚举函数过滤掉的无关子列表。我真的尝试了我能想到的所有 car 和 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)