admin管理员组

文章数量:1278690

Given a structure like this:

var node = { children: [] }

That is to say:

  1. It only has children property.
  2. No parent property.
  3. No nextSibling property.

How to build a flat list of arrays with paths to all the leaf nodes, using a top-down approach:

  1. The algorithm doesn't use any helper methods, just plain JavaScript.
  2. The algorithm builds the arrays as it traverses the tree from the top.

So here is an example data:

var node = {
  item: 1,
  children: [
    {
      item: 2,
      children: [
        {
          item: 3,
          children: [
            {
              item: 4,
              children: []
            },
            {
              item: 5,
              children: []
            },
            {
              item: 6,
              children: [
                {
                  item: 7,
                  children: []
                },
                {
                  item: 8,
                  children: []
                },
                {
                  item: 9,
                  children: []
                }
              ]
            }
          ]
        },
        {
          item: 10,
          children: [
            {
              item: 11,
              children: []
            },
            {
              item: 12,
              children: [
                {
                  item: 13,
                  children: []
                },
                {
                  item: 14,
                  children: []
                }
              ]
            }
          ]
        }
      ]
    }
  ]
}

And the function should return:

[
  [1, 2, 3, 4],
  [1, 2, 3, 5],
  [1, 2, 3, 6, 7],
  [1, 2, 3, 6, 8],
  [1, 2, 3, 6, 9],
  [1, 2, 10, 11],
  [1, 2, 10, 12, 13],
  [1, 2, 10, 12, 14]
]

My attempt so far has been variations of:

function aggregateNodes(node) {
  var stack = [node]
  var array = []
  while (stack.length) {
    var node = stack.pop()
    array.push(node.item)
    node.children.forEach(function(child){
      stack.push(child)
    })
  }
  return array
}

function aggregateNodesRecursive(node) {
  var array = [node.item]
  node.children.forEach(function(child){
    array.push(child.item)
    child.children.forEach(function(confusedNow){
      array.push(confusedNow.item)
      aggregateNodesRecursive(confusedNow)
    })
  })
  return array
}

Given a structure like this:

var node = { children: [] }

That is to say:

  1. It only has children property.
  2. No parent property.
  3. No nextSibling property.

How to build a flat list of arrays with paths to all the leaf nodes, using a top-down approach:

  1. The algorithm doesn't use any helper methods, just plain JavaScript.
  2. The algorithm builds the arrays as it traverses the tree from the top.

So here is an example data:

var node = {
  item: 1,
  children: [
    {
      item: 2,
      children: [
        {
          item: 3,
          children: [
            {
              item: 4,
              children: []
            },
            {
              item: 5,
              children: []
            },
            {
              item: 6,
              children: [
                {
                  item: 7,
                  children: []
                },
                {
                  item: 8,
                  children: []
                },
                {
                  item: 9,
                  children: []
                }
              ]
            }
          ]
        },
        {
          item: 10,
          children: [
            {
              item: 11,
              children: []
            },
            {
              item: 12,
              children: [
                {
                  item: 13,
                  children: []
                },
                {
                  item: 14,
                  children: []
                }
              ]
            }
          ]
        }
      ]
    }
  ]
}

And the function should return:

[
  [1, 2, 3, 4],
  [1, 2, 3, 5],
  [1, 2, 3, 6, 7],
  [1, 2, 3, 6, 8],
  [1, 2, 3, 6, 9],
  [1, 2, 10, 11],
  [1, 2, 10, 12, 13],
  [1, 2, 10, 12, 14]
]

My attempt so far has been variations of:

function aggregateNodes(node) {
  var stack = [node]
  var array = []
  while (stack.length) {
    var node = stack.pop()
    array.push(node.item)
    node.children.forEach(function(child){
      stack.push(child)
    })
  }
  return array
}

function aggregateNodesRecursive(node) {
  var array = [node.item]
  node.children.forEach(function(child){
    array.push(child.item)
    child.children.forEach(function(confusedNow){
      array.push(confusedNow.item)
      aggregateNodesRecursive(confusedNow)
    })
  })
  return array
}
  • javascript
  • arrays
  • binations
Share Improve this question edited Jan 30, 2018 at 14:52 Lance Pollard asked Jan 30, 2018 at 14:42 Lance PollardLance Pollard 79.5k98 gold badges330 silver badges607 bronze badges 3
  • 2 please add your attempt. – Nina Scholz Commented Jan 30, 2018 at 14:45
  • 1 smells like homework – Cruiser Commented Jan 30, 2018 at 14:46
  • 1 added my attempt. not homework lol – Lance Pollard Commented Jan 30, 2018 at 14:52
Add a ment  | 

5 Answers 5

Reset to default 6

A recursive approach would be:

 function traverse(node, path = [], result = []){
     if(!node.children.length)
        result.push(path.concat(node.item));
     for(const child of node.children)
         traverse(child, path.concat(node.item), result);
     return result;
 }

Or some hacky ES6:

const traverse = node => 
  (node.children.length?[]:[[node.item]]).concat(...node.children.map(child => 
     traverse(child).map(arr => 
         [node.item].concat(arr)
      )
  ));

Now calling traverse(node) will return the desired result.

You can create recursive function and first check if current element is array or object and store previous item numbers in one variable.

var node = {"item":1,"children":[{"item":2,"children":[{"item":3,"children":[{"item":4,"children":[]},{"item":5,"children":[]},{"item":6,"children":[{"item":7,"children":[]},{"item":8,"children":[]},{"item":9,"children":[]}]}]},{"item":10,"children":[{"item":11,"children":[]},{"item":12,"children":[{"item":13,"children":[]},{"item":14,"children":[]}]}]}]}]}

const result = []
function flat(data, prev = '') {
  if (Array.isArray(data)) {
    data.forEach(e => flat(e, prev))
  } else {
    prev = prev + (prev.length ? '.' : '') + data.item;
    if (!data.children.length) result.push(prev.split('.').map(Number))
    else flat(data.children, prev)
  }
}

flat(node)
console.log(result)

Here is a solution using object-scan. It's handy for all kinds of data processing - once you wrap your head around it.

// const objectScan = require('object-scan');

const find = (tree) => objectScan(['**.children'], {
  reverse: false,
  filterFn: ({ value, parents, context }) => {
    if (value.length === 0) {
      context.push(
        parents
          .filter((p) => 'item' in p)
          .map(({ item }) => item)
          .reverse()
      );
    }
  }
})(tree, []);

const node = { item: 1, children: [{ item: 2, children: [{ item: 3, children: [{ item: 4, children: [] }, { item: 5, children: [] }, { item: 6, children: [{ item: 7, children: [] }, { item: 8, children: [] }, { item: 9, children: [] }] }] }, { item: 10, children: [{ item: 11, children: [] }, { item: 12, children: [{ item: 13, children: [] }, { item: 14, children: [] }] }] }] }] };

console.log(find(node));
/* =>
  [ [ 1, 2, 3, 4 ],
    [ 1, 2, 3, 5 ],
    [ 1, 2, 3, 6, 7 ],
    [ 1, 2, 3, 6, 8 ],
    [ 1, 2, 3, 6, 9 ],
    [ 1, 2, 10, 11 ],
    [ 1, 2, 10, 12, 13 ],
    [ 1, 2, 10, 12, 14 ] ]
*/
.as-console-wrapper {max-height: 100% !important; top: 0}
<script src="https://bundle.run/[email protected]"></script>

Disclaimer: I'm the author of object-scan

Edit: And here is a more efficient solution, in case performance is important

// const objectScan = require('object-scan');

const find = (tree) => objectScan(['**.children'], {
  reverse: false,
  breakFn: ({ isMatch, parent, context: { stack } }) => {
    if (isMatch) {
      stack.push(parent.item);
    }
  },
  filterFn: ({ value: { length }, context: { result, stack } }) => {
    if (length === 0) {
      result.push([...stack]);
    }
    stack.pop();
  }
})(tree, { stack: [], result: [] }).result;

const node = { item: 1, children: [{ item: 2, children: [{ item: 3, children: [{ item: 4, children: [] }, { item: 5, children: [] }, { item: 6, children: [{ item: 7, children: [] }, { item: 8, children: [] }, { item: 9, children: [] }] }] }, { item: 10, children: [{ item: 11, children: [] }, { item: 12, children: [{ item: 13, children: [] }, { item: 14, children: [] }] }] }] }] };

console.log(find(node));
/* =>
  [ [ 1, 2, 3, 4 ],
    [ 1, 2, 3, 5 ],
    [ 1, 2, 3, 6, 7 ],
    [ 1, 2, 3, 6, 8 ],
    [ 1, 2, 3, 6, 9 ],
    [ 1, 2, 10, 11 ],
    [ 1, 2, 10, 12, 13 ],
    [ 1, 2, 10, 12, 14 ] ]
*/
.as-console-wrapper {max-height: 100% !important; top: 0}
<script src="https://bundle.run/[email protected]"></script>

Disclaimer: I'm the author of object-scan

You could take an iterative and recursive approach with a function which looks for children or returns the path the last node.

function flatNodes(node) {
    const iter = temp => ({ item, children = [] }) => children.length
            ? children.forEach(iter(temp.concat(item)))
            : nodes.push(temp.concat(item));

    var nodes = [];
    [node].forEach(iter([]));
    return nodes;
}

var node = { item: 1, children: [{ item: 2, children: [{ item: 3, children: [{ item: 4, children: [] }, { item: 5, children: [] }, { item: 6, children: [{ item: 7, children: [] }, { item: 8, children: [] }, { item: 9, children: [] }] }] }, { item: 10, children: [{ item: 11, children: [] }, { item: 12, children: [{ item: 13, children: [] }, { item: 14, children: [] }] }] }] }] };

console.log(flatNodes(node).map(a => JSON.stringify(a)));
.as-console-wrapper { max-height: 100% !important; top: 0; }

The accepted answer above throws when a node does not have a children property.

Edit: I realize that the solution I offer below does not satisfy Lance's task. However, it may be useful for flattening a tree structure into a single array.

If the goal is to just create a flat array of all the nodes' item values, this may be better:

const traverse = (node, flattened = [node.item]) => { 
    node.children?.map((child) => {
        flattened.push(child.item); 
        traverse(child, flattened);
    });
    return flattened;
}

The test:

const tree = {
    item: 'a',
    children: [
        { item: 'b'},
        {
             item: 'c', 
             children: [
                { item: 'd'}
             ]
        }
    ]
};
expect(traverse(tree)).toEqual(['a', 'b', 'c', 'd']);

本文标签： javascriptHow to flatten tree structure into array of arraysStack Overflow

版权声明：本文标题：javascript - How to flatten tree structure into array of arrays - Stack Overflow 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.betaflare.com/web/1741259764a2367388.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。