问题描述
我想创建一个函数来收集二叉树中每个节点的值。在ClojureDocs中,我发现了几个用于遍历树/图形的函数,例如tree-seq,prewalk和postwalk。
可以使用这些值来累积值的节点遍历?作为一个Clojure newby,我不明白如何做到。如果你知道如何(在Clojure或类似的Lispy语言),请告诉我。理想情况下,你的答案是可以理解的Clojure newby; - )
我的二叉树用如下节点表示:(value left-child right-child)。例如:
从这个例子中,我想让函数返回(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)
/ pre>
(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
:
(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:
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 sotree-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. theirrest
. 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 afilter
orremove
- 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 thanrest
, 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 predicateslist?
ornil?
(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中遍历树,同时从每个节点节点收集值?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!