Как найти путь до листа в дереве решений?

Question

В наличии имеется бинарное дерево представленное следующим видом: Пример

left_children =  [1, 3, 5, 7, -1, 9, 11, -1, -1, -1, -1, -1, -1] # левые потомки
right_children = [2, 4, 6, 8, -1, 10, 12, -1, -1, -1, -1, -1, -1] # правые потомки

Индекс массивов соответствует номеру вершины дерева.-1 в массиве означает, что у вершины по этому индексу нету детей. Пытаюсь получить словарь, где ключом является индекс вершины (листа), а значением массив целых чисел указывающих путь до этого листа. Для массивов выше нужно получить:

result = {
    4: [1, 0], # для того, чтобы попасть в узел 4 нужно пройти от узла 0 к узлу 1, а потом к узлу 4
    7: [3, 1, 0],
    8: [3, 1, 0],
    9: [5, 2, 0],
    10: [5, 2, 0],
    11:[6, 2, 0],
    12: [6, 2, 0]
}

Как это сделать?

Answer 1

Если не создавать структуру дерева:

left_children =  [1, 3, 5, 7, -1, 9, 11, -1, -1, -1, -1, -1, -1] # левые потомки
right_children = [2, 4, 6, 8, -1, 10, 12, -1, -1, -1, -1, -1, -1] # правые потомки
parents = [-1]*len(left_children)
for i in range(len(left_children)):
    if left_children[i] > 0:
        parents[left_children[i]] = i
    if right_children[i] > 0:
        parents[right_children[i]] = i

dic = {}
for i in range(len(left_children)):
    if left_children[i] > 0:
        p = []
        parent = i
        while parent >=0:
           p.append(parent)
           parent = parents[parent]
        dic[left_children[i]] = p
    if right_children[i] > 0:
        p = []
        parent = i
        while parent >=0:
           p.append(parent)
           parent = parents[parent]
        dic[right_children[i]] = p
print(dic)


{1: [0], 2: [0], 3: [1, 0], 4: [1, 0], 5: [2, 0], 6: [2, 0], 
 7: [3, 1, 0], 8: [3, 1, 0], 9: [5, 2, 0], 10: [5, 2, 0], 
 11: [6, 2, 0], 12: [6, 2, 0]}

Answer 2

Бинарное дерево можно представить как массив, знаю видео на английском Heap - Heap Sort - Heapify - Priority Queues, в начале которого есть хорошее объяснение.

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

[0, 1, 2, 3, 4, 5, 6, 7, 8, -1, -1, 9, 10, 11, 12, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1]

который в тоже время будет являться вытянутым в линию бинарным деревом. Предок узла x этого дерева находится по формуле:

x_parent_index = (x_index - 1) // 2

Пример:

Обратите внимание, что предок находится по индексу узла, а не по значению. А в результат пишем значения узлов - не индексы.

узел со значением 12 имеет индекс 14. Ищем его предка.
предок узла с индексом 14 = (14 - 1) // 2 = 6, индекс и значение совпадают.
предок узла с индексом 6 = (6 - 1) // 2 = 2, индекс и значение совпадают.
предок узла с индексом 2 = (2 - 1) // 2 = 0, индекс и значение совпадают.

Таким образом путь от узла со значением 12 (индекс которого 14) до корня - 6, 2, 0.

Решение

left_children =  [1, 3, 5, 7, -1, 9, 11, -1, -1, -1, -1, -1, -1] # левые потомки
right_children = [2, 4, 6, 8, -1, 10, 12, -1, -1, -1, -1, -1, -1] # правые потомки

bin_tree_as_array = [0]

for childs in zip(left_children, right_children):
    bin_tree_as_array.extend(childs)

result = {}

for node_idx, node_value in enumerate(bin_tree_as_array):
    # Если значение ячейки == -1, значит этого узла нет,
    # соответственно и пути к нему нет
    if node_value == -1:
        continue

    result[node_value] = []
    parent_idx = node_idx
    while parent_idx > 0:
        parent_idx = (parent_idx - 1) // 2
        result[node_value].append(bin_tree_as_array[parent_idx])

from pprint import pprint
pprint(result)

Output

{0: [],
 1: [0],
 2: [0],
 3: [1, 0],
 4: [1, 0],
 5: [2, 0],
 6: [2, 0],
 7: [3, 1, 0],
 8: [3, 1, 0],
 9: [5, 2, 0],
 10: [5, 2, 0],
 11: [6, 2, 0],
 12: [6, 2, 0]}

БЛОГ НА HUSL

Как найти путь до листа в дереве решений?

Ответы (2 шт):