我如何递归计算 Clojure 中树结构的深度？

Question

所以我对 Clojure 有了非常基本的了解，并且想计算使用包含向量本身的向量定义的树的深度。例如，[1 [2] [3 [4] ]] 表示一棵树，其中 1 是根，而 [2] 是 1 的子树，而 [3 [4]] 是子树。

(defn height[tree]
(if(empty? tree)
    (1); Base case
    (inc (apply max (map  height (next tree))))); Calculate the height for every subtree and return maximum
)

我在想这个方法会起作用，因为它应该递归地计算每个子树的深度到 return 最大值。但是，当我尝试运行此方法时，出现非法参数异常。

Answer 1

(1) 是错误的。它尝试将 1 作为函数执行。
你需要能够应付树上的叶子，这些叶子不是向量。
next 调用错误 - 将其删除。

尝试

(defn height [tree]
  (if (vector? tree)
   (if (empty? tree)
     1
     (inc (apply max (map height tree))))
    0))

例如，

(height [1 [2] [3 [4] ]]) ; 3

稍微简单一点的版本是

(defn height [tree]
  (if (vector? tree)
    (inc (apply max 0 (map height tree)))
    0))

通过向 max 提供 initial/default 参数 0，我们可以处理没有条件的空集合。

Answer 2

带拉链的尾部递归变体：

(require '[clojure.zip :as z])

(defn height-2 [tree]
  (loop [curr (z/zipper coll? seq nil tree) h 0]
    (if (z/end? curr) h
        (recur (z/next curr)
               (if (z/branch? curr) h
                   (-> curr z/path count (max h)))))))

回复：

user> (height-2 [1 [2] [3 [4] ]])
3
user> (height-2 (nth (iterate (partial vector 1) []) 1000))
1000
user> (height-2 (nth (iterate (partial vector 1) []) 100000))
100000

我如何递归计算 Clojure 中树结构的深度？

How can i recursively calculate the depth of a tree structure in Clojure?

tree

recursion

clojure