javascript - 使用javascript反向数组遍历

Question

我正在处理需要从 child 遍历到 parent 的对象，这里的主要问题是一个 child 可以有多个 parent 。

我用 visjs 创建了树，如下所示。

我有如下的对象数组。

{
    ChildId:63
    CostObjectHierarchyId:10064
    ParentId:1
},
{
    ChildId:64
    CostObjectHierarchyId:10066
    ParentId:1
},
{
    ChildId:65
    CostObjectHierarchyId:10068
    ParentId:1
},
{
    ChildId:66
    CostObjectHierarchyId:10069
    ParentId:1
},
{
    ChildId:67
    CostObjectHierarchyId:10071
    ParentId:1
},
{
    ChildId:68
    CostObjectHierarchyId:10074
    ParentId:1
},
{
    ChildId:59
    CostObjectHierarchyId:10057
    ParentId:58
},
{
    ChildId:60
    CostObjectHierarchyId:10060
    ParentId:59
},
{
    ChildId:61
    CostObjectHierarchyId:10061
    ParentId:60
},
{
    ChildId:62
    CostObjectHierarchyId:10062
    ParentId:61
},
{
    ChildId:58
    CostObjectHierarchyId:10063
    ParentId:63
},
{
    ChildId:58
    CostObjectHierarchyId:10065
    ParentId:64
},
{
    ChildId:58
    CostObjectHierarchyId:10067
    ParentId:65
},
{
    ChildId:68
    CostObjectHierarchyId:10072
    ParentId:66
},
{
    ChildId:59
    CostObjectHierarchyId:10075
    ParentId:67
},
{
    ChildId:59
    CostObjectHierarchyId:10076
    ParentId:68
}

现在我的查询是假设我选择节点 L4 (61) 那么它应该反向遍历并且我想要拥有所有节点。预期结果为 (60,59,58,68,63,64,65,66,67)。

我正在尝试反向调用循环，直到找到父 ID“1”(全局)。但只要有多个 parent ，我就无法得到。

例子。假设我选择了 60 然后它有 59 作为 parent ，但现在 59 有 3 个 parent 58、68、67。让我如何找到这 3 个然后仍然为每个我应该能够得到他们各自的 parent 。所以 58 有三个 parent 63、64、65。那是拿不到的。

我的代码如下。

// Get Selected Node
var indEdge = _.findIndex($scope.COHData, { 'ChildId': $scope.objectId });
var itsParentId = 1;
var parentsArraySoFar = [];

_.each($scope.COHData, function (data) { // Till whole Array is traversed
    while (true) {
        if (indEdge > -1) {
            itsParentId = $scope.COHData[indEdge].ParentId; // Getting Parent Id of it.
            if (parseInt(itsParentId) === parseInt("1")) { // Will check if it's parent is 1 then stop
                parentsArraySoFar.push({ 'pid': itsParentId });
                break;
            }
            else {
                parentsArraySoFar.push({ 'pid': itsParentId });
                // Else search for next parent passing the resultant parent
                indEdge = _.findIndex($scope.COHData, { 'ChildId': itsParentId }); 
            }
        }
        else {
            break;
        }
    }
});

谢谢

Answer 1

换种方式思考

1. 构建中间数据结构，即每个项目的父级映射
2. 递归遍历所需的 child

举个例子

var items = [{
  ChildId: 63,
  CostObjectHierarchyId: 10064,
  ParentId: 1
}, {
  ChildId: 64,
  CostObjectHierarchyId: 10066,
  ParentId: 1
}, {
  ChildId: 65,
  CostObjectHierarchyId: 10068,
  ParentId: 1
}, {
  ChildId: 66,
  CostObjectHierarchyId: 10069,
  ParentId: 1
}, {
  ChildId: 67,
  CostObjectHierarchyId: 10071,
  ParentId: 1
}, {
  ChildId: 68,
  CostObjectHierarchyId: 10074,
  ParentId: 1
}, {
  ChildId: 59,
  CostObjectHierarchyId: 10057,
  ParentId: 58
}, {
  ChildId: 60,
  CostObjectHierarchyId: 10060,
  ParentId: 59
}, {
  ChildId: 61,
  CostObjectHierarchyId: 10061,
  ParentId: 60
}, {
  ChildId: 62,
  CostObjectHierarchyId: 10062,
  ParentId: 61
}, {
  ChildId: 58,
  CostObjectHierarchyId: 10063,
  ParentId: 63
}, {
  ChildId: 58,
  CostObjectHierarchyId: 10065,
  ParentId: 64
}, {
  ChildId: 58,
  CostObjectHierarchyId: 10067,
  ParentId: 65
}, {
  ChildId: 68,
  CostObjectHierarchyId: 10072,
  ParentId: 66
}, {
  ChildId: 59,
  CostObjectHierarchyId: 10075,
  ParentId: 67
}, {
  ChildId: 59,
  CostObjectHierarchyId: 10076,
  ParentId: 68
}];

function construct(items) {
  var parentMap = {};
  items.forEach(function(item) {
    var mapItem = parentMap[item.ChildId];
    if (mapItem) {
      mapItem.push(item.ParentId);
    } else {
      parentMap[item.ChildId] = [item.ParentId];
    }
  });
  return parentMap;
}

var parents = [];
var map = construct(items);

function getParents(id) {
  map[id].forEach(function(innerId) {
    if (innerId === 1) {
      return;
    }
    parents = parents.concat(innerId);
    getParents(innerId);
  });
  return parents;
}

console.log(getParents(61));