Получить все ветви (от корня до листа) двоичного дерева в виде списков в Python - PullRequest
Новая
       33

Получить все ветви (от корня до листа) двоичного дерева в виде списков в Python

0 голосов
/ 08 июля 2019

Я сделал двоичное дерево в Python в форме словаря, в котором каждая запись имеет форму key: value. Например, 

btree = {..., 
         node1: [value, nodeNoOfLeftChild, nodeNoOfRightChild],
         ... }

Все узлы имеют записи в одном и том же формате, но некоторые узлы также могут отсутствовать.

Например, если узел № 5 имеет значение X, а номера дочерних узлов 12 и 13, запись выглядит следующим образом.

tree[5] = [X, 12, 13]

Но возможно, что узел 13 не существует, поэтому у узла 5 есть только один дочерний элемент. Также возможно, что оба узла 12 и 13 не существуют, что делает узел 5 конечным узлом.

Я хочу получить все ветви (от корня до листа) дерева в виде списков, но проблема в том, что длина списка варьируется в зависимости от ветвления.

Как мне сделать функцию, которая берет в этом словаре и выдает списки?

Ответы [ 3 ]

1 голос
/ 08 июля 2019

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

from pprint import pprint

btree = {
    1: ["Node 1", 2, 3],
    2: ["Node 2", 4, 0],
    3: ["Node 3", 0, 0],
    4: ["Node 4", 5, 0],
    5: ["Node 5", 6, 0],
    6: ["Node 6", 7, 0],
    7: ["Node 7", 0, 0],
}

def do_node(id, path, result):
    node = btree[id]
    if node[1] == 0 and node[2] == 0:
        # This node has no children, and is thus a leaf node, so add it to the result list
        result.append(path + [node[0]])
    else:
        # This is a non-leaf node, so process its children
        if node[1] != 0:
            do_node(node[1], path + [node[0]], result)
        if node[2] != 0:
            do_node(node[2], path + [node[0]], result)


def print_leaf_paths(tree):
    result = []
    do_node(1, [], result)
    pprint(result)

print_leaf_paths(btree)

В образце дерева есть два листовых узла, один сразу и один на 5 уровней. Результат: 

[['Node 1', 'Node 2', 'Node 4', 'Node 5', 'Node 6', 'Node 7'],
 ['Node 1', 'Node 3']]
0 голосов
/ 08 июля 2019

Вы можете использовать рекурсию с генератором: 

tree = {1: ['Node 1', 2, 3], 2: ['Node 2', 4, 0], 3: ['Node 3', 0, 0], 4: ['Node 4', 5, 0], 5: ['Node 5', 6, 0], 6: ['Node 6', 7, 0], 7: ['Node 7', 0, 0]}
def paths(a, c = []):
  if a not in tree:
    yield tuple(c)
  else:
    for i in tree[a][1:]:
      yield from paths(i, c+[tree[a][0]])

print(list(set(paths(1))))

Выход: 

[('Node 1', 'Node 2', 'Node 4', 'Node 5', 'Node 6'), ('Node 1', 'Node 2'), ('Node 1', 'Node 2', 'Node 4'), ('Node 1', 'Node 3'), ('Node 1', 'Node 2', 'Node 4', 'Node 5'), ('Node 1', 'Node 2', 'Node 4', 'Node 5', 'Node 6', 'Node 7')]
0 голосов
/ 08 июля 2019

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

from pprint import pprint

btree = {
    1: ["Node 1", 2, 3],
    2: ["Node 2", 4, 0],
    3: ["Node 3", 0, 0],
    4: ["Node 4", 5, 0],
    5: ["Node 5", 6, 0],
    6: ["Node 6", 7, 0],
    7: ["Node 7", 0, 0],
}

# Process a single node in a binary tree
def do_node(id, path, result):
    node = btree[id]
    if node[1] == 0 and node[2] == 0:
        # No children, so this is a leaf node.  Add it to the result list
        result.append(path + [node[0]])
    else:
        # Non-leaf node, so process the node's children recursively.
        if node[1] != 0:
            do_node(node[1], path + [node[0]], result)
        if node[2] != 0:
            do_node(node[2], path + [node[0]], result)


# Build a list of "paths" to each of the leaf nodes in a binary tree
def print_leaf_paths(tree):
    result = []
    do_node(1, [], result)
    pprint(result)

print_leaf_paths(btree)

В образце дерева есть два листовых узла, один прямо под корнем и один на 5 уровней ниже. Результат: 

[['Node 1', 'Node 2', 'Node 4', 'Node 5', 'Node 6', 'Node 7'],
 ['Node 1', 'Node 3']]
...