我试图实现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])
正如 @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