Получение итератора для обхода бинарного дерева в глубину
Я хочу выполнить первый обход двоичного дерева в глубину с использованием цикла for и выполнять вычисления на каждом этапе.
Допустим, у вас есть дерево из 4 уровней:
root
/ \
/ \
/ \
xx xx
/ \ / \
/ \ / \
xx xx xx xx
/ \ / \ / \ / \
x x x x x x x x
Если вы поместите «шаги исследования дерева в глубину» в список, это будет выглядеть так:
[
[1],
[1,1],
[1,1,1],
[1,1,0],
[1,0],
[1,0,1],
[1,0,0],
[0],
[0,1],
[0,1,0],
[0,1,1],
[0,0],
[0,0,1]
[0,0,0]
]
Есть ли функция, которая с учетом уровней двоичного дерева возвращает «шаги исследования дерева» в списке?
Я сначала использовал библиотеку itertools.permutation, но она не дает вам правильного порядка.
Я также пытался использовать:
l = [False, True]
list(itertools.product(l, repeat=3))
Близко, но не учитывает, что я иду вверх и вниз по уровням дерева.
@itprorh66, например: [1,1,0] указывает слева на первом уровне, слева на втором и справа на третьем.
Ответы 1
Предполагая, что ваше двоичное дерево является бинарным деревом идеально, вы можете использовать эту функцию:
def traverse(height, left=1, right=0):
path = []
while True:
if len(path) < height:
path.append(left)
else:
while path[-1] == right:
path.pop()
if not path:
return
path[-1] = right
yield path
Затем вызовите его следующим образом для дерева высотой 3:
for path in traverse(3):
print(path)
пожалуйста, объясните содержание вашего «древовидного списка исследований». Я понимаю, что 1 = посещено, а 0 означает не посещено, но как позиции связаны с обходом?