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

问题描述 投票:0回答:1

我试图实现BST,但是我的树的头值每次都返回None。我试着查找Python中的其他实现,但他们通常只是声明一个根,然后在类本身之外将其传递进来,而不是在类中包含头部自身。

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])
python data-structures binary-search-tree
1个回答
1
投票

正如 @MarkMeyer 指出的那样。currentNode = Node(data) 只创建了一个本地变量,因此你需要返回curretNode变量给调用者,并通过返回的变量更新节点。因此你需要将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
© www.soinside.com 2019 - 2024. All rights reserved.