枚举树中的所有路径
|
我想知道如何最好地实现树数据结构，以便能够枚举所有级别的路径。让我用以下示例进行说明：
A
/ \\
B C
| /\\
D E F
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
没有找到相关结果
已邀请:
3 个回复
扇献隙
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鞋扣蚊冈借
，其中是从根到节点的路径。假设路径“ 4”是节点“ 6”的数组，其中“ 7”是根，而“ 8”是当前节点。enumerate-paths(p) { for i = 0 .. n output p[n - i] .. p[n] as a path. }是长度为的路径列表。然后，您可以按路径的长度顺序输出路径，尽管这会占用O（n）的存储空间。钨蜡唤喉晤