如何在JavaScript中使用缩进从一个扁平列表构建树形结构？

Question

如何在JavaScript中使用缩进从一个扁平列表构建树形结构？

4

每当我面临这个问题时，我总是很费力，需要做一些认真的工作。我目前正在尝试解决这个问题，可能需要几天时间。想知道您是否有解决此问题的系统或简单方法。

基本上，假设你有一个带有左侧缩进的DOM节点的平坦列表，步骤为15px。在视觉上，它形成了一个类似文件浏览器的树形结构。但在DOM中，它被实现为一个平面列表。那么如何遍历该列表并构建树形结构？

<div style='padding-left: 0px'>A</div>
<div style='padding-left: 15px'>AA</div>
<div style='padding-left: 15px'>AB</div>
<div style='padding-left: 30px'>ABA</div>
<div style='padding-left: 30px'>ABB</div>
<div style='padding-left: 45px'>ABBA</div>
<div style='padding-left: 45px'>ABBB</div>
<div style='padding-left: 45px'>ABBC</div>
<div style='padding-left: 30px'>ABC</div>
<div style='padding-left: 15px'>AC</div>
<div style='padding-left: 0px'>B</div>
<div style='padding-left: 0px'>C</div>
...

那么它应该变成一个像这样的JSON树：

[ 
  {
    title: 'A',
    children: [
      {
        title: 'AA',
        children: []
      },
      {
        title: 'AB',
        children: [
          {
            title: 'ABA',
            children: []
          },
          {
            title: 'ABB',
            children: [
              {
                title: 'ABBA',
                children: []
              },
              {
                title: 'ABBB',
                children: []
              },
              {
                title: 'ABBC',
                children: []
              }
            ]
          },
          {
            title: 'ABC',
            children: []
          }
        ]
      },
      {
        title: 'AC'
      }
    ]
  },
  {
    title: 'B',
    children: []
  },
  {
    title: 'C',
    children: []
  }
]

你如何做到这一点？我感到迷失了：

let tree = []
let path = [0]

let items = list('div')

items.forEach(item => {
  let left = parseInt(item.style[`padding-left`] || 0) % 15
  let set = tree
  let p = path.concat()
  while (left) {
    let x = p.shift()
    set[x] = set[x] || { children: [] }
    set = set[x].children
    left--
  }
})

function list(s) {
  return Array.prototype.slice.call(document.querySelectorAll(s))
}

- Lance

2个回答

1

有趣的练习。这里提供另一种方法，比之前的解决方案更详细一些，但也可以使用DOM节点而不是字符串HTML。

const buildTree = (selector) => {
    const elems = [...document.querySelectorAll(selector)]
              .map((el,i)=>({el, title: el.textContent, idx:i, inset: parseInt(el.style.paddingLeft)}));

    const getChildren = ({inset:pInset, idx:start}) => {
      const nextParentIdx = elems.findIndex(({inset, idx}, i)=> inset <= pInset && i >start);
      const desc = elems.slice(start, nextParentIdx+1 )
                  .filter(({inset})=>inset-pInset === 15);
      return desc.map(getItem); 
    }

    const getItem = (o)=>{
      return {title: o.title, children: getChildren(o)}
    }
    
    return elems.filter(({inset})=>!inset).map(getItem)
}

   
console.log(JSON.stringify(buildTree('div'),null, 4))

.as-console-wrapper {   max-height: 100%!important;top:0;}

<div style='padding-left: 0px'>A</div>
<div style='padding-left: 15px'>AA</div>
<div style='padding-left: 15px'>AB</div>
<div style='padding-left: 30px'>ABA</div>
<div style='padding-left: 30px'>ABB</div>
<div style='padding-left: 45px'>ABBA</div>
<div style='padding-left: 45px'>ABBB</div>
<div style='padding-left: 45px'>ABBC</div>
<div style='padding-left: 30px'>ABC</div>
<div style='padding-left: 15px'>AC</div>
<div style='padding-left: 0px'>B</div>
<div style='padding-left: 0px'>C</div>

- charlietfl

你知道我只是举了字符串HTML作为例子，当然这只是个例子。我当时在手机上，而且不想搞乱它 :) - גלעד ברקן

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- גלעד ברקן · Accepted Answer

由于它是顺序的, 所以它是一个堆栈。类似于这样的东西吗？

我们假设文件夹结构是完全“展开”的，因此每个文件夹的父文件夹(除了最低层，其父级为根)必须在当前文件夹之前被检查过。父文件夹还必须具有“padding-left”赋值更低。

ptrs是一个堆栈，我们向其附加下一个被检查的文件夹的引用。堆栈顶部（末尾）的文件夹是我们检查的最后一个文件夹。如果堆栈顶部的这些文件夹具有高于或等于“padding-left”的赋值，则它们不可能是当前文件夹的父文件夹；并且在当前文件夹之后我们不可能会有更多这些文件夹的子文件夹，因此我们将它们移除(弹出)，直到找到最后一个具有较低“padding-left”的放置的文件夹。

function getData(s){
  const left = +s.match(/\d+/)[0];
  const title = s.match(/[A-Z]+/)[0];
  return [left, title];
}

function f(divs){
  const tree = {
    title: 'root',
    children: []
  };
  const ptrs = [[0, tree]]; // stack
  for (let str of divs){
    const [left, title] = getData(str);
    while (ptrs.length && ptrs[ptrs.length-1][0] >= left)
      ptrs.pop();
    parent = ptrs.length ? ptrs[ptrs.length-1][1] : tree;
    const obj = {title: title, children: []};
    parent.children.push(obj);
    ptrs.push([left, obj]);
  }
  return tree;
}

var divs = [
  "<div style='padding-left: 0px'>A</div>",
  "<div style='padding-left: 15px'>AA</div>",
  "<div style='padding-left: 15px'>AB</div>",
  "<div style='padding-left: 30px'>ABA</div>",
  "<div style='padding-left: 30px'>ABB</div>",
  "<div style='padding-left: 45px'>ABBA</div>",
  "<div style='padding-left: 45px'>ABBB</div>",
  "<div style='padding-left: 45px'>ABBC</div>",
  "<div style='padding-left: 30px'>ABC</div>",
  "<div style='padding-left: 15px'>AC</div>",
  "<div style='padding-left: 0px'>B</div>",
  "<div style='padding-left: 0px'>C</div>"
]

console.log(f(divs));