如何在 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){&nbsp; const left = +s.match(/\d+/)[0];&nbsp; const title = s.match(/[A-Z]+/)[0];&nbsp; return [left, title];}function f(divs){&nbsp; const tree = {&nbsp; &nbsp; title: 'root',&nbsp; &nbsp; children: []&nbsp; };&nbsp; const ptrs = [[0, tree]]; // stack&nbsp; for (let str of divs){&nbsp; &nbsp; const [left, title] = getData(str);&nbsp; &nbsp; while (ptrs.length && ptrs[ptrs.length-1][0] >= left)&nbsp; &nbsp; &nbsp; ptrs.pop();&nbsp; &nbsp; parent = ptrs.length ? ptrs[ptrs.length-1][1] : tree;&nbsp; &nbsp; const obj = {title: title, children: []};&nbsp; &nbsp; parent.children.push(obj);&nbsp; &nbsp; ptrs.push([left, obj]);&nbsp; }&nbsp; return tree;}var divs = [&nbsp; "<div style='padding-left: 0px'>A</div>",&nbsp; "<div style='padding-left: 15px'>AA</div>",&nbsp; "<div style='padding-left: 15px'>AB</div>",&nbsp; "<div style='padding-left: 30px'>ABA</div>",&nbsp; "<div style='padding-left: 30px'>ABB</div>",&nbsp; "<div style='padding-left: 45px'>ABBA</div>",&nbsp; "<div style='padding-left: 45px'>ABBB</div>",&nbsp; "<div style='padding-left: 45px'>ABBC</div>",&nbsp; "<div style='padding-left: 30px'>ABC</div>",&nbsp; "<div style='padding-left: 15px'>AC</div>",&nbsp; "<div style='padding-left: 0px'>B</div>",&nbsp; "<div style='padding-left: 0px'>C</div>"]console.log(f(divs));

Answer 2

有趣的练习。这是另一种方法，它比之前的解决方案更冗长，但也适用于 dom 节点而不是字符串 htmlconst buildTree = (selector) => {&nbsp; &nbsp; const elems = [...document.querySelectorAll(selector)]&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; .map((el,i)=>({el, title: el.textContent, idx:i, inset: parseInt(el.style.paddingLeft)}));&nbsp; &nbsp; const getChildren = ({inset:pInset, idx:start}) => {&nbsp; &nbsp; &nbsp; const nextParentIdx = elems.findIndex(({inset, idx}, i)=> inset <= pInset && i >start);&nbsp; &nbsp; &nbsp; const desc = elems.slice(start, nextParentIdx+1 )&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; .filter(({inset})=>inset-pInset === 15);&nbsp; &nbsp; &nbsp; return desc.map(getItem);&nbsp;&nbsp; &nbsp; }&nbsp; &nbsp; const getItem = (o)=>{&nbsp; &nbsp; &nbsp; return {title: o.title, children: getChildren(o)}&nbsp; &nbsp; }&nbsp; &nbsp;&nbsp;&nbsp; &nbsp; return elems.filter(({inset})=>!inset).map(getItem)}&nbsp; &nbsp;console.log(JSON.stringify(buildTree('div'),null, 4)).as-console-wrapper {&nbsp; &nbsp;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>