时间戳

首页 > 解决方案 > 如何在 JavaScript 中从带有缩进的平面列表构建树？

javascript - 如何在 JavaScript 中从带有缩进的平面列表构建树？

问题描述

面对这个问题，我总是很挣扎，这需要一些认真的工作。我目前正在尝试解决这个问题，可能需要几天时间。想看看您是否有解决此问题的系统或简单方法。

基本上，假设您有一个 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))
}

标签： javascriptalgorithmtree

解决方案

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

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

推荐阅读