Python中的递归预序二叉树遍历--非类型错误

Question

我的代码中有一个助手方法的问题。我提供了正确和不正确的方法来解决这个问题，但我看不出两者之间的区别。

我的方法：

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是根节点，遍历是空字符串

这给出了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

我无法理解这两种方法之间的区别。有人能解释一下这两种方法在执行上有何不同吗？

Answer 1

在这个答案中，我们将前置遍历逻辑与计算/效果分开。从node类开始-

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

现在我们可以print整棵树了-

for val in tree(root).preorder():
  print(val)

# 1
# 2
# 3
# 4
# 5
# 6
# 7

重要的是要将遍历树与我们对树的值进行的计算分开。例如，我们可以很容易地sum值-

print(sum(tree(root).preorder()))
# 28

或者我们可以在一个有序的list中收集所有值-

print(list(tree(root).preorder()))
# [1, 2, 3, 4, 5, 6, 7]

如果print是preorder的一部分，那么您必须为您希望实现的其他每个树操作复制序遍历逻辑。

最佳实践

您可能应该防止访问空节点上的属性-

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或+ )意味着您将有更多的复制。我们一定要避免-

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

作为参考，这又是我们的树-

      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