数组中嵌套对象的JavaScript递归函数

Question

我正在尝试实现一种算法来生成带有分层标题的表格。这些可以无限嵌套。呈现的表格标记的 html 示例如下:

    <table border=1>
      <thead>
        <tr>
          <th colspan="6">
            Super one
          </th>
          <th colspan="6">
            Super two
          </th>
        </tr>
        <tr>
          <th colspan="3">Head one</th>
          <th colspan="3">Head two</th>
          <th colspan="4">Head three</th>
          <th colspan="2">Head four</th>
        </tr>
        <tr>
          <th>Sub one</th>
          <th>Sub two</th>
          <th>Sub three</th>
          <th>Sub four</th>
          <th>Sub five</th>
          <th>Sub six</th>
          <th>Sub seven</th>
          <th>Sub eight</th>
          <th>Sub nine</th>
          <th>Sub ten</th>
          <th>Sub eleven</th>
          <th>Sub twelve</th>
        </tr>
      </thead>
    </table>  

表的配置应作为 JavaScript 对象以这种格式传递:

var columns = [
  {
    label: 'Super one',
    children: [
      {
        label: 'Head one',
        children: [
          {label: 'Sub one'},
          {label: 'Sub two'},
          {label: 'Sub three'}
        ]
      },
      {
        label: 'Head two',
        children: [
          {label: 'Sub four'},
          {label: 'Sub five'},
          {label: 'Sub six'}
        ]
      }
    ]
  },
  {
    label: 'Super two',
    children: [
      {
        label: 'Head three',
        children: [
          {label: 'Sub seven'},
          {label: 'Sub eight'},
          {label: 'Sub nine'},
          {label: 'Sub ten'}
        ]
      },
      {
        label: 'Head four',
        children: [
          {label: 'Sub eleven'},
          {label: 'Sub twelve'}
        ]
      }
    ]
  }
];

现在，让我们忘掉 html 渲染，只关注应该迭代配置的算法，以便获得格式简单的二维数组:

var structure = [
  [6, 6],
  [3, 3, 4, 2],
  [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
]; 

其中每个条目表示包含其列定义 (td) 的表行 (tr)，数字表示 colspan。如何实现该算法？

目前我创建了一个递归函数，它根据配置返回总列数:

function getColumnCount(columns) {
  var count = 0;
  for (var i=0; i<columns.length; i++) {
    var col = columns[i];
    if (col.children && col.children.length > 0) {
      count += getColumnCount(col.children);
    }
    else {
      count++;
    }
  }
  return count;
}

它按预期工作，但我一直在尝试生成“结构”数组……我当前(令人尴尬的)代码尝试是这样的:

function getStructure(columns) {
  var structure = [[]];
  for (var i=0; i<columns.length; i++) {
    var col = columns[i];
    if (col.children && col.children.length > 0) {
      console.log(col.label, '(with children)');
      schema[structure.length - 1].push(getColumnCount(col.children));
      getStructure(col.children, schema);
    }
    else {
      console.log(col.label, '(orphan)');
      schema[structure.length - 1].push(1);
    }
  }
  return structure; 
}

我感觉自己真的很笨，因为我知道这应该是一个相对容易的任务，但是当涉及到递归函数时，我的大脑似乎拒绝协作 XD

你能帮帮我吗？

Answer 1

棘手的部分是计算跨度，即给定节点下的叶节点数或 1 该节点本身就是叶节点。该值可以递归定义如下:

 numberOfLeaves(node) = if node.children then 
       sum(numberOfLeaves(child) for child in node.children) 
       else 1

剩下的就很简单了:

var columns = [
    {
        label: 'Super one',
        children: [
            {
                label: 'Head one',
                children: [
                    {
                        label: 'Sub one',
                        children: [
                            {label: 1},
                            {label: 2},
                        ]
                    },
                    {label: 'Sub two'},
                    {label: 'Sub three'}
                ]
            },
            {
                label: 'Head two',
                children: [
                    {label: 'Sub four'},
                    {label: 'Sub five'},
                    {label: 'Sub six'}
                ]
            }
        ]
    },
    {
        label: 'Super two',
        children: [
            {
                label: 'Head three',
                children: [
                    {label: 'Sub seven'},
                    {label: 'Sub eight'},
                    {label: 'Sub nine'},
                    {label: 'Sub ten'}
                ]
            },
            {
                label: 'Head four',
                children: [
                    {label: 'Sub eleven'},
                    {label: 'Sub twelve'}
                ]
            }
        ]
    }
];

var tab = [];

function calc(nodes, level) {
    tab[level] = tab[level] || [];

    var total = 0;

    nodes.forEach(node => {
        var ccount = 0;
        if ('children' in node) {
            ccount = calc(node.children, level + 1);
        } else {
            ccount = 1;
        }
        tab[level].push({
            label: node.label,
            span: ccount
        });

        total += ccount;
    });

    return total;
}

calc(columns, 0);
console.log(tab);

function makeTable(tab) {
    html = "<table border=1>";
    tab.forEach(row => {
        html += "<tr>";
        row.forEach(cell => {
            html += "<td colspan=" + cell.span + ">" + cell.label + "</td>"
        });
        html += "</tr>"
    })
    return html + "</table>";
}

document.write(makeTable(tab))