目錄

1. 樹形結(jié)構(gòu)可視化

2. 樹形結(jié)構(gòu)轉(zhuǎn)為鏈表

此目標(biāo)是要還原樹形結(jié)構(gòu)的所有路徑。樹形結(jié)構(gòu)是一種常見的數(shù)據(jù)結(jié)構(gòu)，它表示元素之間層次關(guān)系。在樹形結(jié)構(gòu)中，每個(gè)節(jié)點(diǎn)可能擁有一個(gè)或多個(gè)子節(jié)點(diǎn)，形成了一個(gè)分層的結(jié)構(gòu)。為了還原樹形結(jié)構(gòu)的路徑，我們需要找到從根節(jié)點(diǎn)到每個(gè)葉節(jié)點(diǎn)的所有可能路徑。這可以通過深度優(yōu)先搜索或廣度優(yōu)先搜索來實(shí)現(xiàn)。通過遍歷樹形結(jié)構(gòu)，我們可以收集所有路徑，從而完整地還原出整個(gè)樹形結(jié)構(gòu)。這些路徑可以用于各種應(yīng)用，例如路徑規(guī)劃、圖形可視化等。因此，還原樹形結(jié)構(gòu)的所有路徑是一項(xiàng)重要任務(wù)。

1. 樹形結(jié)構(gòu)可視化

import networkx as nx  # pip install networkx
import matplotlib.pyplot as plt

# 構(gòu)造樹結(jié)構(gòu)
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)

# 可視化樹結(jié)構(gòu)
pos = nx.spring_layout(tree)
nx.draw(tree, pos, with_labels=True, node_size=50, font_size=10)
plt.show()

結(jié)果為：

2. 樹形結(jié)構(gòu)轉(zhuǎn)為鏈表

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__":
    # 定義樹型轉(zhuǎn)移序列
    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?函數(shù)是一個(gè)遞歸函數(shù)，它不斷地調(diào)用自己來處理子節(jié)點(diǎn)。對(duì)于每個(gè)節(jié)點(diǎn)，函數(shù)會(huì)檢查它是否存在于?nodes?字典中。如果不存在，說明該節(jié)點(diǎn)是葉節(jié)點(diǎn)，函數(shù)返回一個(gè)只包含該節(jié)點(diǎn)的列表。如果存在，函數(shù)會(huì)遍歷該節(jié)點(diǎn)的所有子節(jié)點(diǎn)，并對(duì)每個(gè)子節(jié)點(diǎn)調(diào)用?tree_to_linked_lists?函數(shù)。函數(shù)返回的列表是所有路徑的列表，每個(gè)路徑都是從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的節(jié)點(diǎn)列表。?文章來源地址http://www.zghlxwxcb.cn/news/detail-737472.html

到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】樹形結(jié)構(gòu)所有路徑復(fù)原為鏈表的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！