Рекурсивный обход двоичного дерева предварительного заказа в 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 - это узел root, а обход - пустая строка

Это дает 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

В этом ответе мы отделяем логику обхода предзаказа c от вычисления / эффекта. Начиная с 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()

Давайте создадим root 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, вам нужно будет продублировать логику обхода предзаказа c для каждой другой древовидной операции, которую вы будете выполнять sh.

---

рекомендация

Возможно, вам следует защититься от доступа к свойствам на пустом узле -

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