我认为最好用一个例子。假设我有一棵有序的树：
(def abcd [:a [:b :c] :d])
我想从中构建键值映射的集合，每个映射代表该树的一个节点，并具有一个随机名称和所有相关信息，即其父级（对于根节点为零）其索引（0、1 ，2 ..），如果它是叶节点，则为其内容（如“：a”）。例如，在这种情况下，可能是：
[{:name G__36654, :parent nil, :index 0}
{:name G__36655, :content :a, :parent G__36654, :index 0}
{:name G__36656, :parent G__36654, :index 1}
{:name G__36657, :content :b, :parent G__36656, :index 0}
{:name G__36658, :content :c, :parent G__36656, :index 1}
{:name G__36659, :content :d, :parent G__36654, :index 2}]
我定义了一个函数，该函数似乎可以实现我想要的功能，但是它通过调用自身来使用递归，而我在弄清楚如何使用循环递归方面遇到了麻烦，而且我相信那里肯定会有更好的东西。这是我的尝试：
(defn mttrav "my tree traversal"
([ptree parent index]
(let [name (gensym)]
(cond
(not (coll? ptree)) [ {:name name :content ptree :parent parent :index index}]
:else (reduce into
[{:name name :parent parent :index index}]
(map-indexed #(mttrav %2 name %1) ptree)))))
([ptree]
(mttrav ptree nil 0)))
顺便说一句，我不知道向量是否适合使用正确的集合，也许集合会更有意义，但是我正在使用向量来简化调试，因为当保留生成节点的顺序时，它更具可读性，并且如果节点意外重复，我希望看到它。
提前致谢！
编辑：只是为了澄清，每个节点都有一个：child节点列表而不是：parent节点列表以及其他一些变体也是可以接受的，只要它是地图的平面集合，每个地图代表一个节点，具有唯一的：name，并在此结构中捕获节点的位置，内容和父子关系。预期的输入是打from解析树，这些树通常来自Instaparse，并且映射旨在成为要插入Clara会话中的记录。
您需要广度优先遍历。因此，如果要在遍历树时构建父级列表，则需要首先唯一地标识所有叶节点。我不确定是否可以这样做，除非您确定您的叶子节点是唯一的。在这里也很晚/很早，所以我的大脑无法最佳工作。我确信我的解决方案会被大量蒸馏掉。
因此，如果您有一棵像[：a [：b：c]：d [：b：c]]的树，则[：b：c]是：b和：c的父级，但是最后两个叶节点也是：b和：c，那么您选择哪个父母？
因此，让我们有一棵树的叶子具有唯一ID的树。
(defn attach-ids [tree]
(clojure.walk/postwalk (fn [node]
(if (coll? node) node
{:node node :id (gensym)}))
tree))
(def tree (attach-ids [:a [:b :c] :d]))
;; produces this
;; [{:node :a, :id G__21500}
;; [{:node :b, :id G__21501} {:node :c, :id G__21502}]
;; {:node :d, :id G__21503}]
现在为其余的解决方案
(defn add-parent [parent-map id branch]
(assoc parent-map id {:children-ids (set (map :id branch))
:child-nodes (map :node branch)}))
(defn find-parent-id [node parent-map]
(->> parent-map
(filter (fn [[parent-id {children-ids :children-ids}]]
(contains? children-ids (:id node))))
ffirst))
(defn find-index [node parent-map tree]
(if-let [parent-id (find-parent-id node parent-map)]
(let [children (:child-nodes (get parent-map parent-id))]
(.indexOf children (:node node)))
(.indexOf tree node)))
(defn bfs [tree]
(loop [queue tree
parent-map {}
ret []]
(if (not-empty queue)
(let [node (first queue)
rst (vec (rest queue))]
(cond
(map? node)
(recur rst
parent-map
(conj ret (assoc node :parent (find-parent-id node parent-map)
:index (find-index node parent-map tree))))
(vector? node)
(let [parent-id (gensym)]
(recur (into rst node)
(add-parent parent-map parent-id node)
(conj ret {:id parent-id
:index (find-index node parent-map tree)
:parent (find-parent-id node parent-map)})))))
ret)))
(def tree (attach-ids [:a [:b :c] :d]))
(bfs tree)
;; children with :parent nil value point to root
;;[{:node :a, :id G__21504, :parent nil, :index 0}
;; {:id G__21513, :index 1}
;; {:node :d, :id G__21507, :parent nil, :index 2}
;; {:node :b, :id G__21505, :parent G__21513, :index 0}
;; {:node :c, :id G__21506, :parent G__21513, :index 1}]
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句