获取二叉树的所有分支（根到叶）作为 Python 中的列表

Question

我在 Python 中以字典的形式创建了一个二叉树，其中每个条目都是 key: value 的形式。例如，

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

所有节点都具有相同格式的条目，但也可能缺少一些节点。

例如，如果节点编号 5 的值为 X，并且 child 节点编号为 12 和 13，则条目如下所示。

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

但有可能节点 13 不存在，所以节点 5 只有一个 child。也有可能节点 12 & 13 都不存在，这使得节点 5 成为叶节点。

我想将树的所有分支（根到叶）作为列表获取，但问题是列表长度根据分支而变化。

我如何制作一个接受这本字典并给出列表的函数？

Answer 1

这是一个使用您的数据结构并生成每个叶节点路径的示例。为了让它变得有趣，我选择让路径包含节点的名称。路径可以很容易地是节点号。我不确定为什么子节点会有一个数字但不存在，所以我的示例假设如果子节点条目是 non-zero，则该节点存在：

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']]

Answer 2

这是一个使用您的数据结构并生成每个叶节点路径的示例。为了让它变得有趣，我选择让路径包含节点的名称。路径可以很容易地是节点号。我不确定为什么子节点会有一个数字但不存在，所以我的示例假设如果子节点条目是 non-zero，则该节点存在：

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']]

Answer 3

您可以对生成器使用递归：

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')]

获取二叉树的所有分支（根到叶）作为 Python 中的列表

Get all branches(root to leaf) of a binary tree as lists in Python

python

binary-tree

traversal