Python中的递归顺序二叉树遍历-Nonetype错误 [英] Recursive Pre-order Binary Tree Traversal in Python - Nonetype Error
问题描述
我的代码中的辅助方法存在问题.我提供了正确和不正确的方法来解决问题，但是我看不到两者之间的区别.
I am having issues with a helper method in my code. I providing both correct and incorrect approaches to the problem but I fail to see the difference between the two.
我的方法:
def preorder_print(self, start, traversal):
if start == None:
return traversal
else:
traversal += str(start.value)
traversal = self.preorder_print(start.left,traversal)
traversal = self.preorder_print(start.right,traversal)
注意: start 是根节点，遍历是一个空字符串
Note : start is the root node and traversal is an empty string
这会给出 TypeError:+ =:'NoneType'和'str '
正确的方法:
def preorder_print(self, start, traversal):
if start:
traversal += str(start.value)
traversal = self.preorder_print(start.left, traversal)
traversal = self.preorder_print(start.right, traversal)
return traversal
我无法理解这两种方法之间的区别.有人可以解释这两种方法在执行方式上有何不同.
I am unable to understand the difference between these two approaches. Can someone explain how the two approaches differ in execution.
推荐答案
在此答案中，我们将前置遍历逻辑与计算/效果分开.从 node 类-
In this answer, we separate preorder traversal logic from the the computation/effect. Starting with a node class -
class node:
def __init__(self, data, left = None, right = None):
self.data = data
self.left = left
self.right = right
这是 tree 类-
class tree:
def __init__(self, root = None):
self.root = root
@property
def is_empty(self):
return self.root is None
@property
def data(self):
return self.root.data
@property
def left(self):
return self.root.left
@property
def right(self):
return self.root.right
def preorder(self):
if not self.is_empty:
yield self.data
yield from tree(self.left).preorder()
yield from tree(self.right).preorder()
让我们创建一个根 node -
root = node \
( 1
, node(2, node(3), node(4))
, node(5, node(6), node(7))
)
哪个代表这棵树-
1
/ \
/ \
2 5
/ \ / \
3 4 6 7
现在我们可以打印整棵树-
for val in tree(root).preorder():
print(val)
# 1
# 2
# 3
# 4
# 5
# 6
# 7
将树的遍历与对树的值进行的计算分开是很重要的.例如，我们可以轻松地 sum 值-
It's important to keep traversal of our tree separate from the computations we make on the tree's values. For example, we can easily sum the values -
print(sum(tree(root).preorder()))
# 28
或者我们可以在有序的列表-
Or we can collect all of the values in an ordered list -
print(list(tree(root).preorder()))
# [1, 2, 3, 4, 5, 6, 7]
如果 print 是 preorder 的一部分，则必须为要实现的所有其他树操作重复执行preorder遍历逻辑.
If print is a part of preorder, you'll have to duplicate the preorder traversal logic for every other tree operation you wish to implement.
最佳做法
您可能应该防止访问空节点上的属性-
You should probably safeguard against accessing properties on an empty node -
class tree:
# ...
@property
def data(self):
if self.is_empty:
raise Exception("cannot get data of an empty tree")
else:
return self.root.data
@property
def left(self):
if self.is_empty:
raise Exception("cannot get left of an empty tree")
else:
return self.root.left
@property
def right(self):
if self.is_empty:
raise Exception("cannot get right of an empty tree")
else:
return self.root.right
其他遍历
现在假设您想以其他方式遍历树，例如 inorder 或 postorder .混合诸如 print 或 + 之类的计算/效果意味着您甚至会有更多个重复项.我们一定会避免这种情况-
Now imagine you want to traverse your tree in other ways, such as inorder or postorder. Mixing computations/effects like print or + means you will have even more duplication. We'll definitely want to avoid that -
class tree:
# ...
def inorder(self):
if not self.is_empty:
yield from tree(self.left).inorder()
yield self.data
yield from tree(self.right).inorder()
def postorder(self):
if not self.is_empty:
yield from tree(self.left).postorder()
yield from tree(self.right).postorder()
yield self.data
作为参考，这又是我们的树-
For reference, here's our tree again -
1
/ \
/ \
2 5
/ \ / \
3 4 6 7
这是工作中的 inorder 遍历-
print(list(tree(root).inorder()))
# [3, 2, 4, 1, 6, 5, 7]
print(sum(tree(root).inorder()))
# 28
和 postorder -
print(list(tree(root).postorder()))
# [3, 4, 2, 6, 7, 5, 1]
print(sum(tree(root).postorder()))
# 28
这篇关于Python中的递归顺序二叉树遍历-Nonetype错误的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
