首先编程实现读入一串字符创建一棵二叉排序树,然后分别实现:二叉排序树的查找;二叉排序树的插入;二叉排序树的删除等操作。
时间: 2023-10-13 21:06:10 浏览: 87
好的,下面是实现代码:
```python
class TreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
class BinarySearchTree:
def __init__(self):
self.root = None
def insert(self, value):
if not self.root:
self.root = TreeNode(value)
else:
self._insert(value, self.root)
def _insert(self, value, node):
if value < node.value:
if node.left:
self._insert(value, node.left)
else:
node.left = TreeNode(value)
else:
if node.right:
self._insert(value, node.right)
else:
node.right = TreeNode(value)
def search(self, value):
return self._search(value, self.root)
def _search(self, value, node):
if not node:
return False
elif node.value == value:
return True
elif value < node.value:
return self._search(value, node.left)
else:
return self._search(value, node.right)
def delete(self, value):
self._delete(value, self.root)
def _delete(self, value, node):
if not node:
return node
if value < node.value:
node.left = self._delete(value, node.left)
elif value > node.value:
node.right = self._delete(value, node.right)
else:
if not node.left:
return node.right
elif not node.right:
return node.left
else:
temp = self._get_min_node(node.right)
node.value = temp.value
node.right = self._delete(temp.value, node.right)
return node
def _get_min_node(self, node):
while node.left:
node = node.left
return node
```
可以使用以下代码进行测试:
```python
bst = BinarySearchTree()
list_input = list(map(int, input().split()))
for num in list_input:
bst.insert(num)
print("Binary search tree created!")
print("Search for 5: ", bst.search(5))
print("Search for 10: ", bst.search(10))
print("Delete 5 from the tree")
bst.delete(5)
print("Search for 5: ", bst.search(5))
```
阅读全文