如何在 JavaScript 中使用缩进从平面列表构建树？

Question

面对这个问题时，我总是很挣扎，这需要一些认真的工作。我目前正在尝试解决这个问题，可能需要几天时间。想看看您是否有解决此问题的系统或简单方法。基本上，假设您有一个 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))}

Answer 1

它是一个堆栈，因为它是顺序的。是这样的吗？

我们假设文件夹结构是完全“展开”的，因此必须在当前文件夹之前检查每个文件夹的父文件夹（最低的文件夹除外，父文件夹是根目录）。父级还必须具有较低的“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));

Answer 2

有趣的练习。这是另一种方法，它比之前的解决方案更冗长，但也适用于 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>