Recreate a flattened tree

问题:

I have a vector of maps, that I'd like to transform in a nested fashion.

The data is structured as follows:

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

Each map has an :id, some other keys and values not important for this discussion, and :parent key, denoting if the elements belong to another element. If :parent is 0, it's a top level element.

I want to nest this flattened list so that each element belonging to a parent gets stored under a key :nodes in the parent map, like this:

(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 []}])

To sum up - I have a flattened tree-like structure that I whish to transform into a tree again. I tried to achieve this using zippers, but failed to handle arbritarily nested levels.

回答1:

The easiest way is to build it recursively by performing a full scan at each step:

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

and then

=> (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})

Update: A more efficient variation

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

回答2:

Such a tree has to be built from the bottom up, so we need a function that will split a seq of nodes into leaves and inner ones:

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

The next step is attaching all leaves to their parents:

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

Those two steps have to be repeated until there are only leaves left:

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

Note that we have to add and remove a virtual root node for this to work since your original set of nodes did not contain one (that's why the function expects the root node's 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})

回答3:

Another option is to convert your child parent relationships to an adjacency list and then traverse the acyclic directed graph.

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