scheme - 方案中的二叉树

Question

我如何计算一棵树有多少个节点？

;;; 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，我应该在虚线中放入什么类型的函数？

Answer 1

这有点类似于您处理列表的方式。区别？现在您将前往每个节点的“左侧”和“右侧”，而不是仅前往“休息区”。除此之外，同样的想法也适用：

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

正如我在问题中看到的那样，您的基本情况是正确的。递归案例很简单！记住，当我们在列表中添加元素时，我们是如何组合结果的？这里是一样的，只是我们结合了左子树和右子树的结果。