利用python语言构造一个平衡二叉树,并进行旋转、查找最小节点、插入节点,删除节点操作
时间: 2025-01-01 19:36:44 浏览: 16
在Python中,我们可以使用内置数据结构`list`来模拟二叉搜索树(BST),因为Python并不是特别适合直接创建平衡二叉树(如AVL树、红黑树等)。但是,为了演示基本操作,我们可以手动维护平衡,通过比较元素值并调整结构。
首先,我们先定义一个简单的二叉树节点:
```python
class TreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def insert(self, value):
if value < self.value:
if self.left is None:
self.left = TreeNode(value)
else:
self.left.insert(value)
else:
if self.right is None:
self.right = TreeNode(value)
else:
self.right.insert(value)
def find_min(self):
current = self
while current.left:
current = current.left
return current.value
def delete(self, target_value):
# 删除过程较为复杂,涉及到四种情况:无子节点、只有一个子节点、有两个子节点
# 这里仅提供删除节点的基本思路,实际完整实现需要考虑所有边界条件
if target_value == self.value:
if self.left and self.right: # 有两个子节点
min_node = self.find_min()
self.value = min_node
self.right = self.delete(min_node) # 调用自身删除最小节点
elif self.left: # 只有左子节点
return self.left
elif self.right: # 只有右子节点
return self.right
else: # 没有子节点
return None
elif target_value < self.value:
if self.left:
self.left = self.left.delete(target_value)
else:
if self.right:
self.right = self.right.delete(target_value)
return self
def rotate_left(self):
# 这里假设left subtree has a right child
pivot, left, right = self, self.right, left.right
self.right = left
left.parent = self
right.parent = pivot
pivot.left = right
right.left = pivot
def rotate_right(self):
# 类似地,这里假设right subtree has a left child
pivot, left, right = self, self.left, left.left
self.left = right
right.parent = self
left.parent = pivot
pivot.right = left
left.right = pivot
# 示例
root = TreeNode(5)
root.insert(3)
root.insert(7)
root.insert(2)
root.insert(4)
root.insert(6)
root.insert(8)
# 查找最小节点
print(root.find_min()) # 输出 2
# 删除节点
root.delete(4)
# 旋转操作(这里仅作为示例,实际操作需根据节点的连接关系)
root.rotate_left()
# ... 更多操作...
```
请注意,上述代码并未处理所有删除操作的边界情况,也没有实现真正的自平衡二叉树。对于复杂的平衡二叉树,如AVL树或红黑树,推荐使用现成的数据结构库,比如`sortedcontainers`或`binarytree`。同时,对于实际生产环境,建议使用专门设计的二叉搜索树实现,例如Python的`bisect`模块,或者像`PyTrees`这样的第三方库。
阅读全文