Python 中的二叉搜索树数据结构

Question

我正在尝试自学 Python，来自 C++，所以我决定尝试构建一个简单的 BST。我设法让我的插入方法正常工作，但我不知道为什么我的 printTree 方法失败了。口译员给我错误：

Traceback (most recent call last): File "test.py", line 40, in myTree.printTree() File "test.py", line 23, in printTree printTree(self.left) NameError: global name 'printTree' is not defined

代码：

class Node(object):                                                                                                                                                                  

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

    def insert(self, node):                                                                                                                                                          
        if self is None:                                                                                                                                                             
            self = node                                                                                                                                                              
        else:                                                                                                                                                                        
            if node.value <= self.value:                                                                                                                                             
                if self.left: insert(self.left, node)                                                                                                                                
                else: self.left = node                                                                                                                                               
            else:                                                                                                                                                                    
                if self.right: insert(self.right, node)                                                                                                                              
                else: self.right = node                                                                                                                                              

    def printTree(self):                                                                                                                                                             
        if not self:                                                                                                                                                                 
            return                                                                                                                                                                   
        else:                                                                                                                                                                        
            printTree(self.left)                                                                                                                                                     
            print(self.value)                                                                                                                                                        
            printTree(self.right)

if __name__ == "__main__":
    myTree = Node(3)
    myTree.insert(Node(2))
    myTree.insert(Node(4))

    myTree.printTree()

我可以不这样传递当前实例吗？

Answer 1

您在方法中对 printTree 的递归调用应该是 self.printTree()。 Python 与 C++ 中的默认作用域不同！

而在 C++ 中，默认范围是当前对象 (*this)，而在 Python 中并非如此。无论我们处理的是全局函数还是方法，默认（非限定）作用域都是相同的。