在树ds中按序遍历时递归函数失败

Question

我试图实现树数据结构，但我卡住了，并有困难理解如何创建一个递归函数，以便遍历我的二叉树。你知道吗

这就是我目前所做的：

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()

那么您确定在您的inoder\u traversal（）函数中可以有多个返回吗？ 最后，函数位于类Node（）中，因此如果调用它，请尝试添加自我功能你知道吗

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]