列出通用(非二进制)列表列表树中叶子的所有路径
Listing all paths to leaves in generic (non-binary) list-of-list tree
我有一棵这样编码的树:
[A, [B, [G, [H], [I]]],
[D, [C], [E], [F]]]
这代表以下结构:
A
/ \
B D
/ /|\
G C E F
/ \
H I
此外,叶子都包含 'end' 而不是实际的字母,因此 H、I、C、E、F 实际上都是 'end'
另一种查看列表的方式可能更直观。在这种情况下,缩进代表树级别
[A,
[B,
[G,
[H],
[I]
]
],
[D,
[C],
[E],
[F]
]
]
我想遍历树并列出所有到叶子的路径
[A, B, G, H]
[A, B, G, I]
[A, D, C]
[A, D, E]
[A, D, F]
我编写了这个可以遍历树并正确识别叶子的函数,但我不确定如何像上面那样构建路径列表:
def leave_paths(lst, level=0):
#level is used to keep track how far in the tree we are to
#perform various functions - removed here for simplicity
if lst[0] == 'end':
#This is a leaf!
for i, l in enumerate(lst[1:]):
if type(l) is list:
leave_paths(l, level + 1)
据我所知,这是正确的,但我不确定如何跟踪路径,以便它们按照我描述的方式进行格式化。
通过递归,您应该确定您的基本案例,然后如何使用简单的单独步骤在该基本案例的基础上构建,以便制作更复杂的案例。
基本案例:
叶子是每条路径所独有的,这似乎是一个线索,表明您在构建路径时可以从叶子开始。将包含叶子的列表作为 return 值传回,这是您的基本情况。在只有一个节点的情况下,您最终只会在一个列表中得到一个值(只有一个路径)。
递归案例:您需要获得递归的结果(根据您的示例最多 2 个分支),然后将当前节点添加到每个子节点的结果中列表(除非当前节点下没有分支,否则可能超过 2 个)。 Return 前置后的结果。
编辑: 由于您要求的代码非常好,基本上您可以执行以下操作:
def leave_paths(current):
# Identify leaves by their length
if len(current) == 1:
return current
# Take all branches, get the paths for the branch, and prepend current
return [[current[0]] + path for branch in current[1:] for path in leave_paths(branch)]
这应该为您提供一个包含 "path" 个列表的列表。请注意我们如何通过遍历 branch
es 在每个递归步骤中重新展平,然后还遍历每个 branch
的结果 path
s,并将前置结果放入将 list
理解为我们的 return 值。
以下是针对两个用例的更实用的复制粘贴答案,基于(主要是机器渴望的答案):
创建一长串路径,例如['ABCDE']
def leave_paths(current):
# Identify leaves by their length
if len(current) == 1:
return current
# Take all branches, get the paths for the branch, and prepend
return [current[0] + path for branch in current[1:] for path in leave_paths(branch)]
如果您希望将路径作为列表,例如['A','B','C','D','E']
def leave_paths(current):
# Identify leaves by their length
if len(current) == 1:
return [current]
# Take all branches, get the paths for the branch, and prepend
return [[current[0]] + path for branch in current[1:] for path in leave_paths(branch)]
我有一棵这样编码的树:
[A, [B, [G, [H], [I]]],
[D, [C], [E], [F]]]
这代表以下结构:
A
/ \
B D
/ /|\
G C E F
/ \
H I
此外,叶子都包含 'end' 而不是实际的字母,因此 H、I、C、E、F 实际上都是 'end'
另一种查看列表的方式可能更直观。在这种情况下,缩进代表树级别
[A,
[B,
[G,
[H],
[I]
]
],
[D,
[C],
[E],
[F]
]
]
我想遍历树并列出所有到叶子的路径
[A, B, G, H]
[A, B, G, I]
[A, D, C]
[A, D, E]
[A, D, F]
我编写了这个可以遍历树并正确识别叶子的函数,但我不确定如何像上面那样构建路径列表:
def leave_paths(lst, level=0):
#level is used to keep track how far in the tree we are to
#perform various functions - removed here for simplicity
if lst[0] == 'end':
#This is a leaf!
for i, l in enumerate(lst[1:]):
if type(l) is list:
leave_paths(l, level + 1)
据我所知,这是正确的,但我不确定如何跟踪路径,以便它们按照我描述的方式进行格式化。
通过递归,您应该确定您的基本案例,然后如何使用简单的单独步骤在该基本案例的基础上构建,以便制作更复杂的案例。
基本案例: 叶子是每条路径所独有的,这似乎是一个线索,表明您在构建路径时可以从叶子开始。将包含叶子的列表作为 return 值传回,这是您的基本情况。在只有一个节点的情况下,您最终只会在一个列表中得到一个值(只有一个路径)。
递归案例:您需要获得递归的结果(根据您的示例最多 2 个分支),然后将当前节点添加到每个子节点的结果中列表(除非当前节点下没有分支,否则可能超过 2 个)。 Return 前置后的结果。
编辑: 由于您要求的代码非常好,基本上您可以执行以下操作:
def leave_paths(current):
# Identify leaves by their length
if len(current) == 1:
return current
# Take all branches, get the paths for the branch, and prepend current
return [[current[0]] + path for branch in current[1:] for path in leave_paths(branch)]
这应该为您提供一个包含 "path" 个列表的列表。请注意我们如何通过遍历 branch
es 在每个递归步骤中重新展平,然后还遍历每个 branch
的结果 path
s,并将前置结果放入将 list
理解为我们的 return 值。
以下是针对两个用例的更实用的复制粘贴答案,基于(主要是机器渴望的答案):
创建一长串路径,例如['ABCDE']
def leave_paths(current):
# Identify leaves by their length
if len(current) == 1:
return current
# Take all branches, get the paths for the branch, and prepend
return [current[0] + path for branch in current[1:] for path in leave_paths(branch)]
如果您希望将路径作为列表,例如['A','B','C','D','E']
def leave_paths(current):
# Identify leaves by their length
if len(current) == 1:
return [current]
# Take all branches, get the paths for the branch, and prepend
return [[current[0]] + path for branch in current[1:] for path in leave_paths(branch)]