Как я могу сделать дерево для 2D-массивов

Question

Я пытаюсь преобразовать древовидную структуру данных в двумерный массив.Я пытаюсь сделать это с помощью цикла, как это.Функция childs () возвращает массив дочерних узлов.

void makeArray(a 1_level_a)
{
    for(2_level_a : 1_level_a.childs())
    {
        for(3_level_a : 2_level_a.childs())
        {

        }
    }
}

Как я могу это сделать?Любое предложение?

Answer 1

Это готовое к работе решение, которое немного модифицирует стандартную BFS и было протестировано на нескольких уровнях.Алгоритм сдвигает предыдущие строки каждый раз, когда из текущего узла добавляется несколько дочерних элементов.Кроме того, он отслеживает общий сдвиг при итерации по определенному уровню, чтобы знать, куда вставить пустые ячейки, которые всплывают от дочерних элементов.Наконец, он распространяет вниз пустые узлы-заполнители для случая, когда он попадает на лист перед конечным уровнем дерева.Когда наша очередь заполнена только этими фиктивными узлами, мы знаем, что можем остановиться.

class Node:
    def __init__(self, val):
        self.val = val
        self.children = []

    def add_children(self, children):
        self.children = children


a = Node("a")
a1 = Node("a1")
a2 = Node("a2")
a3 = Node("a3")
a11 = Node("a11")
a12 = Node("a12")
a31 = Node("a31")


a.add_children([a1, a2, a3])
a2.add_children([a11, a12])
a3.add_children([b1, b2, b3])
a12.add_children([b4])
b2.add_children([b5, b6])

arr = [[a.val]]
queue = [a]
to_process = 1
processed = 0
shifted = 0
while not all(e.val == ""  for e in queue):
    node = queue[0]
    processed+=1
    children = node.children if len(node.children) > 0 else [Node("")]
    if(to_process==processed):
       arr.append(list(map(lambda x: x.val, children)))
       to_process = len(queue)
       queue+=children
       processed = 0
       shifted = 0
    else:
        arr[-1] += list(map(lambda x: x.val, children))
        queue += children
    queue = queue[1:]
    for i in range(0, len(arr)-1):
        arr[i] = arr[i][0:shifted+1] + [""] * (len(children)-1) + arr[i][shifted+1:]
    shifted += len(children)

print("arr: " + str(arr[:-1]))

Answer 2

Вы можете написать массив строка за строкой.Следующий код предполагает, что деревья имеют только глубину 3:

array[0][0] = 1_level_a;
int last_index = 0;

for (2_level_a : 1_level_a.childs()) {
    array[1][last_index] = 2_level_a;
    for (3_level_a : 2_level_a.childs()) {
        array[2][last_index] = 3_level_a;
        last_index++;
    }
    if (2_level_a.childs().size() == 0) {
        last_index++;
    }
}

Если вам нужно обрабатывать деревья большей глубины, вы можете использовать рекурсию:

int writeTree(node, depth, last_index) {
    array[depth][last_index] = node;
    for (child : node.childs()) {
        last_index = writeTree(child, depth + 1, last_index);
    }
    if (node.childs().size() == 0) {
        last_index++;
    }
    return last_index;
}

writeTree(1_level_a, 0, 0);

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