clojure - 计算树数据结构的深度 - 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))