如何使用clojure拉链获取到只有叶子的树中所有子节点的路径？ [英] How to obtain paths to all the child nodes in a tree that only have leaves using clojure zippers?

问题描述

说我有一棵这样的树。我想获得到仅包含叶子而不包含非叶子子节点的子节点的路径。

Say I have a tree like this. I would like to obtain the paths to child nodes that only contain leaves and not non-leaf child nodes.

因此对于这棵树

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"]]

我试图下移到底部节点，并检查（左）和（权利）都不是分支，但这不太起作用。

I've attempted to go down to the bottom nodes and check if the (lefts) and the (rights) are not branches, but that that doesn't quite work.

(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"]])

编辑：我的数据实际上是作为路径列表进入的，我正在将其转换为树。

edit: my data is actually coming in as a list of paths and I'm converting that into a tree. But maybe that is an overcomplication?

[["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"]]

推荐答案

您绝对可以使用文件api浏览目录。如果使用拉链，则可以执行以下操作：

You can definitely use the file api to navigate the directory. If using zipper, you can do this:

(loop [loc (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" "leaf456b"]]
                        ["leaf123"]])
       ans nil]
  (if (end? loc)
    ans
    (recur (next loc)
           (cond->> ans
             (contains-leaves-only? loc)
             (cons (->> loc down path (map node)))))))

将输出以下内容：

(("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"))

定义树的方式，可以将
的帮助函数实现为：

with the way you define the tree, helper functions can be implemented as:

(def is-leaf? #(-> % down nil?))

(defn contains-leaves-only?
  [loc]
  (some->> loc
           down            ;; branch name
           right           ;; children list
           down            ;; first child
           (iterate right) ;; with other sibiling
           (take-while identity)
           (every? is-leaf?)))

UPDATE-添加一个惰性序列版本

(->> ["root"
      ["level_a_node3"
      ["leaf432"]]
      ["level_a_node2"
      ["level_b_node2"
        ["level_c_node1"
        ["leaf654"]]]
      ["level_b_node1"
        ["leaf987"]]
      ["leaf789"]]
      ["level_a_node1"
      ["leaf456" "leaf456b"]]
      ["leaf123"]]
     vector-zip
     (iterate next)
     (take-while (complement end?))
     (filter contains-leaves-only?)
     (map #(->> % down path (map node))))

这篇关于如何使用clojure拉链获取到只有叶子的树中所有子节点的路径？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！