在javascript中创建一个修剪过的树 [英] create a pruned copy of tree in javascript

问题描述

我正在尝试在下面创建一个修剪过的树，我有源数据/树：

I'm trying to create a pruned version of the tree below where I have the source data/tree:

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: []
}];

以及作为输入的叶子节点数组。

and an array of leaf nodes as inputs.

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

鉴于此输入，我希望这个使用叶节点的修剪树构建从根到每个叶子的所有路径：

Given this input, I would want this pruned tree that uses the leaf nodes to build all paths from the root to each leaf:

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的其他语言的答案。

I was thinking of building the copy node by node instead of copying the data source and then taking away the paths not buildable based on the array/list of leaf nodes as I figured that would be the easiest to grok for maintainability purposes but even then, I'm puzzled as to how to coordinate the process, especially when accounting for the middle nodes that have already been added to my copy tree in progress as would be the case for '0-1-0-1' and '0-1-0-2'. At any rate, I've been stumped for awhile and threw my hands up. The code referenced is javascript but I'd be open to answers in other languages similar enough to javascript.

推荐答案

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

You could build new array/objects by finding the target key and collect all objects to it by returning the arrays with the necessary nodes.

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; }

这篇关于在javascript中创建一个修剪过的树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！