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

Question

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

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

到目前为止，这是我对一个简单测试用例的了解：

(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)

Answer 2

这里有一个不同的解决方法：我们标记每个返回的叶值及其在其父项中的位置，然后按标记过滤：

(define (first-values tree)
  (filter-tag 0 (collect-leaf-values 0 tree)))

(define (second-values tree)
  (filter-tag 1 (collect-leaf-values 0 tree)))

现在，filter-tag 和 collect-leaf-values 函数：

(define (filter-tag tag tagged-list)
  (map cdr (filter (lambda (x) (= (car x) tag)) tagged-list)))

(define (leaf? x)
  (not (pair? x)))

(define (collect-leaf-values index tree)
  (if (leaf? tree)
      (list (cons index tree))
      (append-map collect-leaf-values '(0 1) tree)))

SRFI 1 已经定义了此时所需的一切。但是既然你说你只是在使用普通的 Scheme，那么让我们定义 filter 和 append-map（注意 append-map 使用 SRFI 1 也提供的 any——我们将定义一个这里也有简化版):

(define (filter pred lst)
  (cond ((null? lst) '())
        ((pred (car lst)) (cons (car lst) (filter pred (cdr lst))))
        (else (filter pred (cdr lst)))))

(define (any pred lst)
  (cond ((null? lst) #f)
        ((pred (car lst)) => values)
        (else (any pred (cdr lst)))))

(define (append-map func . lists)
  (let recur ((lists lists))
    (if (any null? lists)
        '()
        (append (apply func (map car lists)) (recur (map cdr lists))))))

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

Filtering for the same index on all nodes of a binary tree in Scheme?

lisp

tree

scheme

binary-tree

sicp