recursion - 重新创建一棵扁平的树

Question

我有一个 map 向量，我想以嵌套方式对其进行转换。

数据结构如下:

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

总而言之 - 我有一个扁平的树状结构，我希望将其再次转变为一棵树。我尝试使用 zipper 来实现此目的，但未能处理任意嵌套的级别。

Answer 1

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

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