编程实现: (1)输入一数列,建立二叉排序树; (2)对所建立的二叉排序树进行查找操作,找到了就显示,找不到就插入; (3)对所建立的二叉排序树进行删除操作。
时间: 2023-12-19 08:06:37 浏览: 49
以下是 Python 代码实现:
```python
# 定义二叉排序树节点类
class TreeNode:
def __init__(self, val=None):
self.val = val
self.left = None
self.right = None
# 建立二叉排序树
def build_bst(nums):
root = None
for num in nums:
root = insert_bst(root, num)
return root
# 插入节点到二叉排序树
def insert_bst(root, val):
if not root:
return TreeNode(val)
if val < root.val:
root.left = insert_bst(root.left, val)
elif val > root.val:
root.right = insert_bst(root.right, val)
return root
# 查找节点并插入或返回
def search_bst(root, val):
if not root:
return TreeNode(val)
if val == root.val:
return root
elif val < root.val:
root.left = search_bst(root.left, val)
else:
root.right = search_bst(root.right, val)
return root
# 删除节点并重建二叉排序树
def delete_bst(root, val):
if not root:
return None
if val < root.val:
root.left = delete_bst(root.left, val)
elif val > root.val:
root.right = delete_bst(root.right, val)
else:
if not root.left:
return root.right
if not root.right:
return root.left
min_node = root.right
while min_node.left:
min_node = min_node.left
root.val = min_node.val
root.right = delete_bst(root.right, min_node.val)
return root
```
这里我们定义了一个 TreeNode 类,表示二叉排序树的节点。然后,我们定义了建立二叉排序树的函数 `build_bst`,它遍历输入的数列,调用 `insert_bst` 函数插入节点到二叉排序树中。而 `insert_bst` 函数则是用来插入节点到二叉排序树中的。
接下来,我们定义了 `search_bst` 函数,它在二叉排序树中查找节点。如果找到了,就返回该节点;如果没找到,就调用 `insert_bst` 函数插入节点到二叉排序树中。
最后,我们定义了 `delete_bst` 函数,它用来删除节点。如果节点不存在,就返回 None;如果要删除的节点是叶子节点,就直接删除;如果要删除的节点只有一个子节点,就将其子节点代替该节点;如果要删除的节点有两个子节点,就找到它右子树的最小值节点代替该节点,并删除该最小值节点。
这样,我们就实现了二叉排序树的建立、查找和删除操作。