二叉搜索树的底限和上限 Python
Floor and Ceil of Binary Search Tree Python
我正在尝试计算 bst 的 ceil 和 floor 值,ceil 代码有效但我无法获得正确的 floor 值,我计算了 10 的 floor,在提供的测试用例中应该是10,但它 returns 9,我不确定为什么。
有什么想法吗?
谢谢
class node():
def __init__(self, key, data):
self.data = data
self.key = key
self.leftnode = None
self.rightnode = None
class binarysearch():
def __init__(self):
self.size = 0
self.rootnode = None
def insert(self, key, data):
if self.rootnode == None:
self.rootnode = node(key, data)
else:
self.insertnode(self.rootnode, key, data)
def getroot(self):
return self.rootnode
def insertnode(self, root, key, data):
if root.key == key:
root.data = data
elif key < root.key:
if root.leftnode is None:
root.leftnode = node(key, data)
else:
self.insertnode(root.leftnode, key, data)
else:
if root.rightnode is None:
root.rightnode = node(key, data)
else:
self.insertnode(root.rightnode, key, data)
def searchkey(self, key):
if self.rootnode == None:
return False
else:
found = self.searchnode(self.rootnode, key)
if found:
return True
else:
return False
def searchnode(self, root, key):
if root == None:
return False
else:
if key == root.key:
return True
elif key < root.key:
self.searchnode(root.leftnode, key)
else:
self.searchnode(root.rightnode, key)
def floor(self, root, key):
if root == None:
return None
elif root.key == key:
return key
elif root.key > key:
self.floor(root.leftnode, key)
else:
floorkey = self.floor(root.rightnode, key)
if (floorkey is None) or (floorkey > key):
return root.key
else:
return floorkey
def ceil(self, root, key):
if root == None:
return None
elif root.key == key:
return key
elif root.key < key:
return self.ceil(root.rightnode, key)
else:
ceilkey = self.ceil(root.leftnode, key)
if (ceilkey is None) or (ceilkey < key):
return root.key
else:
return ceilkey
if __name__ == '__main__':
a = binarysearch()
a.insert(7,7)
a.insert(1,1)
a.insert(8,8)
a.insert(3,3)
a.insert(9,9)
a.insert(2,2)
a.insert(4,4)
a.insert(11,11)
a.insert(10,10)
a.searchkey(7)
root = a.getroot()
ceil = a.ceil(root, 10)
print(ceil)
floor = a.floor(root, 10)
print(floor)
您在 floor 函数的这一行缺少 return:
self.floor(root.leftnode, key)
我正在尝试计算 bst 的 ceil 和 floor 值,ceil 代码有效但我无法获得正确的 floor 值,我计算了 10 的 floor,在提供的测试用例中应该是10,但它 returns 9,我不确定为什么。
有什么想法吗? 谢谢
class node():
def __init__(self, key, data):
self.data = data
self.key = key
self.leftnode = None
self.rightnode = None
class binarysearch():
def __init__(self):
self.size = 0
self.rootnode = None
def insert(self, key, data):
if self.rootnode == None:
self.rootnode = node(key, data)
else:
self.insertnode(self.rootnode, key, data)
def getroot(self):
return self.rootnode
def insertnode(self, root, key, data):
if root.key == key:
root.data = data
elif key < root.key:
if root.leftnode is None:
root.leftnode = node(key, data)
else:
self.insertnode(root.leftnode, key, data)
else:
if root.rightnode is None:
root.rightnode = node(key, data)
else:
self.insertnode(root.rightnode, key, data)
def searchkey(self, key):
if self.rootnode == None:
return False
else:
found = self.searchnode(self.rootnode, key)
if found:
return True
else:
return False
def searchnode(self, root, key):
if root == None:
return False
else:
if key == root.key:
return True
elif key < root.key:
self.searchnode(root.leftnode, key)
else:
self.searchnode(root.rightnode, key)
def floor(self, root, key):
if root == None:
return None
elif root.key == key:
return key
elif root.key > key:
self.floor(root.leftnode, key)
else:
floorkey = self.floor(root.rightnode, key)
if (floorkey is None) or (floorkey > key):
return root.key
else:
return floorkey
def ceil(self, root, key):
if root == None:
return None
elif root.key == key:
return key
elif root.key < key:
return self.ceil(root.rightnode, key)
else:
ceilkey = self.ceil(root.leftnode, key)
if (ceilkey is None) or (ceilkey < key):
return root.key
else:
return ceilkey
if __name__ == '__main__':
a = binarysearch()
a.insert(7,7)
a.insert(1,1)
a.insert(8,8)
a.insert(3,3)
a.insert(9,9)
a.insert(2,2)
a.insert(4,4)
a.insert(11,11)
a.insert(10,10)
a.searchkey(7)
root = a.getroot()
ceil = a.ceil(root, 10)
print(ceil)
floor = a.floor(root, 10)
print(floor)
您在 floor 函数的这一行缺少 return:
self.floor(root.leftnode, key)