如何在Clojure中遍历树，同时从每个节点节点收集值？ [英] How to traverse a tree in Clojure while collecting the value from each node node?

问题描述

我想创建一个函数来收集二叉树中每个节点的值。在ClojureDocs中，我发现了几个用于遍历树/图形的函数，例如tree-seq，prewalk和postwalk。

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

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

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

可以使用这些值来累积值的节点遍历？作为一个Clojure newby，我不明白如何做到。如果你知道如何（在Clojure或类似的Lispy语言），请告诉我。理想情况下，你的答案是可以理解的Clojure newby; - ）

我的二叉树用如下节点表示：（value left-child right-child）。例如：

（2（7 nil nil）（88（5 nil nil）nil））

从这个例子中，我想让函数返回（2 7 88 5）。

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

解决方案

好吧， tree-seq 会给你节点序列的深度第一步）。你可以对它进行任何其他的转换，包括（map some-value-extractor-fn（tree-seq ... 需要为该表示选择一个树表示和适当的函数，所以 tree-seq 可以知道什么是内部节点及其子节点
例如，您将树的定义作为嵌套列表：

嵌套列表树

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

 （ - > ）（88（5 nil nil）nil））
（tree-seq list？rest））
  

但这有一点垃圾 - 每个 nil 出现作为seq的成员，我们感兴趣的每个值出现在其列表节点和作为成员本身等。我们可以使用过滤器或 remove 来清理它 - 例如，我们可以丢弃所有叶值，节点：

 （ - > 7（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））
  / pre> 
 
 
，然后只需 map   ：
 （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 列表中的第一个值也是该节点的子节点。 （some-fn list？nil？）是一些高阶函数 - 它构建一个函数，检查输入是否满足谓词列表 或  nil？ 
 
 
 
嵌套地图树
 
 
 
如果你想要更一般的树定义，每个节点可以包含多个值加上可变数量的子项，您可以将您的树定义为嵌套地图： {：value 2：children [{：value 7} {：value 88：children [{：value 5}]}]}  
 
 
 
在这种情况下，仅查看地图作为节点通常是最简单的。我们可能的分支节点是map  - 检查 map？。我们将他们的孩子存储在：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）
  
 
I want to create a function that collects the value from each node in a binary tree.  In the ClojureDocs, I found several functions for traversing a tree/graph, such as tree-seq, prewalk, and postwalk. 

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

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

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

Can any of these be used to accumulate the value of nodes traversed?  As a Clojure newby, I don't see how to do it.  If you know how (in Clojure or similar Lispy language), please show me.  Ideally, your answer will be understandable by a Clojure newby;-)

My binary tree is represented with nodes like this: (value left-child right-child). For example:

  
( 2 (7 nil nil) (88 (5 nil nil) nil) )
From this example, I'd like the function to return (2 7 88 5).

NOTE: The traversal method isn't important.  I just want to learn a technique for collecting node values. 
解决方案
Well, tree-seq will give you the node sequence (of a depth first walk). You can then do any other transformation on it, including (map some-value-extractor-fn (tree-seq ...  to get the values in each node. You just need to pick a tree representation and appropriate functions for that representation so tree-seq can know what is an internal node and what its children are. 
For instance, using your definition of the tree as a nested list:

Nested list tree

The nodes where our tree could branch are lists, which we can identify using list?.Their children are the values following the first, i.e. their rest. So we can define the tree-seq using only standard functions:
(->> '( 2 (7 nil nil) (88 (5 nil nil) nil) )
     (tree-seq list? rest))
but this has a bit of garbage - each nil appears as a member of the seq, each value we're interested in appears both in its list node and as a member in itself and so on. We can clean this up with a filter or remove - for instance we can discard all the leaf values and take only internal nodes:
(->> '( 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))
and then just map first over those:
(->> '( 2 (7 nil nil) (88 (5 nil nil) nil) )
     (tree-seq list? rest)
     (filter list?)
     (map first)) ;;=>(2 7 88 5)
Alternatively we could try to discard internal and nil nodes of the tree, taking only leaves with a value: 
(->> '( 2 (7 nil nil) (88 (5 nil nil) nil) )
     (tree-seq list? seq)
     (remove (some-fn list? nil?))) ;;=>(2 7 88 5)
Note that in this strategy I had to use seq rather than rest, as I want the first value in a list to also be a child of that node. (some-fn list? nil?) is a bit of higher order functions - it builds a function that checks if the input satisfies either of the predicates list? or nil? (or both). 

Nested map tree

If you want a maybe more general tree definition, where each node can contain multiple values plus a variable number of children, you can define your tree as nested maps: {:value 2 :children [{:value 7} {:value 88 :children [{:value 5}]}]}

In this case, looking at only the maps as nodes is generally simplest. Our possibly branching nodes are maps - check for that with map?. We stored their children in the key :children, which is a keyword and so is also a function. We use that function to get the 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})
and then you just need to map over the nodes to get the data you want out of them: 
(->> {:value 2 :children [{:value 7} {:value 88 :children [{:value 5}]}] } 
     (tree-seq map? :children)
     (map :value)) ;;=> (2 7 88 5)


                        
这篇关于如何在Clojure中遍历树，同时从每个节点节点收集值？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！