如何在从每个节点节点收集值时遍历Clojure中的树？

Question

我想创建一个函数来收集二叉树中每个节点的值.在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理解;-)

我的二叉树用这样的节点表示:(值left-child right-child).例如:

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

从这个例子中,我想要返回的功能(2 7 88 5).

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

Answer 1

好吧,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或清除它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?)有点的高阶函数-它建立来检查,如果输入满足功能要么谓词list? 或 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)