时间戳

首页 > 解决方案 > python遍历树的解决方案

python - python遍历树的解决方案

问题描述

我正在处理一个与树遍历方法相关的新问题。我有一个带有条件搜索选项的二叉树。我想解析一个字符串类型的输入并基于这个解析的字符串遍历树。条件有点复杂，所以让我用一个例子来解释一下：

输入 ：

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

这就是树的图片：

1

这些是我的代码，只显示第一个输出行：

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 个或更少的孩子，每条边可能有条件或没有条件。

现在，我想找到树的解决方案。为了找到解决方案，我必须遍历树

我用例子解释树和数组的参数：

2

标签： pythonalgorithmtreebinary-treetree-traversal

解决方案

我认为以下实现应该做到这一点。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)

推荐阅读