Python: двоичные итераторы обхода дерева без использования условных выражений

Question

Я пытаюсь создать модуль в python для итерации по двоичному дереву, используя 4 стандартных обхода дерева (inorder, preorder, postorder и levelorder) без использования условных выражений и только с использованием полиморфного метода отправки или итераторов.Следующие примеры должны работать.

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)

Когда я пытаюсь запустить один из итераторов, как в нижней части кода, яget AttributeError: объект 'NoneType' не имеет атрибута 'inorder' сообщение об ошибке.Я думаю, это потому, что я никогда не поднимаю СтопИтацию.Любые идеи о том, как это исправить и начать реализацию levelorder?

Answer 1

Вы сказали, что хотите использовать полиморфизм, но на самом деле, похоже, вы этого не сделали.Замените все вхождения 'None' в вашем коде специальным объектом, который поддерживает ваши методы, но возвращает пустую последовательность, и все это будет работать.

Также вы должны больше заботиться об отступах при публикации вопросов 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)