时间戳

首页 > 解决方案 > 在 javascript 中创建树的修剪副本

javascript - 在 javascript 中创建树的修剪副本

问题描述

我正在尝试在我拥有源数据/树的下面创建一个修剪后的树版本：

const treeData = [{
  title: '0-0',
  key: '0-0',
  children: [{
    title: '0-0-0',
    key: '0-0-0',
    children: [
      { title: '0-0-0-0', key: '0-0-0-0', children: [] },
      { title: '0-0-0-1', key: '0-0-0-1', children: [] },
      { title: '0-0-0-2', key: '0-0-0-2', children: [] },
    ],
  }, {
    title: '0-0-1',
    key: '0-0-1',
    children: [
      { title: '0-0-1-0', key: '0-0-1-0', children: [] },
      { title: '0-0-1-1', key: '0-0-1-1', children: [] },
      { title: '0-0-1-2', key: '0-0-1-2', children: [] },
    ],
  }, {
    title: '0-0-2',
    key: '0-0-2',
    children: []
  }],
}, {
  title: '0-1',
  key: '0-1',
  children: [
    { title: '0-1-0-0', key: '0-1-0-0', children: [] },
    { title: '0-1-0-1', key: '0-1-0-1', children: [] },
    { title: '0-1-0-2', key: '0-1-0-2', children: [] },
  ],
}, {
  title: '0-2',
  key: '0-2',
  children: []
}];

和一个叶节点数组作为输入。

const leafNodes = ['0-0-1-2', '0-1-0-1', '0-1-0-2']

给定这个输入，我想要这棵修剪过的树，它使用叶子节点来构建从根到每个叶子的所有路径：

const pruned [{
  title: '0-0',
  key: '0-0',
  children: [{
    title: '0-0-1',
    key: '0-0-1',
    children: [
      { title: '0-0-1-2',
        key: '0-0-1-2',
        children: []
      }
    ]
  }]
  }, {
  title: '0-1',
  key: '0-1',
  children: [{
    title: '0-1-0-1',
    key: '0-1-0-1',
    children: []
  }, {
    title: '0-1-0-2',
    key: '0-1-0-2',
    children: []
  }]
}]

我正在考虑逐个节点构建复制节点，而不是复制数据源，然后根据叶节点的数组/列表删除不可构建的路径，因为我认为这对于可维护性目的来说是最容易理解的，但即便如此，我对如何协调过程感到困惑，尤其是在考虑到已经添加到我的复制树中的中间节点时，例如“0-1-0-1”和“0-1”的情况-0-2'。无论如何，我已经被难住了一段时间，举起手来。引用的代码是 javascript，但我愿意接受与 javascript 足够相似的其他语言的答案。

标签： javascriptalgorithm

解决方案

您可以通过找到目标键来构建新的数组/对象，并通过返回具有必要节点的数组来收集所有对象。

function getParts(array, leafes) {
    var result = [];
    array.forEach(o => {
        var children;
        if (leafes.includes(o.key)) {
            result.push(o);
            return;
        }
        children = getParts(o.children, leafes);
        if (children.length) {
            result.push(Object.assign({}, o, { children }));                    
        }
    });
    return result;
}

const
    treeData = [{ title: '0-0', key: '0-0', children: [{ title: '0-0-0', key: '0-0-0', children: [{ title: '0-0-0-0', key: '0-0-0-0', children: [] }, { title: '0-0-0-1', key: '0-0-0-1', children: [] }, { title: '0-0-0-2', key: '0-0-0-2', children: [] }] }, { title: '0-0-1', key: '0-0-1', children: [{ title: '0-0-1-0', key: '0-0-1-0', children: [] }, { title: '0-0-1-1', key: '0-0-1-1', children: [] }, { title: '0-0-1-2', key: '0-0-1-2', children: [] }] }, { title: '0-0-2', key: '0-0-2', children: [] }] }, { title: '0-1', key: '0-1', children: [{ title: '0-1-0-0', key: '0-1-0-0', children: [] }, { title: '0-1-0-1', key: '0-1-0-1', children: [] }, { title: '0-1-0-2', key: '0-1-0-2', children: [] }] }, { title: '0-2', key: '0-2', children: [] }],
    leafNodes = ['0-0-1-2', '0-1-0-1', '0-1-0-2'],
    pruned = getParts(treeData, leafNodes);

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

推荐阅读