用于检查叶属性的布尔函数

Question

考虑一棵树，每个节点都包含一个整数。在方案中，Tree 数据类型可以定义为

(define-type Tree
    [leaf (val : number)]
    [node (val : number)
          (left : Tree)
          (right : Tree)])

我想编写一个函数，给定一棵这样的树，returns #t 如果每个叶子都大于从根到叶子的节点路径中的数字总和。

我考虑的方法是将每个叶子的数量与从叶子到根的每个总和进行比较（即计算从叶子到根的每条路径的总和）。叶子编号小于或等于路径总和的第一条路径将我引向 return #f。否则我必须搜索每条路径。这是最有效的方法吗？深度优先搜索是实施该策略的最佳方式吗？

Answer 1

我觉得最方便的方式就是直接树递归，即深度优先，用一个参数来存储"the sum so far"。

伪代码：

(define (all-greater tree sum)
    (if the tree is a leaf 
        (> (val of tree) sum)
        (and (all-greater (left subtree of tree) (+ sum (val of tree)))
             (all-greater (right subtree of tree) (+ sum (val of tree))))))


(define (all-greater? tree) (all-greater tree 0))

用于检查叶属性的布尔函数

Boolean function to check for leaf properties

tree

scheme

depth-first-search