javascript - 使用id和parentid创建层次结构

Question

可能重复，但这与其他问题不同，它不希望将对象挂接到另一个问题。我想创建一个包含层次结构数据的新对象/数组

所以我有这些数据集：

var sets = {
    'dataSet1': {
        'ID': '1',
        'ParentID': '0'
    },

    'dataSet2': {
        'ID': '2',
        'ParentID': '1'
    },

    'dataSet3': {
        'ID': '3',
        'ParentID': '1'
    },

     'dataSet4': {
         'ID': '4',
         'ParentID': '3'
    }
}

我想遍历它们，并使用ID和ParentID动态创建层次结构。我想将处理的结果输出为：

var tiers = {
     'tier1':[
     {
        'parentid':'0',
        'id':'1'
     }
     ]

    ,'tier2':[
     {
        'parentid':'1',
        'id':'2'
     },
     {
        'parentid':'1',
        'id':'3'
     }
     ]
    ,'tier3':[
     {
        'parentid':'3',
        'id':'4'
     }
     ]
}

基本上，分层对象将包含包含具有id和parent id字段的对象的分层数组。

因此，当我访问数据时，我要做的就是通过tiers ['tier2'] [1]获得它们。我需要做的就是将数据组织到一个层次结构中。注意：本机js

这是我目前的尝试，但这仅适用于层次结构顶部的一个，第二层及以下是最大的问题

var datasetobj = sets;
var hierarchy = tiers;
for (x in datasetobj) {

        if (datasetobj[x]['ParentID'] == 0) {
            hierarchy['tier1'].push({
                'parentid': datasetobj[x]['ParentID'],
                'id': datasetobj[x]['ID']
            });
        }

    }

现在，如果我要通过使用静态方法来限制程序可以处理的层数，然后检查每个ID然后插入层，这将相当容易。但这不完全是OOP的处理方法。

Answer 1

您的问题需要遍历依赖关系树，同时跟踪深度。您可以使用简单的depth-first-traversal来解决问题，该recursion使用递归并增加深度。

由于缺乏解释，我不得不道歉。如果您以后需要它们，我将添加更多详细信息，但我必须运行。希望这有助于解决您的问题。让我知道是否需要更多说明。

我还已将originalKey属性添加到分层对象，以便您可以使用originalKey访问原始对象。



更新：好的，您想要更多的解释，您将获得更多的解释。我还更改了实现以使其速度更快。


  此外，您能否提供一些链接，以链接到我可以研究这些概念的地方？您的方法对我来说是很新的


只有使用sets和一些基本的计算机科学概念才能真正解决此问题。我将解释代码，并提供一些指向良好计算机科学概念的链接。概念并不太复杂。这些是您在计算机科学本科课程中首先要学习的东西。



将hashMap转换为sets

我要做的第一件事是将您的hashMap对象转换为另一个我称为tier的对象。我将其转换为这种形式，因为在创建sets对象时，它将使“查找”更快。

这是Object.keys对象供参考：

const sets = {
  'dataSet1': {
    'ID': '1',
    'ParentID': '0'
  },

  'dataSet2': {
    'ID': '2',
    'ParentID': '1'
  },

  'dataSet3': {
    'ID': '3',
    'ParentID': '1'
  },

  'dataSet4': {
    'ID': '4',
    'ParentID': '3'
  }
};

然后执行此转换：

const hashMap = (Object
  // 1
  .keys(sets)
  // 2
  .map(datasetKey => ({
    originalKey: datasetKey,
    id: sets[datasetKey].ID,
    parentId: sets[datasetKey].ParentID
  }))
  // 3
  .reduce((hashMap, value) => {
    // 4
    const hashMapKey = 'hasParentId' + value.parentId;
    // 5
    if (hashMap[hashMapKey] === undefined) {
      hashMap[hashMapKey] = [];
    }
    // 6
    hashMap[hashMapKey].push(value);
    // 7
    return hashMap;
  }, {})
);

这导致该对象：

{
  "hasParentId0": [
    {
      "originalKey": "dataSet1",
      "id": "1",
      "parentId": "0"
    }
  ],
  "hasParentId1": [
    {
      "originalKey": "dataSet2",
      "id": "2",
      "parentId": "1"
    },
    {
      "originalKey": "dataSet3",
      "id": "3",
      "parentId": "1"
    }
  ],
  "hasParentId3": [
    {
      "originalKey": "dataSet4",
      "id": "4",
      "parentId": "3"
    }
  ]
}

所以一步一步来：


使用 sets从对象 Array.prototype.map获取键数组
使用 Object.keys将创建数组的每个键从调用 originalKey映射到新对象。该对象具有3个属性： id， parentId， Array.prototype.reduce
使用 graph将映射对象的数组（在上一步中创建）简化为单个对象。 Array.prototype.reduce的第一个参数是带有两个参数的“ reducer”函数。 “ reducer”函数的第一个参数是“累加器”，第二个参数是数组中的项。该reducer将被调用多次，一次调用数组中的每个项目。 reducer函数返回一个累加器，并且该累加器将在此内部函数的下一次调用中使用（因此，数组中的所有项目都将减少到累加器中）。 Array.prototype.reduce的第二个参数是初始累加器。在这种情况下，初始累加器为空对象 {}。
在reducer函数内部，我们创建一个字符串 hashMapKey。该字符串将用作累加器的键。
此转换期望每个 hashMap[hashMapKey]是一个数组。在这里，我们检查 hashMap[hashMapKey]的值是否为数组，如果不是，则将其设为一个。
现在我们知道在 hashMap[hashMapKey]处有一个数组，我们可以将 value推入该数组。请记住， value是我们从步骤2映射的对象。
返回修改后的 hashMap用作下一个“ reducer”调用的“累加器”。


归约完成后， hashMap包含正确的变换。下一步需要快速从 sets转换为 hashMap。

将 hashMap转换为 tier

这是计算机科学思想的发源地。上面的结构包含一个隐含的 depth-first-traversal，其中每个节点（aka点）是 sets中的对象，每个边都是通过属性 ParentID的有向关系。

为了创建所需的结构，需要在跟踪深度的同时执行 traverse遍历此图。

这是代码：

// 1
const tier = {};
let maxDepth = 0;

// 2
function traverse(currentParentId, depth) {
  // 3
  if (depth > maxDepth) {
    maxDepth = depth;
  }
  // 4
  const childrenOfCurrentParent = hashMap['hasParentId' + currentParentId]

  // 5
  if (childrenOfCurrentParent === undefined) {
    return;
  }

  // 6
  childrenOfCurrentParent.forEach(value => {
    // 7
    const tierKey = 'tier' + depth;
    if (tier[tierKey] === undefined) {
      tier[tierKey] = [];
    }
    // 8
    tier[tierKey].push(value);
    // 9
    traverse(value.id, depth + 1);
  });
}

创建一个空对象来存储层。 （可选）创建一个用于保留最大深度的变量。如果要将tiers对象转换为tiers数组，这将很有用。
定义一个带有两个参数的函数 currentParentId： depth和 currentParentId。 currentParentId是用于标识当前父代ID的密钥。最初使用 0的 depth和 0的 maxDepth调用此函数。一旦我们看一下代码的实现，这将更有意义。
重新分配 childrenOfCurrentParent
从查找表中获取 childrenOfCurrentParent。明白我们为什么做到了吗？在此表中查找值非常快:)
如果没有任何 Array.prototype.forEach，请不要执行任何操作。
使用 recursion遍历 childrenOfCurrentParent。 value还是转换中映射对象的 value。
创建一个 tierKey来存储 value在其中。如果未初始化数组，请对其进行初始化。
按下 value
使用 ，从自身内部再次调用 traverse函数，以更改 currentParrentId并递增 depth。从第3步开始重复，直到没有其他物品可放置为止。简而言之，这基本上是深度优先遍历




将 tier转换为 tierArray

我认为这是不言自明的。由于这些层是一组有序项目，因此最好将其存储在数组中。这就是为什么我们要跟踪 maxDepth的原因。



工作片段

const sets = {
  'dataSet1': {
    'ID': '1',
    'ParentID': '0'
  },

  'dataSet2': {
    'ID': '2',
    'ParentID': '1'
  },

  'dataSet3': {
    'ID': '3',
    'ParentID': '1'
  },

  'dataSet4': {
    'ID': '4',
    'ParentID': '3'
  }
};

// `hashMap` is a data transform
// see the `console.log` of this transform
const hashMap = (Object
  // grab the keys of the object `sets`
  .keys(sets)
  // then map every key to a new object
  .map(datasetKey => ({
    originalKey: datasetKey,
    id: sets[datasetKey].ID,
    parentId: sets[datasetKey].ParentID
  }))
  // reduce the new objects into a single object
  .reduce((hashMap, value) => {
    // create a key to store the `value`
    const hashMapKey = 'hasParentId' + value.parentId;
    // if `hashMap[hashMapKey]` isn't intialized yet,
    // initialize it to an array
    if (hashMap[hashMapKey] === undefined) {
      hashMap[hashMapKey] = [];
    }
    // then push the value (the objects created above)
    hashMap[hashMapKey].push(value);
    // return the hashMap
    return hashMap;
  }, {})
);

console.log('hashMap', hashMap);

// create an object to store the `tier`s in.
const tier = {};
// keep track of the `maxDepth` in case you want to transform `tier` to an array
let maxDepth = 0;

// this is a recursive function to traverse your graph
// this implements a depth-first-traversal keeping track of the `depth`
function traverse(currentParentId, depth) {
  if (depth > maxDepth) {
    maxDepth = depth;
  }
  const childrenOfCurrentParent = hashMap['hasParentId' + currentParentId]

  // if there are no children of the currentParent
  if (childrenOfCurrentParent === undefined) {
    return;
  }

  childrenOfCurrentParent.forEach(value => {
    const tierKey = 'tier' + depth;
    if (tier[tierKey] === undefined) {
      tier[tierKey] = [];
    }
    tier[tierKey].push(value);
    traverse(value.id, depth + 1);
  });
}

// call the function to start the traversal
// using 0 as the first `currentParentId` and
// using 0 as the first `depth` value
traverse(0, 0);


// the tier object is now created
console.log('tier', tier);

// but it might be more natural to have `tier` as an array
const tierArray = [];
for (let i = 0; i < maxDepth; i += 1) {
  tierArray[i] = tier['tier' + i];
}

console.log('tierArray', tierArray);

ew，真是个答案。希望这可以帮助！