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

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

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 函数。函数返回的列表是所有路径的列表，每个路径都是从根节点到叶节点的节点列表。