很抱歉，如果这是一个常见的问题，但我还没有找到一个适合我的问题的答案。我正在尝试实现一个walk方法，该方法将二叉树从其根节点遍历到其每个叶节点，每当我到达叶节点时都会生成根到叶路径。例如，遍历由以下项表示的二叉树：
__a__
/ \
b d
/ \ / \
- c - -
会产生：
['a', 'b', 'c']
['a', 'd']
我的想法是
BinaryTree.walk在根节点上调用Node.traverse，而根节点又递归地调用每个子节点的traverse方法。BinaryTree.walk还创建一个空列表，该列表随每个调用一起传递，附加每个节点的数据，到达叶节点时生成该列表，并在访问每个节点后弹出列表中的每个元素。但在某个时候，有些事情出了问题。这是我的代码：
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
我知道我做了一些错误的事情，因为它试图弹出时，它是空的，但我不明白它是怎么做到的。它应该为每个
traverse调用调用pop一次。我也不知道为什么节点被输入和退出，但是
append消息没有被打印出来…好像我的代码不知怎么跳过了ON NODE:行？有谁能帮我弄明白我把事情搞砸了吗？
提前谢谢你的帮助！
最佳答案
这里有一个修改过的代码变体。
代码.py：
#!/usr/bin/env python3
import sys
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):
if self.left:
yield self.left
if self.right:
yield self.right
@property
def is_leaf(self):
return self.left is None and self.right is None
def traverse_preord(self, accumulator=list()):
print(" On node:", self)
accumulator.append(self.data)
if self.is_leaf:
yield accumulator
else:
for child in self.children:
print(" Entering child:", child)
yield from child.traverse_preord(accumulator=accumulator)
accumulator.pop()
print(" Exiting child:", child)
def main():
root = Node(data="A",
left=Node(data="B",
right=Node(data="C")
),
right=Node(data="D",
#left=Node(data="E"),
#right=Node(data="F"),
)
)
for path in root.traverse_preord():
print("Found path:", path)
if __name__ == "__main__":
print("Python {:s} on {:s}\n".format(sys.version, sys.platform))
main()
笔记：
我对代码进行了一些重构（简化、更改了一些标识符名称、文本和其他无关紧要的更改）
子属性：
对于节点的left或right属性，None表示该节点没有子节点，因此返回的结果中没有包含它的点
因为问题涉及到收益率，所以我把它变成了一个生成器（而不是返回元组或列表…）。因此，我不得不添加is leaf，因为生成器的计算结果不是False（即使是空的）
输出：
[cfati@CFATI-5510-0:e:\Work\Dev\StackOverflow\q055424449]> "e:\Work\Dev\VEnvs\py_064_03.07.03_test0\Scripts\python.exe" code.py
Python 3.7.3 (v3.7.3:ef4ec6ed12, Mar 25 2019, 22:22:05) [MSC v.1916 64 bit (AMD64)] on win32
On node: Node(A)
Entering child: Node(B)
On node: Node(B)
Entering child: Node(C)
On node: Node(C)
Found path: ['A', 'B', 'C']
Exiting child: Node(C)
Exiting child: Node(B)
Entering child: Node(D)
On node: Node(D)
Found path: ['A', 'D']
Exiting child: Node(D)
你的密码怎么了？
这是遍历循环调用（
child.traverse(branch=branch)）。它创建了一个生成器，但是由于它在任何地方都没有使用（迭代），因此函数实际上没有调用它自己，从而导致尝试删除比添加的元素更多的元素（只有1:这是根节点）。原来你就快到了。你所要做的，就是在它前面加一个yield from：）。有关[Python]: PEP 380 -- Syntax for Delegating to a Subgenerator的更多详细信息。