如何使用 clojure 拉链获取只有叶子的树中所有子节点的路径？

Question

假设我有一棵这样的树。我想获取仅包含叶子而不包含非叶子子节点的子节点的路径。

\n\n

那么对于这棵树

\n\n

root\n\xe2\x94\x9c\xe2\x94\x80\xe2\x94\x80leaf123\n\xe2\x94\x9c\xe2\x94\x80\xe2\x94\x80level_a_node1\n\xe2\x94\x82   \xe2\x94\x9c\xe2\x94\x80\xe2\x94\x80leaf456\n\xe2\x94\x9c\xe2\x94\x80\xe2\x94\x80level_a_node2\n\xe2\x94\x82  \xe2\x94\x9c\xe2\x94\x80\xe2\x94\x80level_b_node1\n\xe2\x94\x82  \xe2\x94\x82  \xe2\x94\x94\xe2\x94\x80\xe2\x94\x80leaf987\n\xe2\x94\x82  \xe2\x94\x94\xe2\x94\x80\xe2\x94\x80level_b_node2\n\xe2\x94\x82     \xe2\x94\x94\xe2\x94\x80\xe2\x94\x80level_c_node1\n|        \xe2\x94\x94\xe2\x94\x80\xe2\x94\x80 leaf654\n\xe2\x94\x9c\xe2\x94\x80\xe2\x94\x80leaf789\n\xe2\x94\x94\xe2\x94\x80\xe2\x94\x80level_a_node3\n   \xe2\x94\x94\xe2\x94\x80\xe2\x94\x80leaf432\n

\n\n

结果将是

\n\n

[["root"  "level_a_node1"]\n["root"  "level_a_node2" "level_b_node1"]\n["root"  "level_a_node2" "level_b_node2" "level_c_node1"]\n["root"  "level_a_node3"]]\n

\n\n

我试图深入到底部节点并检查 和 是否(lefts)不是(rights)分支，但这不太有效。

\n\n

(z/vector-zip ["root"\n               ["level_a_node3" ["leaf432"]]\n               ["level_a_node2" ["level_b_node2" ["level_c_node1" ["leaf654"]]] ["level_b_node1" ["leaf987"]] ["leaf789"]]\n               ["level_a_node1" ["leaf456"]]\n               ["leaf123"]])\n

\n\n

编辑：我的数据实际上是作为路径列表输入的，我正在将其转换为树。但也许这过于复杂化了？

\n\n

[["root" "leaf"]\n["root"  "level_a_node1" "leaf"]\n["root"  "level_a_node2" "leaf"]\n["root"  "level_a_node2" "level_b_node1" "leaf"]\n["root"  "level_a_node2" "level_b_node2" "level_c_node1" "leaf"]\n["root"  "level_a_node3" "leaf"]]\n

\n

Answer 1

打嗝式建筑是一个值得参观的好地方，但我不想住在那里。也就是说，它们写起来非常简洁，但以编程方式操作却非常痛苦，因为语义嵌套结构没有反映在节点的物理结构中。因此，我要做的第一件事就是转换为 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 ()})}

完成此操作后，最后一个阻碍您的事情就是您对使用拉链的渴望。它们是有针对性的遍历的好工具，您非常关心正在处理的节点附近的结构。但是，如果您只关心节点及其子节点，那么只需编写一个简单的递归函数来遍历树就会容易得多：

(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 职业生涯中多次为您服务的技能（例如，我最近在 Code Review 上回答的类似问题）。事实证明，树上的大量函数只是：在每个子节点上递归地调用自己，并以某种方式组合结果，通常是在可能嵌套的循环中for。困难的部分只是弄清楚你的基本情况需要是什么，以及正确的映射/映射猫序列来组合结果，而不会引入不需要的嵌套级别。

如果您坚持坚持使用 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 风格的树来表示内部数据。