clojure - 在树中，如何找到具有带叶子的子节点的树节点的路径？

Question

基本上，我正在尝试实现这个算法，尽管也许有更好的方法来实现它。

• 从根开始
• 检查当前节点的每个孩子是否有带叶子的孩子（孩子的孩子）
• 如果当前节点的任何子节点有叶子，则记录到当前节点的路径（而不是子节点），并且不要继续沿着该路径继续前进。
• 否则继续 DFS

非功能性伪代码：

def find_paths(node):
    for child in node.children:
       if child.children.len() == 0
          child_with_leaf = true
    if child_with_leaf
       record path to node
    else
       for child in node.children
           find_paths(child)

例如：

:root
  |- :a
  |   +- :x
  |       |- :y
  |       |   +- :t
  |       |       +- :l2
  |       +- :z
  |          +- :l3
  +- :b
      +- :c
          |- :d
          |   +- :l4
          +- :e
              +- :l5

结果将是：

[[:root :a]
 [:root :b :c]]

这是我在clojure中的破解：

(defn atleast-one?
  [pred coll]
  (not (nil? (some pred coll))))

; updated with erdos's answer
(defn children-have-leaves?
  [loc]
  (some->> loc
           (iterate z/children)
           (take-while z/branch?)
           (atleast-one? (comp not empty? z/children))))

(defn find-paths
  [tree]
  (loop [loc (z/vector-zip tree)
         ans nil]
    (if (z/end? loc)
      ans
      (recur (z/next loc)
             (cond->> ans
                      (children-have-leaves? loc)
                      (cons (->> loc z/down z/path (map z/node)))))))
  )

(def test-data2
  [:root [:a [:x [:y [:t [:l2]]] [:z [:l3]]]] [:b [:c [:d [:l4]] [:e [:l5]]]]]
  )

更新：使用下面的 erdos 答案修复了崩溃，但我认为我的代码仍然存在问题，因为它会打印每条路径而不是所需的路径。

标签： clojure

Answer 1

例外来自您的children-have-leaves?功能。

(not (empty? z/children))表达式失败，因为z/children是一个函数，但是，它是空的吗？必须在集合上调用。

您需要的是一个谓词，true如果节点有子节点，则返回，例如：(fn [x] (not (empty? (z/children x))))或更短：(comp not empty? z/children)

正确的实现：

(defn children-have-leaves?
  [loc]
  (some->> loc
           (iterate z/children)
           (take-while z/branch?)
           (atleast-one? (comp not empty? z/children))))