CODEWITHSUNDEEP
javaalgorithmtree
user678898
user678898

Reputation: 49

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:

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 able 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.

Upvotes: 2

Views: 985

Answers (1)

tskuzzy
tskuzzy

Reputation: 36456

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).

Upvotes: 4

Related Questions