枚举树中的所有路径 [英] Enumerating all paths in a tree
本文介绍了枚举树中的所有路径的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
我想知道如何最好地实现树数据结构,以便能够枚举所有级别的路径.让我用下面的例子来解释它:
I was wondering how to best implement a tree data structure to be able to enumerate paths of all levels. Let me explain it with the following example:
A
/
B C
| /
D E F
我希望能够生成以下内容:
I want to be able to generate the following:
A
B
C
D
E
F
A-B
A-C
B-D
C-E
C-F
A-B-D
A-C-E
A-C-F
截至目前,我正在对使用字典构建的数据结构执行不同深度的深度优先搜索,并记录看到的唯一节点,但我想知道是否有更好的方法来执行这种搜索遍历.有什么建议吗?
As of now, I am executing a depth-first-search for different depths on a data structure built using a dictionary and recording unique nodes that are seen but I was wondering if there is a better way to do this kind of a traversal. Any suggestions?
推荐答案
每当你在树上发现问题时,就使用递归 :D
Whenever you find a problem on trees, just use recursion :D
def paths(tree):
#Helper function
#receives a tree and
#returns all paths that have this node as root and all other paths
if tree is the empty tree:
return ([], [])
else: #tree is a node
root = tree.value
rooted_paths = [[root]]
unrooted_paths = []
for subtree in tree.children:
(useable, unueseable) = paths(subtree)
for path in useable:
unrooted_paths.append(path)
rooted_paths.append([root]+path)
for path in unuseable:
unrooted_paths.append(path)
return (rooted_paths, unrooted_paths)
def the_function_you_use_in_the_end(tree):
a,b = paths(tree)
return a+b
这篇关于枚举树中的所有路径的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文