二叉排序树基本操作的实现
时间: 2023-10-25 08:30:21 浏览: 46
二叉排序树也称为二叉搜索树,它是一种特殊的二叉树,满足以下性质:
1. 左子树中的所有节点的值均小于根节点的值;
2. 右子树中的所有节点的值均大于根节点的值;
3. 左子树和右子树也都是二叉排序树。
基本操作包括插入节点、删除节点和查找节点。下面是它们的实现:
1. 插入节点:
插入节点操作用于向二叉排序树中插入一个新节点。从根节点开始,比较插入节点的值与当前节点的值,如果小于当前节点的值,则进入左子树,否则进入右子树。直到找到一个空位置,将新节点插入到该位置。
示例代码如下:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def insert_node(root, val):
if root is None:
return TreeNode(val)
if val < root.val:
root.left = insert_node(root.left, val)
else:
root.right = insert_node(root.right, val)
return root
```
2. 删除节点:
删除节点操作用于从二叉排序树中删除指定节点。分为三种情况:
- 被删除节点没有子节点:直接删除即可;
- 被删除节点只有一个子节点:将子节点替代被删除节点的位置;
- 被删除节点有两个子节点:找到被删除节点的后继节点(右子树中最小的节点),将后继节点的值复制到被删除节点,然后删除后继节点。
示例代码如下:
```python
def find_min(node):
while node.left is not None:
node = node.left
return node
def delete_node(root, val):
if root is None:
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 root.left is None:
return root.right
elif root.right is None:
return root.left
else:
successor = find_min(root.right)
root.val = successor.val
root.right = delete_node(root.right, successor.val)
return root
```
3. 查找节点:
查找节点操作用于在二叉排序树中查找指定值的节点。从根节点开始,比较目标值与当前节点的值,如果小于当前节点的值,则进入左子树,否则进入右子树。如果找到匹配的节点,则返回该节点;如果遍历完整个树仍未找到匹配的节点,则返回空。
示例代码如下:
```python
def search_node(root, val):
if root is None or root.val == val:
return root
if val < root.val:
return search_node(root.left, val)
else:
return search_node(root.right, val)
```
以上是二叉排序树基本操作的实现。你可以根据需要调用这些函数来操作二叉排序树。