在树中查找值的路径

Question

假设您要编写一个函数，该函数将一棵树和一个值 x 作为参数。该函数必须 return 从树的根到该值的所有路径，以列表的形式。如果有多个路径，那么函数 return 是一个列表列表。

这是我目前得到的结果

def path_finder(t,value):
    paths = []
    if label(t) == value:
       return [label(t)]
    for b in branches(t):
       path = path_finder(b, value)
       if path:
         paths.append([label(t)]+path)
    return paths

但是，给定树 t 和值 x = 5，这是我的输出

t = tree(1, [tree(2, [tree(3), tree(4, [tree(6)]), tree(5)]), tree(5)])

path_finder(t,5)

[[1,[2,5]],[1,5]]

好像是堆叠问题。

对调试有什么帮助吗？

注：label(t) --> root的值

Answer 1

不知道有没有你用的标准树class，所以我做了一个。

class tree():
    def __init__(self, val, sub=[]):
        self.val = val
        self.sub = sub # a list of trees

def label(t):
    return t.val
def branches(t):
    return t.sub

def path_finder(t, value):
    paths = []
    if label(t) == value:
        paths.append([value])
    for b in branches(t):
        paths += [[label(t)] + path for path in path_finder(b, value)]
    return paths

t = tree(1, [tree(2, [tree(3), tree(4, [tree(6)]), tree(5)]), tree(5)])
for x in range(7):
    print(x, path_finder(t, x))

主要修正在paths += [[label(t)] + path for path in path_finder(b, value)]行。另请注意，当 label(t) == value 时，我不会立即返回列表。在那一刻停止代码将不会找到每条路径，例如，当节点 5 在另一个节点 5.

输出：

# 0 [] # when path_finder cannot find the value
# 1 [[1]]
# 2 [[1, 2]]
# 3 [[1, 2, 3]]
# 4 [[1, 2, 4]]
# 5 [[1, 2, 5], [1, 5]]
# 6 [[1, 2, 4, 6]]

在树中查找值的路径

Finding paths to a value in a tree

python

binary-tree