В дереве, как мне найти пути к узлам дерева, у которых есть дети с листьями?

Question

По сути, я пытаюсь реализовать этот алгоритм, хотя, возможно, есть лучший способ сделать это.

• начиная с корня
• проверить каждый дочерний элемент текущего узла напотомки с листьями (child of child)
• если какие-либо узлы child-of-child текущего узла имеют листы, путь записи к текущему узлу (не к child) и не продолжаются по этому путидалее.
• еще продолжить 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]]

Вот моя ошибка в этом случае:

(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 ниже, но я думаю, что проблема все еще существуетс моим кодом, так как при этом печатаются все пути, а не нужные.

Answer 1

Исключение составляет функция children-have-leaves?.

Выражение (not (empty? z/children)) завершается ошибкой, поскольку z / children является функцией, однако для коллекции необходимо вызывать empty? .

Вам нужен предикат, который возвращает 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))))

Answer 2

Я полагаю, вы ссылались на мой предыдущий ответ , связанный с застежкой-молнией.Но обратите внимание, что мой предыдущий ответ использует vector-zip как есть, и, следовательно, вы должны перемещаться по нему как vector-zip - который вам, возможно, придется обернуть вокруг, как работают два курсора.Чтобы упростить навигацию, я предлагаю вам создать собственную молнию для вашей древовидной структуры.Т.е.

(defn my-zipper [root]
  (z/zipper ;; branch?
            (fn [x]
              (when (vector? x)
                (let [[n & xs] x] (and n (-> xs count zero? not)))))
            ;; children
            (fn [[n & xs]] xs)
            ;; make-node
            (fn [[n & _] xs] [n xs])
            root))

тогда решение будет похоже на мой другой ответ:

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

(->> test-data2
     my-zipper
     (iterate z/next)
     (take-while (complement z/end?))
     (filter (comp children-with-leaves? z/node))
     (map #(->> % z/path (map z/node)))
     set)
;; => #{(:root :a :x) (:root :a :x :y) (:root :b :c)}

, где основная логика упрощена до:

(defn children-with-leaves? [[_ & children]]
  (some (fn [[c & xs]] (nil? xs)) children))

Answer 3

Если вы хотите обрабатывать древовидные структуры данных, я настоятельно рекомендую библиотеку tupelo.forest .

Хотя я не понимаю твоей цели. Узлы :a и :c в вашем примере не одинаково удалены от ближайшего листа.

На самом деле, я только что заметил , что дерево в вашем примере отличается от дерева в вашей попытке кода. Не могли бы вы обновить вопрос, чтобы привести их в соответствие?

---

Вот пример того, как вы могли бы сделать это:

(dotest ; find the grandparent of each leaf
  (hid-count-reset)
  (with-forest (new-forest)
    (let [data              [:root
                             [:a
                              [:x
                               [:y [:t [:l2]]]
                               [:z [:l3]]]]
                             [:b [:c
                                  [:d [:l4]]
                                  [:e [:l5]]]]]
          root-hid          (add-tree-hiccup data)
          leaf-paths        (find-paths-with root-hid [:** :*] leaf-path?)
          grandparent-paths (mapv #(drop-last 2 %) leaf-paths)
          grandparent-tags  (set
                              (forv [path grandparent-paths]
                                (let [path-tags (it-> path
                                                  (mapv #(hid->node %) it)
                                                  (mapv #(grab :tag %) it))]
                                  path-tags)))]
      (is= (format-paths leaf-paths)
        [[{:tag :root} [{:tag :a} [{:tag :x} [{:tag :y} [{:tag :t} [{:tag :l2}]]]]]]
         [{:tag :root} [{:tag :a} [{:tag :x} [{:tag :z} [{:tag :l3}]]]]]
         [{:tag :root} [{:tag :b} [{:tag :c} [{:tag :d} [{:tag :l4}]]]]]
         [{:tag :root} [{:tag :b} [{:tag :c} [{:tag :e} [{:tag :l5}]]]]]])
      (is= grandparent-tags
          #{[:root :a :x] 
            [:root :a :x :y] 
            [:root :b :c]} ))))