scheme - 将树表示为列表

Question

我应该编写一个函数来计算给定树中的叶子数量。在编写算法之前，我想确定我的表示。

对于这棵树，我的表示是:

(define liste 
    (list '5 (list '1 (list '8) (list '2 (list '1) (list '9))) (list '10) 
    (list '4 (list '9))))

正确吗？

我的另一个问题是这个函数除了 list 之外还需要任何参数吗？

顺便说一句，我知道我不需要每次都写list，但这对我来说看起来更清楚。

编辑:

(define (howmany L)
    (if (empty? L) 
        0
        (if (= (length L) 1)
            (+ 1 (howmany (cdr L)))
            (if (= (length (car (cdr L))) 1)
                (+ 1 (howmany (cdr L)))
                (howmany (cdr L))))))

当我调用 (howmany (list-ref liste 1)) 时，它返回 2。但是，它应该返回 3。(8, 1, 9)

当我调用(howmany (list-ref liste 2))时，它返回1。很好。

当我调用(howmany (list-ref liste 3))时，它返回2。它应该返回1。(只有9)

我的错误是什么？

Answer 1

缩进表达式以模仿树的图形表示表明您的表达式是正确的:

(define liste 
  (list 5 
        (list 1 
              (list 8) 
              (list 2 
                    (list 1) 
                    (list 9)))
        (list 10) 
        (list 4 
              (list 9))))

获得结构等效值的更短方法是:

      '(5
        (1
         (8)
         (2
          (1)
          (9)))
        (10)
        (4
         (9)))

你的sum-of-leaves函数不需要更多参数，但如果你想使用累加器，你可以这样写:

(define (sum tree)
  (sum-it tree 0))

(define (sum-it tree sum-so-far)
   ...)