Well, tree-seq
将为您提供节点序列(深度优先遍历的)。然后您可以对其进行任何其他转换,包括(map some-value-extractor-fn (tree-seq ...
获取每个节点中的值。您只需要选择一个树表示和该表示的适当函数,这样tree-seq
可以知道什么是内部节点以及它的子节点是什么。
例如,使用您对树的定义作为嵌套列表:
嵌套列表树
我们的树可以分支的节点是列表,我们可以使用list?
.他们的孩子是继第一个孩子之后的价值观,即他们的孩子rest
。因此我们可以仅使用标准函数来定义 tree-seq:
(->> '( 2 (7 nil nil) (88 (5 nil nil) nil) )
(tree-seq list? rest))
但这有一点垃圾 - 每个nil
作为 seq 的成员出现,我们感兴趣的每个值都出现在其列表节点中并作为其本身的成员,依此类推。我们可以用一个清理这个filter
or 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)
或者,我们可以尝试丢弃树的内部节点和零节点,只获取具有值的叶子:
(->> '( 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?)
是一些高阶函数 - 它构建一个函数来检查输入是否满足either谓词的list?
or nil?
(或两者)。
嵌套地图树
如果您想要一个可能更通用的树定义,其中每个节点可以包含多个值以及可变数量的子节点,您可以将树定义为嵌套映射:{:value 2 :children [{:value 7} {:value 88 :children [{:value 5}]}]}
在这种情况下,仅将地图视为节点通常是最简单的。我们可能的分支节点是地图 - 检查它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)