从自引用数组转换为树中的嵌套数组

Question

我有自己引用的数组 table 像这样：

var obj = [
        {id:1,label:"Animal"},
        {id:2,label:"Vigitable"},
        {id:3,label:"Cats",parent:1},
        {id:4,label:"black cat",parent:3},
        {id:5,label:"orange",parent:2},
    ];

我想把它转换成这样嵌套：

var convrted = [
        {id:1,label:"Animal",children[
         {id:3,label:"Cats",parent:1,children[{id:4,label:"black cat",parent:3}]}
        ]},
        {id:2,label:"Vigitable",children[
         {id:5,label:"orange",parent:2}
        ]}
];

我希望它能无限动态地工作。

Answer 1

这将完成工作：

function nest (array) {
  nested = [];
  for (var i = 0; i < array.length; i++) {
    var parent = array[i].parent;
    if (!parent) {
      nested.push(array[i]);
    } else {
      // You'll want to replace this with a more efficient search
      for (var j = 0; j < array.length; j++) {
        if (array[j].id === parent) {
          array[j].children = array[j].children || [];
          array[j].children.push(array[i]);
        }
      }
    }
  }
  return nested;
}

第二个 for 循环是寻找父级的低效方法；如果您有多个项目要嵌套，则需要用不会扫描整个数组的项目替换它。

Answer 2

这是称为数据转换的一般 class 操作的一个实例，这可能非常有趣和有用。我的总体方法是编写递归搜索并删除可在主转换函数中使用的树函数。通常，递归函数的性能不如其等效的迭代实现，但它们更易于编写和理解。例如，这是我使用的搜索功能：

function getById(tree, id) {
    var len = tree.length;
    for (var i = 0; i < len; i++) {
        if (tree[i].id === id) {
            return tree[i];
        }
    }

    for (var i = 0; i < len; i++) {
        if (tree[i].children) {
            var node = getById(tree[i].children, id);
            if (node) {
                return node;
            }
        }
    }

    return null;
}

这是一个广度优先搜索的例子，我首先希望在树的顶层找到元素。如果我不这样做，我将在每个顶级节点的 .children 成员上调用搜索函数（如果存在）。如果失败，我 return null 表示找不到节点。

接下来，我想要一个像 Javascript 的 splice 函数一样工作的递归删除函数。我的想法是将具有给定 ID 的节点从树中拔出，以便我可以将其作为其父节点的子节点重新插入。

function removeFromTree(tree, id) {
    var node = getById(tree, id);
    if (node) {
        if (node.parent) {
            var parent = getById(tree, node.parent);
            if (parent && parent.children) {
                var index = indexInTree(parent.children, id);
                if (index != -1) {
                    return parent.children.splice(index, 1)[0];
                }
            }
        }

        var index = indexInTree(tree, id);
        return tree.splice(index, 1)[0];
    }
    return null;
}

你可以看到我使用 splice 来做实际的 "plucking"，但是 splice 需要一个索引，所以我写了一个函数来检索给定已知父节点的索引:

function indexInTree(tree, id) {
    var len = tree.length;
    for (var i = 0; i < len; i++) {
        if (tree[i].id === id) {
            return i;
        }
    }

    return -1;
}

这是一个非常简单的操作，其工作方式与数组上的 indexof 函数几乎相同，只是我们只是匹配 ID 而不是整个对象。

有了这些辅助函数，转换函数就非常简单了：

function myTransform(array) {
    var tree = array.concat([]);
    var len = array.length;
    for (var i = 0; i < len; i++) {
        if (array[i].parent && (array[i].parent !== array[i].id)) {
            var objToMove = removeFromTree(tree, array[i].id);
            if (objToMove) {
                var parent = getById(tree, objToMove.parent);
                if (parent) {
                    if (!parent.children) {
                        parent.children = [];
                    }
                    parent.children.push(objToMove);
                }
            }
        }
    }
    return tree;
}

首先，我使用 concat([]) 复制原始数组。然后我遍历原始数组。每当我遇到一个带有父 ID 的对象时，我都会使用我的删除函数从副本中提取该对象。然后，我使用广度优先搜索功能找到正确的父对象。最后，我将该对象插入到父项的子项列表中。

可以在 on JSFiddle.

中找到这个连同一些简单的测试代码来验证它是否有效

受到 Andrew Larson 的启发，我决定尝试一种构建对象而不是数组副本的实现，以便通过 id 进行搜索 O(1) 操作。好吧，假设在 Javascript 运行时内部通过键访问对象属性是 O(1)。

function otherTransform(originalArray) {
  var array = {}; // Create the object
  var len = originalArray.length;
  for (var i = 0; i < len; i++) {
    array[originalArray[i].id] = originalArray[i]; // Store by id
  }

  var nested = [];
  for (var i in array) { // Using "in" syntax to iterate over object keys
    var parent = array[i].parent;
    if (!parent) {
      nested.push(array[i]);
    } else {
      array[parent].children = array[parent].children || [];
      array[parent].children.push(array[i]);
    }
  }

  return nested;
}

现在的问题是您是否真的希望首先将数据转换为数组样式树。看起来这种新形式的嵌套树通常会更有用。

从自引用数组转换为树中的嵌套数组

Convert from self-reference array into nested array in tree

javascript

arrays

self-reference

twitter-bootstrap

angularjs