преобразовать плоский список в дерево с ограниченным количеством узлов на глубину

Question

Я ищу решение для следующей задачи:

У меня плоский список с большим количеством данных.

Теперь я хочу преобразовать этот список в дерево со следующими правилами:

• все мои списки должны быть листами
• количество узлов на глубину дерева должно быть ограничено определенным пределом
• узлы могут быть вложены с неограниченной глубиной

Я думаю, что это похоже на k-арное дерево (с k - предел узла на уровень), но, возможно, эта вещь имеет другое имя.

Фоном для этой задачи является проблема визуализации моего списка в радиальном дереве. Отображение всех листьев на первом уровне в радиальном дереве не выглядит хорошо, когда их слишком много. Поэтому я думаю, что лучше будет добавить несколько узлов для группировки моих данных, когда достигнут предел уровня. Полученное дерево должно отображать листья лучше визуально.

Есть ли алгоритм или даже лучше реализация для этой задачи?

Спасибо за любой указатель или информацию.

Answer 1

Допустим, N, количество элементов в вашем списке равно 4 и K=2.Таким образом, это будет двоичное дерево.

Шаг 1: Создайте 2 узла

  P1        P2

1    2    3    4

Шаг 2: Создайте связи между двумя узлами и K конечных узлов

  P1        P2
 /  \      /  \
1    2    3    4

Шаг 3: Создать еще один узел

       P5

  P1        P2
 /  \      /  \
1    2    3    4

Шаг 4: Создать связи между этим узлом и двумя предыдущими узлами, которые вы создали

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

Видите шаблон?Вы можете сделать это довольно легко итеративно для любых таких N и K.Вы должны немного беспокоиться о случаях, когда N не является идеальной силой K.В основном, число дочерних элементов каждого узла не превышает ceil (N / K).