Python 3 : 递归错误引发NameError (BST问题)

Question

当我把in-order traversal作为我的类的一个方法运行时，我遇到了一个问题。

class BST:
    def __init__(self,data):
        self.data=data
        self.left=None
        self.right=None

    def insert(self,data):
        if self.data < data:
            #insert right
            if self.right is None:
                self.right = BST(data)
            else:
                insert(self.right, data)
        else:
            if self.left is None:
                self.left = BST(data)
            else:
                insert(self.left,data)

     def inorder(self):
        if self.left:
            inorder(self.left)
        print(self.data)
        if self.right:
            inorder(self.right)


r = BST('50')
r.insert('60')
r.insert('40')
r.inorder()

这对于插入来说是很好的。请注意，我没有使用self.insert，只是用insert进行递归。

下面是我在BST类中的顺序遍历方法。

    def inorder(self):
        if self.left:
            inorder(self.left)
        print(self.data)
        if self.right:
            inorder(self.right)

这时会出现一个错误，说

30 r.insert('60')
     31 r.insert('40')
---> 32 r.inorder()
     33 print(r.right.data)
     34 print(r.left.data)

AttributeError: 'BST' object has no attribute 'inorder'.

我试着使用self.inorder()，它说它收到了两个参数，虽然它期望的是一个。

然而，如果我把inorder(Self.left)的代码修改为self.left.inorder()，它就能正常工作。

谁能解释一下为什么会发生这种情况？另外，在类方法内部使用self.function_name进行递归调用是否很重要，因为我的insert函数无论如何都能工作？

Answer 1

试试使用帮助函数。

class BST:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None


def insert(root, bst):
    if root is None:
        root = bst
    else:
        if root.data < bst.data:
            if root.right is None:
                root.right = bst
            else:
                insert(root.right, bst)
        else:
            if root.left is None:
                root.left = bst
            else:
                insert(root.left, bst)


def inorder(root):
    if root:
        inorder(root.left)
        print(root.data)
        inorder(root.right)


r = BST(50)
insert(r, BST(60))
insert(r, BST(40))
inorder(r)

如果你想把帮助函数作为方法包含在类中，那么你可以这样写。

class BST:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

    def insert(self, root, bst):
        if root is None:
            root = bst
        else:
            if root.data < bst.data:
                if root.right is None:
                    root.right = bst
                else:
                    self.insert(root.right, bst)
            else:
                if root.left is None:
                    root.left = bst
                else:
                    self.insert(root.left, bst)

    def inorder(self, root):
        if root:
            self.inorder(root.left)
            print(root.data)
            self.inorder(root.right)


r = BST(50)
r.insert(r, BST(60))
r.insert(r, BST(40))
r.inorder(r)