实现读入一串字符创建一棵二叉排序树,然后分别实现:二叉排序树的查找;二叉排序树的插入;二叉排序树的删除等操作
时间: 2023-11-28 17:45:37 浏览: 121
以下是实现读入一串字符创建一棵二叉排序树,然后分别实现二叉排序树的查找、插入、删除等操作的Python代码:
```python
# 定义二叉排序树的节点类
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
# 定义二叉排序树类
class BST:
def __init__(self):
self.root = None
# 插入节点
def insert(self, val):
if not self.root:
self.root = TreeNode(val)
return
cur = self.root
while cur:
if val < cur.val:
if not cur.left:
cur.left = TreeNode(val)
return
cur = cur.left
else:
if not cur.right:
cur.right = TreeNode(val)
return
cur = cur.right
# 查找节点
def search(self, val):
cur = self.root
while cur:
if cur.val == val:
return True
elif cur.val > val:
cur = cur.left
else:
cur = cur.right
return False
# 删除节点
def delete(self, val):
def find_min(root):
while root.left:
root = root.left
return root
def delete_node(root, val):
if not root:
return None
if root.val == val:
if not root.left and not root.right:
return None
if not root.left:
return root.right
if not root.right:
return root.left
min_node = find_min(root.right)
root.val = min_node.val
root.right = delete_node(root.right, min_node.val)
elif root.val > val:
root.left = delete_node(root.left, val)
else:
root.right = delete_node(root.right, val)
return root
self.root = delete_node(self.root, val)
# 读入一串字符
s = input()
# 创建二叉排序树
bst = BST()
for c in s:
bst.insert(c)
# 查找节点
print(bst.search('a'))
# 插入节点
bst.insert('b')
# 删除节点
bst.delete('a')
```
阅读全文