Извините, если это общий вопрос, но я не нашел подходящего ответа для своей конкретной проблемы. Я пытаюсь реализовать метод walk, который перемещает двоичное дерево от его корневого узла к каждому из его конечных узлов, получая путь от корня к листу всякий раз, когда я добираюсь до конечного узла. Например, ходьба по двоичному дереву, представленному как:
__a__
/ \
b d
/ \ / \
- c - -
даст:
['a', 'b', 'c']
['a', 'd']
Моя идея состоит в том, что BinaryTree.walk вызывает Node.traverse для корневого узла, который, в свою очередь, вызывает рекурсивно метод traverse каждого дочернего узла. BinaryTree.walk также создает пустой список, который передается при каждом вызове traverse, добавляя данные каждого узла, получая список после достижения конечного узла и выталкивая каждый элемент из списка после посещения каждого узла.
В какой-то момент что-то идет не так, хотя. Это мой код:
class Node:
def __init__(self, data=None, left=None, right=None):
self.data = data
self.left = left
self.right = right
def __repr__(self):
return f"{self.__class__.__name__}({self.data})"
@property
def children(self):
return self.left, self.right
def traverse(self, branch):
print('ON NODE:', self)
branch.append(self.data)
if self.left is None and self.right is None:
yield branch
else:
for child in self.children:
if child is not None:
print('ENTERING CHILD:', child)
child.traverse(branch=branch)
print('EXITING CHILD:', child)
branch.pop()
class BinaryTree:
def __init__(self, root=Node()):
if not isinstance(root, Node):
raise ValueError(f"Tree root must be Node, not {type(root)}")
self.root = root
def __repr__(self):
return f"{self.__class__.__name__}({self.root})"
def walk(self):
node = self.root
branch = []
yield from node.traverse(branch=branch)
if __name__ == '__main__':
# create root node
n0 = Node('A')
# create binary tree with root node
tree = BinaryTree(root=n0)
# create others nodes
n1 = Node(data='B')
n2 = Node(data='C')
n3 = Node(data='D')
# connect nodes
n0.left = n1
n0.right = n3
n1.right = n2
# walk tree and yield branches
for branch in tree.walk():
print(branch)
Ожидаемый результат:
ON NODE: Node(A)
ENTERING CHILD: Node(B)
ON NODE: Node(B)
ENTERING CHILD: Node(C)
ON NODE: Node(C)
['A', 'B', 'C'] # yielded branch
EXITING CHILD: Node(C)
EXITING CHILD: Node(B)
ENTERING CHILD: Node(D)
ON NODE: Node(D)
['A', 'D'] # yielded branch
EXITING CHILD: Node(D)
Фактическая выработка:
ON NODE: Node(A)
ENTERING CHILD: Node(B)
EXITING CHILD: Node(B)
ENTERING CHILD: Node(D)
EXITING CHILD: Node(D)
IndexError: pop from empty list
Я понимаю, что делаю что-то не так со списком, так как он пытается выскочить, когда он пуст, но я не могу понять, как он дошел до этого. Он должен вызывать pop один раз для каждого append вызова.
Также я не могу понять, почему узлы вводятся и выходят, но сообщение ON NODE: не печатается ... Как будто мой код просто как-то пропускает строку child.traverse(branch=branch)?
Может кто-нибудь помочь мне понять, где я все испортил?
Заранее спасибо за помощь!