scheme - 二叉树在里面搜索

Question

谁能告诉我我需要在这里做什么？

(define (count-values abst v)
  (cond [(empty? abst) 0]
        [else (+ (cond [(equal? v (bae-fn abst)) 1]
                       (else 0))
                 (count-values .... v)
                 (count-values .... v ))]))

我基本上需要一个函数来计算二叉树中符号 v 的数量

(define bae
  (make-bae '+
            (make-bae '* (make-bae '+ 4 1)
                      (make-bae '+ 5 2))
            (make-bae '- 6 3)))
(count-values bae '+) => 3

因为 bae 中有 3 '+

Answer 1

你需要：

1. 发布树的定义 - 我猜bae是一个结构 - 不要假设我们知道您的代码，将所有相关信息作为问题的一部分发布
2. 确保您发布的代码至少部分有效 - 例如，由于命名冲突，(define bae ...)即使您提供了 的定义，该部分也不会有效bae
3. 按照遍历二叉树的秘诀，我敢打赌它在教科书中是对的

解决方案的总体思路是这样的，不看你到目前为止所做的代码的实际实现是我能给你的唯一帮助：

1. 如果树为空，则返回 0
2. 如果当前元素的值等于搜索到的值，加1；否则加 0
3. 无论哪种方式，将值添加到递归遍历左右子树的结果中

Answer 2

如果你递归定义你的数据结构，那么自然会出现递归计数算法：

;; Utils
(define (list-ref-at n)
  (lambda (l) (list-ref l n)))
(define (eq-to x)
  (lambda (y) (eq? x y)))

;; Data Type    
(define (make-bae op arg1 arg2)
  `(BAE ,op, arg1, arg2))
(define (bae? thing) 
  (and (list? thing) (eq? 'BAE (car thing)) (= 4 (length thing))))
(define bae-op   (list-ref-at 1))
(define bae-arg1 (list-ref-at 2))
(define bae-arg2 (list-ref-at 3))

;; Walk
(define (bae-walk func bae)  ;; 'pre-ish order'
  (if (not (bae? bae))
      (func bae)
      (begin
        (func (bae-op bae))
        (bae-walk func (bae-arg1 bae))
        (bae-walk func (bae-arg2 bae)))))

;; Count
(define (bae-count-if pred bae)
  (let ((count 0))
    (bae-walk (lambda (x) 
                 (if (pred x) 
                     (set! count (+ 1 count))))
              bae)
     count))

(define (bae-count-if-plus bae)
  (bae-count-if (eq-to '+) bae))

> bae
(BAE + (BAE * (BAE + 4 1) (BAE + 5 2)) (BAE - 6 3))

> (bae-count-if-plus bae)
3

;; Find
(define (bae-find-if pred bae)
  (call/cc (lambda (exit)
             (bae-walk (lambda (x)
                         (if (pred x) (exit #t)))
                       bae)
             #f)))