如何将整数数组转换为树？ [英] How to convert an array of integers to a tree?

问题描述

这里是100个数字，每行10个。

  [1、2、3、4、5、6、7、8、9 ，0，
 1，2，3，4，5，6，7，8，9，0，
 1，2，3，4，5，6，7，8，9，0 ，
 1，2，3，4，5，6，6，7，8，9，0，
 1，2，3，4，5，5，6，7，8，9，0，
 1，2，3，4，5，6，7，8，9，0，
 $ 1，2，3，4，4，5，6，7，8，9，0，
 1，2，3，4，5，6，6，7，8，9，0，
 1，2，3，4，5，6，7，8，9，0，
 1 ，2，3，4，5，6，7，8，9，0] 
  

我想安排这些数到树中，每个节点最多包含5个元素。像这样的东西：

  [] 
 []，[]，[]，[] 
 []，[] ，[]，[]，[] []，[]，[]，[]，[] []，[]，[]，[]，[] []，[]，[]，[]，[] ] 
 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 
 2 7 2 7 2 7 2 7 2 7 2 7 2 7 2 7 2 7 2 7 
 3 8 3 8 3 8 3 8 3 8 3 8 3 8 3 8 3 8 8 8 
 4 9 4 9 4 9 4 9 4 9 4 9 4 9 4 9 4 9 4 9 4 9 
 5 0 5 0 5 0 5 0 5 0 5 0 5 0 5 0 5 0 5 0 
  

所以我们有4 层在树中：

1. 在第1层（顶层）中，我们有4个子代（4个数字数组）。


2. 在第2层中，我们有5个孩子（5个数字数组）。


3. 在第3层中，我们有5个孩子（5个数字）。


4. 第4层是数字。

一个人如何编写JavaScript算法来生成这样的树？规则是每个块最多5个。或更笼统地说，每个块最大 n 。

这有点类似于数组分块算法，但同时看起来更加复杂。

I已经为此困扰了几天，但这将有助于解决此问题：

基本上，如何将数组划分为大小为2的幂的桶树？

随着数组的增加，嵌套会越来越大。

另一个更简单的示例是13项数组：

  [1、2、3、4、5、6、7、8、9、0，
 1、2、3] 
  

将转换为该树：

  [] 
 []，[ ]，[] 
 1 6 1 
 2 7 2 
 3 8 3 
 4 9 
 5 0 
  

解决方案

您可以使用递归方法，从最内部的块大小开始，然后在每个级别上将输出划分。因此，只要结果长度更大，就可以通过调用函数来划分 size 参数。

  const data = [
 1，2，3，4，5，6，7，8，9，0，
 1，2 ，3、4、5、6、7、8、9、0，
 1、2、3、4、5、6、7、8、9、0，
 1、2、3 ，4、5、6、7、8、9、0，
 1、2、3、4、5、6、7、8、9、0，
 1、2、3、4 ，5、6、7、8、9、0，
 1、2、3、4、5、6、7、8、9、0，
 1、2、3、4、5 ，6、7、8、9、0，
 1、2、3、4、5、6、7、8、9、0，
 1、2、3、4、5、6 ，7，8，9，0 
] 
 
函数除法（数据，大小）{
 const result = [] 
 
 for（let i = 0; i< data.length; i + = size）{
 const chunk = data.slice（i，i + size）; 
 result.push（chunk）
} 
 
 if（result.length&size; size）{
返回除法（结果，大小）
} 
 
返回结果； 
} 
 
 const结果=除法（data，5）; 
 console.log（结果） 

Here is 100 numbers, 10 per row.

[1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0]

I would like to arrange these numbers into a tree sort of thing, where each node has max 5 elements. Something like this:

[                                                                                       ]
 [                   ],[                   ],[                   ],[                   ]
  [ ],[ ],[ ],[ ],[ ]   [ ],[ ],[ ],[ ],[ ]   [ ],[ ],[ ],[ ],[ ]   [ ],[ ],[ ],[ ],[ ]
   1   6   1   6   1     6   1   6   1   6     1   6   1   6   1     6   1   6   1   6
   2   7   2   7   2     7   2   7   2   7     2   7   2   7   2     7   2   7   2   7
   3   8   3   8   3     8   3   8   3   8     3   8   3   8   3     8   3   8   3   8
   4   9   4   9   4     9   4   9   4   9     4   9   4   9   4     9   4   9   4   9
   5   0   5   0   5     0   5   0   5   0     5   0   5   0   5     0   5   0   5   0

So we have 4 "layers" in the tree:

1. In layer 1 (top layer), we have 4 children (4 arrays of arrays of numbers).
2. In layer 2, we have 5 children (5 arrays of numbers).
3. In layer 3, we have 5 children (5 numbers).
4. Layer 4 are the numbers.

How does one write a JavaScript algorithm to generate a tree like this? The rules are, max 5 per block. Or more generally, max n per block.

This is somewhat similar to an array chunking algorithm, but at the same time way more complicated it seems.

I have been stumped on this for a few days, but it will help in solving this problem: How to divide an array into a tree of buckets sized by powers of two?

Basically, as the array gets longer, the nesting will get bigger and bigger.

Another simpler example is this, 13-item-array:

[1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
 1, 2, 3]

Which is converted into this tree:

[           ]
 [ ],[ ],[ ]
  1   6   1
  2   7   2
  3   8   3
  4   9   
  5   0   

解决方案

You could use recursive approach where you start from the inner most chunk size and then divide that output on each level up. So as long as the result length is larger then the size param you divide it by calling the function.

const data = [
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0
]

function divide(data, size) {
  const result = []

  for (let i = 0; i < data.length; i += size) {
    const chunk = data.slice(i, i + size);
    result.push(chunk)
  }

  if (result.length > size) {
    return divide(result, size)
  }

  return result;
}

const result = divide(data, 5);
console.log(result)

这篇关于如何将整数数组转换为树？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！