编程实现读入一串字符创建一棵二叉排序树,然后分别实现:二叉排序树的查找、插入、删除,并给出流程
时间: 2024-04-30 19:21:55 浏览: 20
以下是 Python 代码实现:
```python
# 定义二叉排序树的结点
class BSTNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
# 插入结点
def insert(root, val):
if not root: # 如果树为空,则将新结点作为根结点
return BSTNode(val)
if val < root.val: # 如果新结点值小于根结点值,则插入到左子树中
root.left = insert(root.left, val)
elif val > root.val: # 如果新结点值大于根结点值,则插入到右子树中
root.right = insert(root.right, val)
return root
# 查找结点
def search(root, val):
if not root or root.val == val: # 如果找到了结点或者树为空,则返回根结点
return root
if val < root.val: # 如果要查找的值小于根结点值,则在左子树中查找
return search(root.left, val)
else: # 如果要查找的值大于根结点值,则在右子树中查找
return search(root.right, val)
# 删除结点
def delete(root, val):
if not root: # 如果树为空,则直接返回根结点
return root
if val < root.val: # 如果要删除的值小于根结点值,则在左子树中删除
root.left = delete(root.left, val)
elif val > root.val: # 如果要删除的值大于根结点值,则在右子树中删除
root.right = delete(root.right, val)
else: # 如果找到了要删除的结点
if not root.left: # 如果要删除的结点没有左子树,则直接用右子树代替该结点
temp = root.right
root = None
return temp
elif not root.right: # 如果要删除的结点没有右子树,则直接用左子树代替该结点
temp = root.left
root = None
return temp
else: # 如果要删除的结点既有左子树又有右子树,则用右子树中最小结点代替该结点
temp = minValueNode(root.right)
root.val = temp.val
root.right = delete(root.right, temp.val)
return root
# 寻找最小值结点
def minValueNode(node):
current = node
while current.left:
current = current.left
return current
# 中序遍历二叉排序树
def inorder(root):
if not root:
return
inorder(root.left)
print(root.val)
inorder(root.right)
# 构建二叉排序树
def buildBST(s):
root = None
for c in s:
root = insert(root, c)
return root
# 测试
if __name__ == '__main__':
s = input("请输入一串字符:")
root = buildBST(s)
inorder(root)
# 查找结点
val = input("请输入要查找的值:")
node = search(root, val)
if node:
print("找到了结点:" + str(node.val))
else:
print("未找到结点")
# 插入结点
val = input("请输入要插入的值:")
insert(root, val)
inorder(root)
# 删除结点
val = input("请输入要删除的值:")
delete(root, val)
inorder(root)
```
运行结果示例:
```
请输入一串字符:bcaedf
a
b
c
d
e
f
请输入要查找的值:d
找到了结点:d
请输入要插入的值:g
a
b
c
d
e
f
g
请输入要删除的值:e
a
b
c
d
f
g
```
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![txt](https://img-home.csdnimg.cn/images/20210720083642.png)