convert a flat list into a tree with limited number of nodes per depth

i'm search a solution for the following task:

i have a flat list with a lot of data.

Now i want to transfrom this list into an tree with the following rules:

• all of my listitems should be leafs
• the number of nodes per tree depth should be limit the a certain limit
• nodes can be nested with unlimited depth

i think it's like an k-ary (with k is the node limit per level) tree, but maybe this thing has annother name.

The background for this task is a visualisation problem of my list in a radial tree. Displaying all leafs on the first level in the radial tree doesn't look good when there are too much. So i think it's better to insert some nodes to group my data when the level limit is reached. The resulting tree should be ab开发者_开发百科le to display the leafs in a better visually way.

is there an algorithm or even better an implementation for this task?

Thanks for any pointer or infos.

Let's say N, the number of items in your list is 4 and K=2. So this will be a binary tree.

Step 1: Create 2 nodes

  P1        P2

1    2    3    4

Step 2: Create links between the 2 nodes and K of the leaf nodes

  P1        P2
 /  \      /  \
1    2    3    4

Step 3: Create another node

       P5

  P1        P2
 /  \      /  \
1    2    3    4

Step 4: Create the links between that node and the 2 previous nodes you created

       P5
    /      \
  P1        P2
 /  \      /  \
1    2    3    4

See the pattern? You can do this iteratively pretty easily for any such N and K. You have to worry a little about cases where N is not a perfect power of K. Basically the number of children of every node is at most ceil(N/K).