從文本文件中查找Python樹的深度

Question

我對python比較陌生，在遇到這個問題時我試着解決了一些問題。一棵樹在以下方式使用文本文件中定義的，

d: 
e: 
b: d e 
c: 
a: b c 

所以，我想寫發現的這種深度的簡單python腳本。我無法找出解決這個問題的策略。有沒有任何算法或技術？

Answer 1

我的策略會是如下：

1. 查找無子女元素。
2. 對於每個這些，找到父。確定是否有任何元素將此父項作爲子項 - 如果不是，則您的長度爲兩（2）。
3. 如果是這樣，找到父級的父級。重複步驟2，增加你的長度計數器。繼續每一步更新計數器的過程。

對於您的情況：

d -> b -> a (len 3) 
e -> b -> a (len 3) 
c -> a (len 2) 

這可以被描述爲 '自下而上' 的樹構建方法/算法。

Answer 2

你給樹格式有一個很好的特性：如果x是y孩子，然後x在文件中y前給出。所以你可以簡單地遍歷文件一次，並將深度讀入字典。例如：

depth = {} 
for line in f: 
    parent, children = read_node(line) 
    if children: 
     depth[parent] = max(depth.get(child,1) for child in children) + 1 

然後，只需print depth['a']，作爲a是根。這裏read_node是一個快速的函數從行的文件的解析家長和孩子：

def read_node(line): 
    parent, children = line.split(":") 
    return parent, children.split() 

Answer 3

我不知道你所說的深度的意思，如果它是你有多少步去拜訪每一個節點，您可以使用Depth-First Search來查看訪問圖中每個節點需要多長時間。

這裏有一個簡單的實現：

text_tree = """d: 
e: 
b: d e 
c: 
a: b c""" 

tree = {} 

for line in text_tree.splitlines(): 
    node, childs = line.split(":") 
    tree[node] = set(childs.split()) 

def dfs(graph, start): 
    visited, stack = [], [start] 
    while stack: 
     vertex = stack.pop() 
     if vertex not in visited: 
      visited.append(vertex) 
      stack.extend(graph[vertex]) 
    return visited 

result = dfs(tree,"a")  
print "It took %d steps, to visit every node in tree, the path took was %s"%(len(result),result) 

，輸出：

It took 5 steps, to visit every node in tree, the path took was ['a', 'b', 'd', 'e', 'c']