Python:二叉树遍历迭代器不使用条件
问题描述:
我想在python中创建一个模块,使用4标准树遍历(inorder,preorder,postorder和levelorder)遍历二叉树而不使用条件并只使用多态方法分派或迭代器。下面的例子应该工作。Python:二叉树遍历迭代器不使用条件
for e in t.preorder():
print(e)
for e in t.postorder():
print(e)
for e in t.inorder():
print(e)
for e in t.levelorder():
print(e)
到目前为止,我想出了以下
def build_tree(preord, inord):
tree = BinaryTree()
tree.root = buildTreeHelper(preord, inord)
return tree
def buildTreeHelper(preorder, inorder):
if len(inorder) == 0:
return None
elem = preorder[0]
elemInorderIndex = inorder.find(elem)
if elemInorderIndex > -1:
leftPreorder = preorder[1:elemInorderIndex + 1]
rightPreorder = preorder[elemInorderIndex + 1:]
leftInorder = inorder[0:elemInorderIndex]
rightInorder = inorder[elemInorderIndex + 1:]
left = buildTreeHelper(leftPreorder, leftInorder)
right = buildTreeHelper(rightPreorder, rightInorder)
return BinaryTreeNode(elem, left, right)
else:
return "No valid tree for the given args"
class BinaryTree:
def __init__(self):
self.root = None
def preorder(self):
return self.root.preorder()
def inorder(self):
return self.root.inorder()
def postoder(self):
return self.root.postorder()
class BinaryTreeNode:
def __init__(self, element, left=None, right=None):
self.element = element
self.left = left
self.right = right
def preorder(self):
yield self.element
for e in self.left.preorder():
yield e
for e in self.right.preorder():
yield e
def inorder(self):
for e in self.left.inorder():
yield e
yield self.element
for e in self.right.inorder():
yield e
def postorder(self):
for e in self.left.postorder():
yield e
for e in self.right.postorder():
yield e
yield self.element
if __name__ == "__main__":
t = build_tree("BAC", "ABC")
for e in t.inorder():
print(e)
当我尝试运行迭代的一个类似的代码的底部,我得到一个 AttributeError的:“NoneType”对象没有属性'inorder' 错误消息。我认为这是因为我从来没有提出StopIteration。关于如何解决这个问题并开始实施Levelorder的任何想法?
答
你说你想使用多态,但实际上你并没有这样做。将代码中所有出现的“无”替换为支持您的方法的特殊对象,但返回一个空序列,它将全部工作。
在发布Python问题时,您还应该更加注意缩进。您发布的代码不会按原样运行。
def build_tree(preord, inord):
tree = BinaryTree()
tree.root = buildTreeHelper(preord, inord)
return tree
def buildTreeHelper(preorder, inorder):
if len(inorder) == 0:
return empty
elem = preorder[0]
elemInorderIndex = inorder.find(elem)
if elemInorderIndex > -1:
leftPreorder = preorder[1:elemInorderIndex + 1]
rightPreorder = preorder[elemInorderIndex + 1:]
leftInorder = inorder[0:elemInorderIndex]
rightInorder = inorder[elemInorderIndex + 1:]
left = buildTreeHelper(leftPreorder, leftInorder)
right = buildTreeHelper(rightPreorder, rightInorder)
return BinaryTreeNode(elem, left, right)
else:
return "No valid tree for the given args"
class BinaryTree:
def __init__(self):
self.root = empty
def preorder(self):
return self.root.preorder()
def inorder(self):
return self.root.inorder()
def postorder(self):
return self.root.postorder()
class EmptyNode:
def preorder(self):
return()
inorder = postorder = preorder
empty = EmptyNode()
class BinaryTreeNode:
def __init__(self, element, left=empty, right=empty):
self.element = element
self.left = left
self.right = right
def preorder(self):
yield self.element
for e in self.left.preorder():
yield e
for e in self.right.preorder():
yield e
def inorder(self):
for e in self.left.inorder():
yield e
yield self.element
for e in self.right.inorder():
yield e
def postorder(self):
for e in self.left.postorder():
yield e
for e in self.right.postorder():
yield e
yield self.element
if __name__ == "__main__":
t = build_tree("BAC", "ABC")
for e in t.inorder():
print(e)
不能没有停止条件递归。您可能无法在代码中明确指定一个,但它仍然存在。为什么麻烦? – 2010-09-22 07:22:31