抱歉，如果这是一个常见问题，但我还没有找到适合我的特定问题的答案。我正在尝试实施一个walk方法将二叉树从根节点遍历到每个叶节点，每当到达叶节点时都会生成根到叶路径。例如，遍历表示为的二叉树：
__a__
/ \
b d
/ \ / \
- c - -
会产生：
['a', 'b', 'c']
['a', 'd']
我的想法是BinaryTree.walk calls 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 call.
我也无法弄清楚为什么要进入和退出节点，但是ON NODE:消息没有被打印...就像我的代码只是跳过了child.traverse(branch=branch)以某种方式线？
谁能帮我理解我哪里搞砸了？
在此先感谢您的帮助！
