计算树数据结构的深度 - clojure

Question

我正在尝试通过 Clojure Zippers 实现一种算法来查找序列表达式的深度。

(zip/seq-zip (+ 1 (* 2 3)))

这就是我解释要转换为树数据结构的序列的方式。有没有直接的方法通过 Zipper 库来计算这个（深度计算为 2，从给定的例子）？

如有任何建议，我们将不胜感激！

Answer 1

您可以使用以下递归方法：

(defn height [s-expr]
  (if-let [sub-trees (seq (filter coll? s-expr))]
    (inc
     (apply max
            (map height sub-trees)))
    0))


=> (height '(+ 1 (* 2 3)))
=> 1

有效地将集合视为分支，将其他所有内容视为叶子。您可以将 coll? 替换为适合您需要的任何其他分支定义（例如 list?）。

Answer 2

您可能想要计算树的最小高度和最大高度。在这种情况下，您可以扩展以包含 comp 函数参数以确定该选择标准。

;; Compute the height (either min or max, according to the `comp` function)
;; of the tree `tree`. Trees must be expressed as nested sequences.
(defn height
  [tree comp]
  (if (coll? tree)
    (inc (apply comp (map #(height % comp) tree)))
    0))

(defn max-height [tree] (height tree max))
(defn min-height [tree] (height tree min))

计算树数据结构的深度 - clojure

Calculating the depth of a tree data structure - clojure

clojure

zipper

s-expression