转换亲子阵列树

Question

谁能帮亲子以下对象列表转换：

 
[ 
    { 
     "name":"root", 
     "_id":"root_id", 
    }, 
    { 
     "name":"a1", 
     "parentAreaRef":{ 
     "id":"root_id", 
     }, 
     "_id":"a1_id", 
    }, 
    { 
     "name":"a2", 
     "parentAreaRef":{ 
     "id":"a1_id", 
     }, 
     "_id":"a2_id", 
    }, 
    { 
     "name":"a3", 
     "parentAreaRef":{ 
     "id":"a2_id", 
     }, 
     "_id":"a3_id", 
    }, 
    { 
     "name":"b1", 
     "parentAreaRef":{ 
     "id":"root_id", 
     }, 
     "_id":"b1_id", 
    }, 
    { 
     "name":"b2", 
     "parentAreaRef":{ 
     "id":"b1_id", 
     }, 
     "_id":"b2_id", 
    }, 
    { 
     "name":"b3", 
     "parentAreaRef":{ 
     "id":"b1_id", 
     }, 
     "_id":"b3_id", 
    } 
]

成一个树状结构显示父子关系：

 
[ 
    { 
     "name": "root", 
     "_id":"root_id", 
     "children": [ 
      { 
       "name": "a1", 
       "_id":"a1_id", 
       "children" : [ 
        { 
         "name" : "a2", 
         "_id":"a2_id", 
         "children" : [ 
          { 
           "name" : "a3" 
           "_id":"a3_id" 
          } 
         ] 
        } 
       ] 
      }, 
      { 
       "name": "b1", 
       "_id":"b1_id", 
       "children" : [ 
        { 
         "name" : "b2" 
         "_id":"b2_id" 
        }, 
        { 
         "name" : "b3" 
         "_id":"b3_id" 
        } 
       ] 
      } 
     ] 
    } 
] 

（该输出结构是一个允许多个根的数组，但是如果我们可以得到一个解决方案来处理单个根也是很好的。）

输出树看起来像这样：

 

root 
    | 
    -- a1 
    | | 
    | -- a2 
    |  | 
    |  -- a3 
    | 
    -- b1 
     | 
     -- b2 
     -- b3 

谢谢！

Answer 1

我有一个可行的解决方案。我可以给你提示，只要解决它。好处是您的数据不包含任何对节点的前向引用。所以你可以通过数组来创建你的树。如果需要注意，您需要先通过整个阵列来构建一个到节点的ID映射。

你的算法看起来像这样。

1. 创建一个将id映射到节点的映射。这将使查找节点变得容易。
2. 循环遍历节点阵列。
3. 对于每个元素。
   1. 在地图中添加一个条目。
   2. 将一个children属性（一个数组）添加到此节点。
   3. 元素是否有父级？如果不是，则它必须是根，因此将此元素分配给树的根。
   4. 此元素有一个父元素，所以查找父节点，然后将此当前节点添加为父节点的子元素（将其添加到children数组中）。

这应该有助于您解决问题。如果你对这个算法有特殊的问题，我可以指出问题出在哪里，如何解决或发布解决方案，并解释我如何解决它。

UPDATE

我看着你有解决方案。实际上，您不需要为此进行递归，您可以使用上述算法迭代地执行此操作。您也正在修改结构，这使得算法更加复杂。但你有点正确。下面是我如何解决它：

var idToNodeMap = {}; //Keeps track of nodes using id as key, for fast lookup 
var root = null; //Initially set our loop to null 

//loop over data 
data.forEach(function(datum) { 

    //each node will have children, so let's give it a "children" poperty 
    datum.children = []; 

    //add an entry for this node to the map so that any future children can 
    //lookup the parent 
    idToNodeMap[datum._id] = datum; 

    //Does this node have a parent? 
    if(typeof datum.parentAreaRef === "undefined") { 
     //Doesn't look like it, so this node is the root of the tree 
     root = datum;   
    } else {   
     //This node has a parent, so let's look it up using the id 
     parentNode = idToNodeMap[datum.parentAreaRef.id]; 

     //We don't need this property, so let's delete it. 
     delete datum.parentAreaRef; 

     //Let's add the current node as a child of the parent node. 
     parentNode.children.push(datum);   
    } 
}); 

现在root指向整个树。

Fiddle。

对于元素数组以任意顺序排列的情况，您必须首先初始化idToNodeMap。该算法的其余部分保持更多或更少相同的（除了在您的节点存储在地图中的路线;这是没有必要的，因为你在第一遍做的话）：

var idToNodeMap = data.reduce(function(map, node) { 
    map[node._id] = node; 
    return map; 
}, {});