【数据结构】树形结构所有路径复原为链表

目录

1. 树形结构可视化

2. 树形结构转为链表

此目标是要还原树形结构的所有路径。树形结构是一种常见的数据结构，它表示元素之间层次关系。在树形结构中，每个节点可能拥有一个或多个子节点，形成了一个分层的结构。为了还原树形结构的路径，我们需要找到从根节点到每个叶节点的所有可能路径。这可以通过深度优先搜索或广度优先搜索来实现。通过遍历树形结构，我们可以收集所有路径，从而完整地还原出整个树形结构。这些路径可以用于各种应用，例如路径规划、图形可视化等。因此，还原树形结构的所有路径是一项重要任务。

1. 树形结构可视化

import networkx as nx  # pip install networkx
import matplotlib.pyplot as plt# 构造树结构
tree = nx.Graph()# 单条边添加
# tree.add_edge('1', '2')
# tree.add_edge('1', '3')
# tree.add_edge('2', '4')
# tree.add_edge('3', '5')
# tree.add_edge('5', '6')
# tree.add_edge('5', '7')# 批量边添加
lst = [(1, 2), (2, 3), (3, 4), (3, 5), (3, 6), (4, 7), (5, 8), (6, 9), (7, 10), (8, 11), (9, 12), (10, 13), (11, 13), (12, 13), (13, 14)]
tree.add_edges_from(lst)# 可视化树结构
pos = nx.spring_layout(tree)
nx.draw(tree, pos, with_labels=True, node_size=50, font_size=10)
plt.show()

结果为：

2. 树形结构转为链表

from collections import defaultdict
from pprint import pprintdef tree_to_linked_lists(node, nodes):if node not in nodes:return [[node]]linked_lists = []for child in nodes[node]:linked_lists.extend(tree_to_linked_lists(child, nodes))return [[node] + sub_list for sub_list in linked_lists]def get_different_endings_sequence(root, transitions):nodes = defaultdict(list)for transition in transitions:parent, child = transitionnodes[parent].append(child)print(nodes)linked_lists = tree_to_linked_lists(root, nodes)return linked_listsif __name__ == "__main__":# 定义树型转移序列root = 1transitions = [(1, 2), (2, 3), (3, 4), (3, 5), (3, 6), (4, 7), (5, 8), (6, 9), (7, 10), (8, 11), (9, 12), (10, 13), (11, 13), (12, 13), (13, 14)]result = get_different_endings_sequence(root, transitions)pprint(result)"""defaultdict(<class 'list'>, {1: [2], 2: [3], 3: [4, 5, 6], 4: [7], 5: [8], 6: [9], 7: [10], 8: [11], 9: [12], 10: [13], 11: [13], 12: [13], 13: [14]})[[1, 2, 3, 4, 7, 10, 13, 14],[1, 2, 3, 5, 8, 11, 13, 14],[1, 2, 3, 6, 9, 12, 13, 14]]"""

代码中的 tree_to_linked_lists 函数是一个递归函数，它不断地调用自己来处理子节点。对于每个节点，函数会检查它是否存在于 nodes 字典中。如果不存在，说明该节点是叶节点，函数返回一个只包含该节点的列表。如果存在，函数会遍历该节点的所有子节点，并对每个子节点调用 tree_to_linked_lists 函数。函数返回的列表是所有路径的列表，每个路径都是从根节点到叶节点的节点列表。