javascript - 递归数据结构将每个分支分开

Question

我有一个像下面这个例子的递归数据结构，我希望它的目标可以是每一个分支，从null(parentTagId)延伸到只要final一个。

我不知道该怎么做，任何建议将不胜感激!!

原始数据:

[ 
  { TagId: 2, ParentTagId: null, Name: 'women' },
  { TagId: 5, ParentTagId: 2, Name: 'bottom' },
  { TagId: 4, ParentTagId: 2, Name: 'top' },
  { TagId: 7, ParentTagId: 4, Name: 'shirt' },
  { TagId: 8, ParentTagId: 4, Name: 'tshirt' },
  { TagId: 12, ParentTagId: 7, Name: 'longsleeve' },
  { TagId: 16, ParentTagId: null, Name: 'men' }
]

预期结果:

women > bottom  
women > top > shirt > longsleeve   
women > tshirt  
men  

输出数据:

[
  {
    path: [ 
      { TagId: 2, ParentTagId: null, Name: 'women' },
      { TagId: 5, ParentTagId: 2, Name: 'bottom' }
    ]
  },
  {
    path: [
      { TagId: 2, ParentTagId: null, Name: 'women' },
      { TagId: 4, ParentTagId: 2, Name: 'top' },
      { TagId: 7, ParentTagId: 4, Name: 'shirt' },
      { TagId: 12, ParentTagId: 7, Name: 'longsleeve' }
    ]
  },
  {
    path: [
      { TagId: 2, ParentTagId: null, Name: 'women' },
      { TagId: 4, ParentTagId: 2, Name: 'top' },
      { TagId: 8, ParentTagId: 4, Name: 'tshirt' }
    ]
  },
  {
    path: [
      { TagId: 16, ParentTagId: null, Name: 'men' }
    ]
  }
]

Answer 1

将您的输入数据视为一棵树。您想要为每个叶 生成路径。叶子是一个带有 TagId 的标签，它不被任何其他标签引用为 ParentTagId。

所以最简单的解决方案是:

1. 遍历所有标签并构建所有 ParentTagId 值的集合(即具有唯一条目的列表)。对于您的数据，即 [2,4,7]。
2. 通过遍历所有标签并选择那些 TagId 不在该集合中的标签来找到您的叶子。对于您的数据，即 [5,8,12,16]。
3. 编写函数 getTagById 以通过其 id 检索标签。
4. 编写一个递归函数来生成路径。
5. 遍历所有叶子并将 getPath([], leaf) 的结果推送到数组 paths 中。之后，paths 包含每个叶子的路径作为标签数组。
6. 根据路径构建输出。

第一步代码:

var parentTagIdSet = [];
for (var i = 0; i < originData.length; ++i) {
  var parentTagId = originData[i].ParentTagId;
  if (parentTagId != null && parentTagIdSet.indexOf(parentTagId) == -1) {
    parentTagIdSet.push(parentTagId);
  }
}

步骤 2 的代码:

var leaves = [];
for (var i = 0; i < originData.length; ++i) {
  var tag = originData[i];
  if (parentTagIdSet.indexOf(tag.TagId) == -1) {
    leaves.push(tag);
  }
}

第三步的代码:

function getTagById(id) {
  for (var i = 0; i < originData.length; ++i) {
    var tag = originData[i];
    if (tag.TagId == id) {
      return tag;
    }
  }
  // If you finish the loop without returning, a ParentTagId is wrong.
  return null;
}

第 4 步的代码:

function getPath(path, currentTag) {
   if (currentTag == null) {
     // If you end up in here, some ParentTagId was wrong.
     path.reverse();
     return path;
   }
   path.push(currentTag);
   var parentId = currentTag.ParentTagId;
   if (parentId == null) {
     path.reverse();
     return path;
   } else {
     return getPath(path, getTagById(parentId));
   }
 }

第 5 步的代码:

var paths = [];
for (var i = 0; i < leaves.length; ++i) {
  paths.push(getPath([], leaves[i]));
}