使用Python实现森林数据结构

2023-04-11 00:00:00 python 数据结构 森林

森林数据结构是由许多树组成的数据结构，每个树都可以看作一个森林。它可以用 Python 的列表和字典来实现。

我们可以用字典来表示森林中的每一棵树，键为树的根节点，值为树中每个节点的子节点。例如，对于以下的树：

    1
   / \
  2   3
 / \
4   5

可以用字典表示为：

{
 1: [2, 3],
 2: [4, 5],
 3: [],
 4: [],
 5: []
}

其中，键值对中的键表示该节点的值，值表示该节点的子节点。在这个例子中，节点 1 有两个子节点 2 和 3，节点 2 有两个子节点 4 和 5，节点 3 没有子节点。节点 4 和 5 同样没有子节点。

创建一个空的森林可以使用空的列表：

forest = []

要向森林中添加一棵树，可以用以下代码：

tree = {
    root_node: child_nodes
}
forest.append(tree)

其中，root_node 为这棵树的根节点，child_nodes 为子节点列表。

下面是一个完整的例子，演示如何构建一个包含两棵树的森林，并输出森林中每棵树的节点：

tree1 = {
    1: [2, 3],
    2: [4, 5],
    3: [],
    4: [],
    5: []
}

tree2 = {
    "pidancode.com": ["Python", "Java"],
    "Python": ["Numpy", "Pandas"],
    "Numpy": [],
    "Pandas": [],
    "Java": ["Spring", "Hibernate"],
    "Spring": [],
    "Hibernate": []
}

forest = [tree1, tree2]

# 遍历每一棵树
for tree in forest:
    # 获取树的所有节点
    nodes = list(tree.keys())
    # 输出每个节点
    print("Tree nodes:", nodes)

输出结果为：

Tree nodes: [1, 2, 3, 4, 5]
Tree nodes: ['pidancode.com', 'Python', 'Java', 'Numpy', 'Pandas', 'Spring', 'Hibernate']

相关文章