如何在Clojure中遍历一棵树，同时从每个节点节点收集值？

Question

我想创建一个函数来收集二叉树中每个节点的值。在ClojureDocs中，我找到了几个遍历tree/graph的函数，比如tree-seq、prewalk和postwalk。

https://clojuredocs.org/clojure.core/tree-seq

https://clojuredocs.org/clojure.walk/prewalk

https://clojuredocs.org/clojure.walk/postwalk

这些都可以用来累加遍历节点的值吗？作为 Clojure 新手，我不知道该怎么做。如果您知道如何（使用 Clojure 或类似的 Lispy 语言），请告诉我。理想情况下，Clojure 新手可以理解您的回答；-)

我的二叉树用这样的节点表示：（值左子右子）。例如：

( 2 (7 nil nil) (88 (5 nil nil) nil) )

在这个例子中，我希望函数为 return (2 7 88 5)。

注意：遍历方法并不重要。我只是想学习一种收集节点值的技术。

Answer 1

好吧，tree-seq 会给你节点序列（深度优先遍历）。然后您可以对其进行任何其他转换，包括 (map some-value-extractor-fn (tree-seq ... 以获取每个节点中的值。您只需要为该表示选择一个树表示和适当的函数，这样 tree-seq 就可以知道什么是内部节点以及它的 children 是什么。例如，使用您对树的定义作为嵌套列表：

嵌套列表树

我们的树可以分支的节点是列表，我们可以使用 list? 来识别它们。它们的 children 是第一个之后的值，即它们的 rest。所以我们可以只使用标准函数来定义 tree-seq：

(->> '( 2 (7 nil nil) (88 (5 nil nil) nil) )
     (tree-seq list? rest))

但这有一点垃圾 - 每个 nil 都作为 seq 的成员出现，我们感兴趣的每个值都出现在它的列表节点中并作为其自身的成员等等。我们可以用 filter 或 remove 清理它——例如我们可以丢弃所有叶值并只采用内部节点：

(->> '( 2 (7 nil nil) (88 (5 nil nil) nil) )
     (tree-seq list? rest)
     (filter list?))
;;=> ((2 (7 nil nil) (88 (5 nil nil) nil)) (7 nil nil) (88 (5 nil nil) nil) (5 nil nil))

然后 map first 超过那些：

(->> '( 2 (7 nil nil) (88 (5 nil nil) nil) )
     (tree-seq list? rest)
     (filter list?)
     (map first)) ;;=>(2 7 88 5)

或者我们可以尝试丢弃树的内部节点和 nil 节点，只取具有以下值的叶子：

(->> '( 2 (7 nil nil) (88 (5 nil nil) nil) )
     (tree-seq list? seq)
     (remove (some-fn list? nil?))) ;;=>(2 7 88 5)

请注意，在此策略中我必须使用 seq 而不是 rest，因为我希望列表中的第一个值也是该节点的 child。 (some-fn list? nil?) 是一些高阶函数 - 它构建了一个函数来检查输入是否满足谓词 either list? or nil?（或两者）。

嵌套地图树

如果你想要一个可能更通用的树定义，其中每个节点可以包含多个值加上可变数量的 children，你可以将你的树定义为嵌套映射：{:value 2 :children [{:value 7} {:value 88 :children [{:value 5}]}]}

在这种情况下，仅将地图视为节点通常是最简单的。我们可能的分支节点是地图 - 用 map? 检查它。我们将它们的 children 存储在键 :children 中，这是一个关键字，因此也是一个函数。我们使用该函数来获取 children。

(->> {:value 2 :children [{:value 7} {:value 88 :children [{:value 5}]}]} 
     (tree-seq map? :children)) 
;;=> ({:value 2, :children [{:value 7} {:value 88, :children [{:value 5}]}]} {:value 7} {:value 88, :children [{:value 5}]} {:value 5})

然后您只需要 map 遍历节点即可从中获取您想要的数据：

(->> {:value 2 :children [{:value 7} {:value 88 :children [{:value 5}]}] } 
     (tree-seq map? :children)
     (map :value)) ;;=> (2 7 88 5)

Answer 2

为了累积树的节点值，我有一个非功能性的解决方案：

user> (def a (atom 0))
#'user/a
user> (dorun (clojure.walk/postwalk #(when (number? %) (swap! a (partial + %))) '( 2 (7 nil nil) (88 (5 nil nil) nil))))
nil
user> @a
102

如何在Clojure中遍历一棵树，同时从每个节点节点收集值？

How to traverse a tree in Clojure while collecting the value from each node node?

lisp

tree

clojure

嵌套列表树

嵌套地图树