代码之家 › 专栏 › 技术社区 › adapt-dev

在树中,如何找到子节点具有叶子的树节点的路径?

clojurescript clojure

adapt-dev · 技术社区 · 7 年前

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

从根开始
否则继续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的答案修复了崩溃,但是我认为我的代码仍然有问题,因为它打印了所有的路径,而不是期望的路径。

0 回复 | 直到 7 年前

rmcv 7 年前

我想你引用了我以前的 answer 与拉链有关。但请注意,我之前的回答使用 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))

erdos 7 年前

例外情况来自于 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))))

Alan Thompson 7 年前

如果您想处理类似树的数据结构,我强烈建议 the tupelo.forest library .

不过,我不明白你的目标。节点 :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]} ))))