我正在自学二进制搜索树,在此程序中,我正在树中插入数据,但发生错误'NoneType' object has no attribute 'data'
错误。
from collections import deque
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def insert(rnode, data):
if data > rnode.data:
insert(rnode.right, data)
rnode.right.data = data
return print('Node inserted')
if data < rnode.data:
insert(rnode.left, data)
rnode.left.data = data
return print('Node inserted')
def bfs():
q = deque()
temp = self.root
while temp:
print(temp.data)
q.append(temp.left)
q.append(temp.right)
temp = q.popleft()
root = Node(8)
insert(root, 3)
bfs()
错误:
Exception has occurred: AttributeError
'NoneType' object has no attribute 'data'
File "/home/mayank/Documents/datastructures/binarysearchtree.py", line 9, in insert
if data > rnode.data:
File "/home/mayank/Documents/datastructures/binarysearchtree.py", line 14, in insert
insert(rnode.left, data)
File "/home/mayank/Documents/datastructures/binarysearchtree.py", line 29, in <module>
insert(root, 3)
救命!!
最佳答案
您的insert
函数假定rnode.right
和rnode.left
始终引用可插入值的树,但是rnode
是叶子(如果在插入树时最终将是叶子)则不是这种情况。 insert
需要为新值创建一个新节点。
def insert(rnode, data):
if data > rnode.data:
if rnode.right is None:
rnode.right = Node(data)
else:
insert(rnode.right, data)
if data < rnode.data:
if rnode.left is None:
rnode.left = Node(data)
else:
insert(rnode.left, data)