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

目录

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 pprint def 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 = transition nodes[parent].append(child) print(nodes) linked_lists = tree_to_linked_lists(root, nodes) return linked_lists if __name__ == "__main__": # 定义树型转移序列 root = 1 transitions = [(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 函数。函数返回的列表是所有路径的列表，每个路径都是从根节点到叶节点的节点列表。