假设我有一棵这样的树。我想获得只包含叶子而不是非叶子子节点的子节点的路径。
所以对于这棵树
root
├──leaf123
├──level_a_node1
│ ├──leaf456
├──level_a_node2
│ ├──level_b_node1
│ │ └──leaf987
│ └──level_b_node2
│ └──level_c_node1
| └── leaf654
├──leaf789
└──level_a_node3
└──leaf432
结果是
[["root" "level_a_node1"]
["root" "level_a_node2" "level_b_node1"]
["root" "level_a_node2" "level_b_node2" "level_c_node1"]
["root" "level_a_node3"]]
我试图深入到底部节点并检查 (lefts)
和 (rights)
是否不是分支,但那不是非常有效。
(z/vector-zip ["root"
["level_a_node3" ["leaf432"]]
["level_a_node2" ["level_b_node2" ["level_c_node1" ["leaf654"]]] ["level_b_node1" ["leaf987"]] ["leaf789"]]
["level_a_node1" ["leaf456"]]
["leaf123"]])
编辑:我的数据实际上是以路径列表的形式出现的,我正在将其转换为树。但这也许过于复杂了?
[["root" "leaf"]
["root" "level_a_node1" "leaf"]
["root" "level_a_node2" "leaf"]
["root" "level_a_node2" "level_b_node1" "leaf"]
["root" "level_a_node2" "level_b_node2" "level_c_node1" "leaf"]
["root" "level_a_node3" "leaf"]]
最佳答案
打嗝式建筑是个值得游览的好地方,但我不想住在那里。也就是说,它们写起来非常简洁,但是以编程方式进行操作却非常痛苦,因为语义嵌套结构没有反射(reflect)在节点的物理结构中。因此,我要做的第一件事是转换为 Enlive 风格的树表示(或者,理想情况下,首先生成 Enlive):
(def hiccup
["root"
["level_a_node3" ["leaf432"]]
["level_a_node2"
["level_b_node2"
["level_c_node1"
["leaf654"]]]
["level_b_node1"
["leaf987"]]
["leaf789"]]
["level_a_node1"
["leaf456"]]
["leaf123"]])
(defn hiccup->enlive [x]
(when (vector? x)
{:tag (first x)
:content (map hiccup->enlive (rest x))}))
(def enlive (hiccup->enlive hiccup))
;; Yielding...
{:tag "root",
:content
({:tag "level_a_node3", :content ({:tag "leaf432", :content ()})}
{:tag "level_a_node2",
:content
({:tag "level_b_node2",
:content
({:tag "level_c_node1",
:content ({:tag "leaf654", :content ()})})}
{:tag "level_b_node1", :content ({:tag "leaf987", :content ()})}
{:tag "leaf789", :content ()})}
{:tag "level_a_node1", :content ({:tag "leaf456", :content ()})}
{:tag "leaf123", :content ()})}
完成此操作后,最后一件阻碍您使用 zipper 的事情就是您的愿望。它们是目标遍历的好工具,您非常关心正在处理的节点附近的结构。但是,如果您只关心节点及其子节点,那么只需编写一个简单的递归函数来遍历树就容易得多:
(defn paths-to-leaves [{:keys [tag content] :as root}]
(when (seq content)
(if (every? #(empty? (:content %)) content)
[(list tag)]
(for [child content
path (paths-to-leaves child)]
(cons tag path)))))
像这样编写递归遍历的能力是一项将在您的 Clojure 职业生涯中多次为您服务的技能(例如,a similar question I recently answered on Code Review)。事实证明,树上的大量函数只是:在每个 child 上递归调用自己,并以某种方式组合结果,通常在可能嵌套的 for
循环中。困难的部分只是弄清楚您的基本案例需要什么,以及正确的 maps/mapcat 序列以组合结果而不引入不需要的嵌套级别。
如果您坚持坚持使用 Hiccup,您可以在使用部位拆解它而不会太痛苦:
(defn hiccup-paths-to-leaves [node]
(when (vector? node)
(let [tag (first node), content (next node)]
(if (and content (every? #(= 1 (count %)) content))
[(list tag)]
(for [child content
path (hiccup-paths-to-leaves child)]
(cons tag path))))))
但它明显更困惑,并且每次处理一棵树时都必须重复这项工作。我再次鼓励您使用 Enlive 风格的树来表示您的内部数据。
关于clojure - 如何使用 clojure zippers 获取只有叶子的树中所有子节点的路径?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/56030511/