抱歉,这是一个常见问题,但是我没有针对我的特定问题找到合适的答案.我正在尝试实现一种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
我知道我对列表做错了,因为它在空时尝试弹出,但是我不明白它是怎么做到的.它应该为每个追加调用调用一次pop.
我也无法弄清楚为什么要输入和退出节点,但是没有显示ON NODE：消息…就像我的代码以某种方式跳过child.traverse(branch = branch)行一样？
谁能帮助我了解我在哪里搞砸了？
在此先感谢您的帮助！
code.py：
#!/usr/bin/env python3
import sys
class Node:
def __init__(self,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(即使为空)
输出：
06001
您的代码有什么问题？
这是遍历重复调用(child.traverse(branch = branch)).它创建了一个生成器,但是由于没有在任何地方使用(迭代)该生成器,因此该函数实际上并未调用自身,从而导致尝试删除的元素多于添加的元素(只有1：这是根节点).因此,事实证明您已经快到了.您所要做的就是在其前面添加一个产量:).有关[Python]: PEP 380 — Syntax for Delegating to a Subgenerator的更多详细信息.