首先编程实现读入一串字符创建一棵二叉排序树,然后分别实现:二叉排序树的查找;二叉排序树的插入;二叉排序树的删除等操作。
时间: 2023-10-16 21:33:38 浏览: 91
二叉排序树的基本操作-创建,查找,删除,插入(C++)
4星 · 用户满意度95%
好的,下面是 Python 代码实现:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
class BinarySearchTree:
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 val == cur.val:
return True
elif val < cur.val:
cur = cur.left
else:
cur = cur.right
return False
def delete(self, val):
def find_min(node):
while node.left:
node = node.left
return node
def delete_node(root, val):
if not root:
return root
if val < root.val:
root.left = delete_node(root.left, val)
elif val > root.val:
root.right = delete_node(root.right, val)
else:
if not root.left and not root.right:
root = None
elif not root.left:
root = root.right
elif not root.right:
root = root.left
else:
min_node = find_min(root.right)
root.val = min_node.val
root.right = delete_node(root.right, min_node.val)
return root
self.root = delete_node(self.root, val)
```
其中,`TreeNode` 表示二叉排序树的节点,包含 `val` 值、`left` 左子树、`right` 右子树。`BinarySearchTree` 表示二叉排序树,包含 `root` 根节点和三个操作 `insert` 插入、`search` 查找、`delete` 删除。
在 `insert` 操作中,如果根节点为空,则直接插入;否则,从根节点开始遍历,如果插入的值比当前节点小,则往左子树遍历;如果插入的值比当前节点大,则往右子树遍历;直到找到一个节点,其左或右子树为空,此时插入新节点。
在 `search` 操作中,从根节点开始遍历,如果查找的值等于当前节点的值,则返回 True;如果查找的值小于当前节点的值,则往左子树遍历;如果查找的值大于当前节点的值,则往右子树遍历;直到遍历完整棵树都没有找到,则返回 False。
在 `delete` 操作中,分为三种情况:
1. 要删除的节点没有子节点,直接将其置为 None。
2. 要删除的节点只有一个子节点,将该子节点替换到要删除的节点的位置上。
3. 要删除的节点有两个子节点,先找到右子树中最小的节点,将该节点的值赋给要删除的节点,然后再递归删除右子树中的最小节点。
最后,我们可以按照以下步骤使用上述代码:
1. 创建一个二叉排序树对象 `bst = BinarySearchTree()`。
2. 读入一串字符,通过 `split()` 方法将其拆分成多个字符串,并将其转换成整数类型。
3. 遍历这些整数,在二叉排序树中插入每一个数,即 `bst.insert(num)`。
4. 可以使用 `bst.search(val)` 查找指定的值是否在二叉排序树中。
5. 可以使用 `bst.delete(val)` 删除指定的值在二叉排序树中的节点。
阅读全文