2

ツリーに含まれるノードの数をどのように数えますか?

;;; A Binary is one of:
;;; - Number
;;; - (make-node BT BT)


(define-struct node (left right))

(define tree1 (make-node (make-node 10 9)
(make-node 3
(make-node 1 5))))

(define (how-many? nd)
  (cond
    [(number? nd)....]
    [(node? n)
     (..... (how-many? (node-left nd))
             (how-many? (node-right nd)))]))

したがって、tree1の場合は取得する必要があります

 (check-expect (how-many? tree1) 5)

テンプレは合ってると思う 数値の場合は、 を返す必要があります1。しかし、それが の場合node、どのタイプの関数を点線に入れる必要がありますか?

4

1 に答える 1

4

これは、リストを処理する方法と多少似ています。違い？これで、「残り」だけではなく、各ノードの「左」と「右」に移動します。それ以外は、同じアイデアが適用されます。

(define (how-many? nd)
  (cond
    [(number? nd) <???>] ; if it's a leaf, then how many numbers does it have?
    [(node? nd)
     (<???> (how-many? (node-left nd)) ; how do we combine the results?
            (how-many? (node-right nd)))]))

質問でわかるように、あなたは基本的なケースを正しく理解しています。再帰ケースは簡単です！リストに要素を追加するときに、どのように結果を結合したか覚えていますか? これは同じことです。左側のサブツリーと右側のサブツリーの結果を組み合わせているだけです。

于 2013-11-14T20:10:04.333 に答える