我在Python中的插入BST实现有什么问题？

Question

我正在尝试实现BST，但是我的树的head值每次都返回无。我尝试在Python中查找其他实现，但它们通常只是声明一个根并将其传递到类本身之外，而不是将head自包含在类中。

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
    def __repr__(self):
        return self.data
    def __str__(self):
        return str(self.data)

class Tree:
    def __init__(self, nodes):
        self.head = None
        if nodes is not None:
            for elem in nodes:
                self.insert(self.head, elem)
        print(self.head) #prints out None every time

    def insert(self, currentNode, data):
        if(currentNode == None):
            currentNode = Node(data)
        if(data != currentNode.data):
            if(data < currentNode.data): 
                if(currentNode.left is None): currentNode.left = Node(data)
                else: self.insert(currentNode.left, data)
            elif(data > currentNode.data): 
                if(currentNode.right is None): currrentNode.right = Node(data)
                else: self.insert(currentNode.right, data)

    def inOrder(self, data=None, visitedHead=False):
        if not visitedHead:
            self.inOrder(self.head.left, True)
            print(self.head)
            self.inOrder(self.head.right, True)
        elif(data == None): return
        else:
            self.inOrder(data.left, True)
            print(data)
            self.inOrder(data.right, True)

treeTime = Tree([1, 80, 3, 0])

Answer 1

正如@MarkMeyer所指出的，loctNode=Node（data）只创建一个局部变量。因此，您需要将curretNode变量返回给调用者，并通过返回的变量更新节点。

当您修复四行（#1到#4）时，您将获得所需的结果。

class Tree:
    def __init__(self, nodes):
        self.head = None
        if nodes is not None:
            for elem in nodes:
                self.head = self.insert(self.head, elem) #1 Update the head
        print(self.head) #prints out None every time
        print(self.head.left)
        print(self.head.right)
        print(self.head.right.left)

    def insert(self, currentNode, data):
        if(currentNode == None):
            currentNode = Node(data)
        if(data != currentNode.data):
            if(data < currentNode.data): 
                if(currentNode.left is None): currentNode.left = Node(data)
                else: currentNode.left = self.insert(currentNode.left, data) #2 Update the left node
            elif(data > currentNode.data): 
                if(currentNode.right is None): currentNode.right = Node(data)
                else: currentNode.right = self.insert(currentNode.right, data) #3 Update the right node
        return currentNode #4 Return the currentNode

这是结果。

1  # head
0  # head.left
80 # head.right
3  # head.right.left