重新创建展平的树 [英] Recreate a flattened tree

问题描述

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

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

数据的结构如下：

(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，则它​​是一个顶级元素。

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.

我想嵌套此扁平化列表，以便每个属于父级的元素存储在父级映射中的键：nodes 下，例如：

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.

推荐答案

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

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

然后

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

这篇关于重新创建展平的树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！