Сбой рекурсивной функции при обходе inorder в дереве ds

Question

Я пытаюсь реализовать древовидную структуру данных, но у меня возникли проблемы с пониманием того, как создать рекурсивную функцию для обхода inorder для моего двоичного дерева.

Это то, что я сделал до сих пор:

class Node:
    def __init__(self, node):
        self.node = node
        self.left = None
        self.right= None



    def inorder_traversal(self):
        if self.node != None:
            return inorder_traversal(self.node.left)
            return self.node
            return inorder_traversal(self.node.right)

Кажется, я не понимаю, в чем дело.

Тествходы:

root = Node(1)
root.left = Node(3)
root.right = Node(4)

Ошибка:

File "trees-implementation.py", line 23, in inorder_traversal
    return inorder_traversal(self.node.left)
NameError: name 'inorder_traversal' is not defined

Answer 1

Во-первых, не могли бы вы проверить, если у вас есть объект, вы не поместите параметр в

root = Node ()

Тогда вы уверены, чтоу вас может быть несколько возвратов в вашей функции inorder_traversal ()?Наконец, функция находится в классе Node (), поэтому, если вы ее вызываете, попробуйте добавить self.yourfunction

Answer 2

Похоже, вы определили свои функции обхода относительно узла.Это имеет смысл для вас?

Вы должны определить обход относительно Дерева, а не Узла.Узел не знает, что он принадлежит дереву, это тупой объект.

Определить узел.

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right= None

Определить дерево.Также определите здесь свои методы обхода.

class Tree:
    def __init__(self, root=None):
        self.root = root

    def inorder_traversal(self):
        def _inorder(root):
            if root != None:
                yield from _inorder(root.left)
                yield root.value
                yield from _inorder(root.right)

        return list(_inorder(self.root))

Инициализируйте дерево с корнем, а затем обойдите его.

tree = Tree(root)
tree.inorder_traversal()
[3, 1, 4]