方案中的二叉树 [英] Binary trees in scheme

问题描述

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

How would I count how many nodes a tree has?

;;; 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 我应该得到

so for tree1 I should get

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

我想我的模板是对的.如果是数字，则应返回1.但是如果它是一个node，我应该在虚线中放入什么类型的函数?

I think I got the template right. If it's a number, you should return 1. But if it's a node, what type of function should I put in the dotted lines?

推荐答案

这有点类似于您处理列表的方式.区别?现在你将去到每个节点的左边"和右边"，而不是只去休息".除此之外，同样的想法也适用:

This is somewhat similar to how you'd process a list. The difference? that now you'll go to the "left" and to the "right" of each node, instead of going just to the "rest". Other than that, the same ideas apply:

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

正如我在问题中所见，您的基本情况是正确的.递归的情况很简单！还记得，当我们在列表中添加元素时，我们是如何组合结果的?这是同样的事情，只是我们组合了来自左子树和来自右子树的结果.

You got the base case right, as I can see in the question. The recursive case is simple! remember, how did we combine the results when we were adding the elements in a list? here's the same thing, it's just that we combine the results from the left and from the right subtrees.

这篇关于方案中的二叉树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！