简单的 Scheme 树深度计数

Question

我正在做 Simply Scheme 程序中的问题 18.3（页面底部的问题）： https://people.eecs.berkeley.edu/~bh/ssch18/trees.html 问题是写深度，程序表示returns一棵树最长分支的节点数。到目前为止我已经写了：

(define (depth-count node)
    (cond ((null? (children node))
     1)
    (else
     (reduce + (depth-count (children node)))))

所以我将基本情况作为 'leaf' 节点 - 没有子节点。我想为每个父节点 + 1 到一个叶子，然后比较相同深度的节点并从每个级别获取最大值的节点。我期望写更多的 cond 子句，这些子句将选择一个分支（最大节点）而不是另一个分支。我希望递归案例是一个我可以计算的列表......这就是我认为我被卡住的地方。我这样做是对的吗？非常感谢任何建议。

Answer 1

您正在计算节点的数量，而不是找到最长的分支 - 这与找到树的高度相同。为此，您想要递归地找到每个节点的树的 maximum 深度。像这样：

(define (depth-count node)
  (cond ((null? (children node)) 1) ; base case: if node is a leaf
        (else                       ; otherwise node has children
         (add1                                          ; add one
          (apply max                                    ; to the maximum of
                 (map depth-count (children node))))))) ; the recursive call

例如，如果我们将上述过程与给定 link 中定义的 world-tree 一起使用，我们将获得：

(depth-count world-tree)
=> 4

简单的 Scheme 树深度计数

Simply Scheme tree depth count

tree

scheme