2

我有一个地图矢量，我想以嵌套的方式进行转换。

数据结构如下：

(def data
  [{:id 1 :name "a" :parent 0}
   {:id 2 :name "b" :parent 0}
   {:id 3 :name "c" :parent 0}
   {:id 4 :name "a_1" :parent 1}
   {:id 5 :name "a_2" :parent 1}
   {:id 6 :name "b_1" :parent 2}
   {:id 7 :name "a_1_1" :parent 4}])

每个映射都有一个:id，一些其他的键和值对于这个讨论并不重要，:parent键，表示元素是否属于另一个元素。如果:parent为 0，则它是顶级元素。

我想嵌套这个扁平列表，以便属于父级的每个元素都存储在:nodes父级映射中的一个键下，如下所示：

(def nested
  [{:id 1 :name "a" :parent 0 :nodes
    [{:id 4 :name "a_1" :parent 1 :nodes []}
     {:id 5 :name "a_2" :parent 1 :nodes
      [{:id 7 :name "a_1_1" :parent 4 :nodes []}]}]}
   {:id 2 :name "b" :parent 0 :nodes
    [{:id 6 :name "b_1" :parent 2}]}
   {:id 3 :name "c" :parent 0 :nodes []}])

总而言之 - 我有一个扁平的树状结构，我希望再次变成一棵树。我尝试使用拉链来实现这一点，但未能处理任意嵌套级别。

4

3 回答 3

3

最简单的方法是通过在每一步执行完整扫描来递归构建它：

(defn tree
  ([flat-nodes]
    (tree flat-nodes 0))
  ([flat-nodes parent-id]
    (for [node flat-nodes
          :when (= (:parent node) parent-id)]
      (assoc node
        :nodes (tree flat-nodes (:id node))))))

接着

=> (tree data)
({:parent 0, :name "a", :nodes 
   ({:parent 1, :name "a_1", :nodes 
     ({:parent 4, :name "a_1_1", :nodes (), :id 7}), :id 4}
    {:parent 1, :name "a_2", :nodes (), :id 5}), :id 1}
 {:parent 0, :name "b", :nodes
   ({:parent 2, :name "b_1", :nodes (), :id 6}), :id 2}
 {:parent 0, :name "c", :nodes (), :id 3})

更新：更有效的变化

(defn tree [flat-nodes]
  (let [children (group-by :parent flat-nodes)
        nodes (fn nodes [parent-id]
                (map #(assoc % :nodes (nodes (:id %)))
                  (children parent-id)))]
    (nodes 0)))
于 2015-01-27T16:16:08.750 回答
1

这样一棵树必须自下而上构建，因此我们需要一个函数将一系列节点拆分为叶子和内部节点：

(defn split-leaves
  [nodes]
  (let [parent-id? (set (map :parent nodes))]
    (group-by
      (comp #(if % :inner :leaves) parent-id? :id)
      nodes)))

下一步是将所有叶子附加到它们的父母身上：

(defn attach-leaves
  [inner leaves]
  (let [leaves-by-parent (group-by :parent leaves)]
    (map
      (fn [{:keys [id] :as node}]
        (update-in node [:nodes] concat (leaves-by-parent id)))
      inner)))

必须重复这两个步骤，直到只剩下叶子：

(defn generate
  [nodes root-id]
  (loop [nodes (conj nodes {:id root-id})]
    (let [{:keys [leaves inner]} (split-leaves nodes)]
      (if (seq inner)
        (recur (attach-leaves inner leaves))
        (some #(when (= (:id %) root-id) (:nodes %)) leaves)))))

请注意，我们必须添加和删除一个虚拟根节点才能使其正常工作，因为您的原始节点集不包含一个（这就是函数需要根节点 ID 的原因）。

(generate data 0)
;; => ({:parent 0, :name "c", :id 3}
;;     {:parent 0, :name "b",
;;      :nodes ({:parent 2, :name "b_1", :id 6}),
;;      :id 2}
;;     {:parent 0, :name "a",
;;      :nodes ({:parent 1, :name "a_2", :id 5}
;;              {:parent 1, :name "a_1",
;;               :nodes ({:parent 4, :name "a_1_1", :id 7}),
;;               :id 4}),
;;      :id 1})
于 2015-01-27T13:25:04.513 回答
0

另一种选择是将您的子父关系转换为邻接列表，然后遍历无环有向图。

(defn adjacency-list [coll]
  (reduce (fn [r {p :parent c :id}]
            (-> r
              (update-in [:counts p] #(or % 0))
              (update-in [:counts c] #(if % (inc %) 1))
              (update-in [:adjacency p] #(if % (conj % c) [c]))))
          {}
          coll))

(defn get-data [k]
  (first (filter #(= (:id %) k) data)) )

(defn traverse [m al roots]
  (reduce (fn [r k]
            (conj r
                  (assoc (get-data k)
                         :nodes (if-let [v (get al k)]
                                  (traverse [] al v)
                                  []))))
          m
          roots))

(clojure.pprint/pprint
 (let [{:keys [adjacency]} (adjacency-list data)]
   (traverse [] adjacency (get adjacency 0))))
于 2015-01-27T18:37:48.867 回答