我正在处理一个与树遍历方法相关的新问题。我有一个带有条件搜索选项的二叉树。
我想根据这个解析的字符串解析字符串类型的输入并遍历树。条件是
有点复杂,让我用一个例子来解释它:
输入 :
data = [
'dummy',
['null', 'd2', 'd1'],
['null', 'b2', 'b1'],
'dummy',
['b2', 'a2', 'a1'],
['b1', 'c1', 'c2'],
'dummy',
'dummy',
'dummy',
'dummy',
['c1', 'a1', 'a2'],
['c2', 'a2', 'a1']
]
输出应该是:d2,b2,a2
d2,b2,a1
d1,b2,a2
d1,b2,a1
d2,b1,c1,a1
d2,b1,c1,a2
d1,b1,c1,a1
d1,b1,c1,a2
d2,b1,c2,a2
d2,b1,c2,a1
d1,b1,c2,a2
d1,b1,c2,a1
这就是树的图片:这些是我只显示第一行输出的代码:
solution, solutions = [], []
for d in data:
x = d[0] * 2
child = []
for i in data:
if i[0] == x:
child.append(i[0])
if i[0] == x + 1:
child.append(i[0])
d.insert(1, child)
root = data[1]
solution.append(root[3])
i = 0
pointer = data[root[0] * 2]
last = None
while i <= len(data):
if solution[-1:] != [last]:
solution.append(pointer[3])
try:
pointer = data[pointer[0] * 2]
except:
break
if len(pointer) > 3:
if pointer[2] == 'null' or pointer[2] == solution[-1:]:
solution.append(pointer[3])
else:
solutions.append(solution)
solution = []
pointer = data[int((pointer[0] / 2) + 1)]
last = pointer[3]
i += 1
print(solutions)
这是输出:[['d2', 'b2', 'a2']]
更多细节:这棵树是词典偏好树,我用数组实现它。我想树的每个节点可能有 2 个或更少的 child ,并且每个边可能有条件或没有条件。
现在,我想找到树的解决方案。为了找到解决方案,我必须遍历树
我用例子解释树和数组的参数:
最佳答案
我认为以下实现应该这样做。它为示例 data
生成输出你提供了。我相信该数据结构存在一些冗余,因此我也在代码中添加了一些验证,如果它违反了该验证,则会引发错误。
def getpaths(data, i, tracks):
paths = []
isleaf = True
j = 2*i
for k in range(1, 3):
if j < len(data) and data[j] != 'dummy':
isleaf = False
if data[j][0] == 'null':
yield from getpaths(data, j, [track + [data[i][m]] for track in tracks for m in range(1,3)])
break
elif data[j][0] != data[i][k]:
raise ValueError("inconsistent tree")
else:
yield from getpaths(data, j, [track + [data[i][k]] for track in tracks])
j += 1
if isleaf:
for track in tracks:
yield track + [data[i][1]]
yield track + [data[i][2]]
# Example run
data = [
'dummy',
['null', 'd2', 'd1'],
['null', 'b2', 'b1'],
'dummy',
['b2', 'a2', 'a1'],
['b1', 'c1', 'c2'],
'dummy',
'dummy',
'dummy',
'dummy',
['c1', 'a1', 'a2'],
['c2', 'a2', 'a1']
]
for path in getpaths(data, 1, [[]]):
print(path)
关于python - 用python遍历树的解决方案,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/62611966/