一千萬個為什麽

搜索

計劃中的二叉樹

考慮以下BNF定義數字樹。 請註意,樹可以是葉子,具有一個子樹的節點1或節點-2 有兩個子樹。

tree ::= (’leaf number)
| (’node-1 tree)
| (’node-2 tree tree)

一個。為這些樹上的遞歸過程編寫模板。

灣定義返回的過程(leaf-count t) t中的葉子數量

> (leaf-count ’(leaf 5))

1

> (leaf-count ’(node-2 (leaf 25) (leaf 17)))

2

> (leaf-count ’(node-1
(node-2 (leaf 4)
(node-2 (leaf 2) (leaf 3)))))

3

這是我到目前為止所擁有的:

;define what a leaf, node-1, and node-2 is
(define leaf list)
(define node-1 list)
(define node-2 list)

;procedure to decide if a list is a leaf or a node
(define (leaf? tree) (number? (car tree)))
(define (node? tree) (pair? (car tree)))

(define (leaf-count tree)
 (cond ((null? tree) 0)
        ((number? tree) 0)
        ((leaf? tree) 1)
        (else (+ (leaf-count (car tree))
                 (leaf-count (cdr tree))))))

它看起來應該運行得很好,但是當我嘗試使用簡單的測試用例來運行它時

(leaf-count '(leaf 5))

我收到以下錯誤消息:

car:期望類型對的參數;給葉子

這個錯誤信息是什麽意思?我將葉子定義為列表。但由於某種原因,它沒有看到,並給了我錯誤信息。

最佳答案

實際上,解決其他人的任務很有趣。

(define leaf-count
  (match-lambda 
   [(list 'leaf x)     1]
   [(list 'node-1 t)   (leaf-count t)]
   [(list 'node-2 l r) (+ (leaf-count l) (leaf-count r))]))

轉載註明原文: 計劃中的二叉樹