用python写一个二叉搜索树,要具有插入、查找、删除的功能
时间: 2024-06-06 19:07:20 浏览: 57
class Node:
def __init__(self, value):
self.value = value
self.left_child = None
self.right_child = None
class BinarySearchTree:
def __init__(self):
self.root = None
def insert(self, value):
if not self.root:
self.root = Node(value)
else:
self._insert(value, self.root)
def _insert(self, value, current_node):
if value < current_node.value:
if not current_node.left_child:
current_node.left_child = Node(value)
else:
self._insert(value, current_node.left_child)
elif value > current_node.value:
if not current_node.right_child:
current_node.right_child = Node(value)
else:
self._insert(value, current_node.right_child)
else:
print("Value already in tree!")
def find(self, value):
if self.root:
is_found = self._find(value, self.root)
if is_found:
return True
return False
else:
return None
def _find(self, value, current_node):
if value == current_node.value:
return True
elif value < current_node.value and current_node.left_child:
return self._find(value, current_node.left_child)
elif value > current_node.value and current_node.right_child:
return self._find(value, current_node.right_child)
return False
def delete(self, value):
if self.root is None:
return None
else:
self.root = self._delete(value, self.root)
def _delete(self, value, current_node):
if current_node is None:
return current_node
if value < current_node.value:
current_node.left_child = self._delete(value, current_node.left_child)
elif value > current_node.value:
current_node.right_child = self._delete(value, current_node.right_child)
else:
if current_node.left_child is None:
temp = current_node.right_child
current_node = None
return temp
elif current_node.right_child is None:
temp = current_node.left_child
current_node = None
return temp
temp = self._min_value_node(current_node.right_child)
current_node.value = temp.value
current_node.right_child = self._delete(temp.value, current_node.right_child)
return current_node
def _min_value_node(self, node):
current = node
while current.left_child is not None:
current = current.left_child
return current
bst = BinarySearchTree()
bst.insert(50)
bst.insert(30)
bst.insert(20)
bst.insert(40)
bst.insert(70)
bst.insert(60)
bst.insert(80)
print(bst.find(30)) # True
print(bst.find(10)) # False
bst.delete(20)
print(bst.find(20)) # False
bst.delete(30)
print(bst.find(30)) # False
bst.delete(50)
print(bst.find(50)) # False
阅读全文