从带有父字段的平面列表构建层次结构树？

Question

我有一个包含parent字段的“页面”对象列表。这个parent字段引用列表中的另一个对象。我想根据这个字段从该列表创建一棵树形层次结构。

这是我的原始列表：

[
  {
    id: 1,
    title: 'home',
    parent: null
  },
  {
    id: 2,
    title: 'about',
    parent: null
  },
  {
    id: 3,
    title: 'team',
    parent: 2
  },
  {
    id: 4,
    title: 'company',
    parent: 2
  }
]

我想将它转换成这样的树形结构:

[
  {
    id: 1,
    title: 'home',
    parent: null
  },
  {
    id: 2,
    title: 'about',
    parent: null,
    children:  [
      {
        id: 3,
        title: 'team',
        parent: 2
      },
      {
        id: 4,
        title: 'company',
        parent: 2
      }
    ]
]

我希望有一个可重用的函数，可以随时对任意列表进行调用。有人知道如何处理这个问题吗？任何帮助或建议将不胜感激！

- TruMan1

Answer 1

function treeify(list, idAttr, parentAttr, childrenAttr) {
    if (!idAttr) idAttr = 'id';
    if (!parentAttr) parentAttr = 'parent';
    if (!childrenAttr) childrenAttr = 'children';

    var treeList = [];
    var lookup = {};
    list.forEach(function(obj) {
        lookup[obj[idAttr]] = obj;
        obj[childrenAttr] = [];
    });
    list.forEach(function(obj) {
        if (obj[parentAttr] != null) {
            if (lookup[obj[parentAttr]] !== undefined) {
                lookup[obj[parentAttr]][childrenAttr].push(obj);
            } else {
                 //console.log('Missing Parent Data: ' + obj[parentAttr]);
                 treeList.push(obj);
            }               
        } else {
            treeList.push(obj);
        }
    });
    return treeList;
};

Fiddle

->

- Amadan

---

@PhilipStanislaus: O(2n) = O(n)。我的解决方案也是O(n)。我承认我没有创造速度记录。无论是我的版本还是你的版本更快，都可以测量（两个简单循环与一个复杂循环），但我不能事先确定哪个更快。然而，它们的时间复杂度完全相同。 - Amadan

由于我收到了许多有关我的npm包performant-array-to-tree的下载量，因此我编写了一些基准测试，以测试npm上某些可用包的性能。请在此处查看结果：https://github.com/philipstanislaus/array-to-tree-benchmarks。如果您有兴趣，我们很乐意添加其他内容！ - Philip Stanislaus

你能否更新代码以处理一种轻微变体？在这种情况下，没有父ID。相反，假定如果深度低于或等于前一个列表元素，则其父项是其前任。 - SumNeuron

@SumNeuron StackOverflow规则：每个问题只能提出一个问题。可以作为解决方案考虑的一部分，请随意在此处链接新问题。 - Amadan

这段代码并没有使用递归，但是我不知道你所说的“移动值”的意思。无论如何，假设性地讲话很困难，而且这个问题与主题无关。请尝试自己翻译，如果不行，请发布一个问题，并附上指向此答案的链接；如果你愿意，也可以在这里评论新问题的链接，我会去看一下（尽管我不是C#专家）。 - Amadan

Answer 2

这个被采纳的答案对我的研究非常有帮助，但是，我不得不在脑海中解析id参数，我理解这使得函数更加灵活，但对于新接触该算法的人来说可能会有些难以理解。

如果其他人也遇到了同样的困难，这里提供基本相同的代码，但可能更容易理解：

const treeify = (arr, pid) => {
  const tree = [];
  const lookup = {};
  // Initialize lookup table with each array item's id as key and 
  // its children initialized to an empty array 
  arr.forEach((o) => {
    lookup[o.id] = o;
    lookup[o.id].children = [];
  });
  arr.forEach((o) => {
    // If the item has a parent we do following:
    // 1. access it in constant time now that we have a lookup table
    // 2. since children is preconfigured, we simply push the item
    if (o.parent !== null) {
      lookup[o.parent].children.push(o);
    } else {
      // no o.parent so this is a "root at the top level of our tree
      tree.push(o);
    }
  });
  return tree;
};

这段代码与被接受的答案相同，但有一些注释来解释代码运行过程。以下是一个使用案例，它将在页面上呈现出一系列带有内联marginLeft缩进的

，缩进基于它们在层级中所处的位置：

const arr = [
  {id: 1, title: 'All', parent: null},
  {id: 2, title: 'Products', parent: 1},
  {id: 3, title: 'Photoshop', parent: 2},
  {id: 4, title: 'Illustrator', parent: 2},
  {id: 4, title: 'Plugins', parent: 3},
  {id: 5, title: 'Services', parent: 1},
  {id: 6, title: 'Branding', parent: 5},
  {id: 7, title: 'Websites', parent: 5},
  {id: 8, title: 'Pen Testing', parent: 7}];
const render = (item, parent, level) => {
  const div = document.createElement('div');
  div.textContent = item.title;
  div.style.marginLeft = level * 8 + 'px';
  parent.appendChild(div);
  if (item.children.length) {
    item.children.forEach(child => render(child, div, ++level));
  }
  return parent;
}
const fragment = document.createDocumentFragment();
treeify(arr)
  .map(item => render(item, fragment, 1))
  .map(frag => document.body.appendChild(frag))

如果您想运行它，可以在Codepen中查看：https://codepen.io/roblevin/pen/gVRowd?editors=0010

在我看来，这个解决方案的有趣之处在于，查找表保持扁平，使用项目的ID作为键，并且只有根对象被推入到结果树列表中。然而，由于JavaScript对象具有引用性质，根对象有其子对象，子对象有其子对象，依此类推，但本质上从根部连接并形成类似于树的结构。

- Rob