手劈二叉树

**手劈二叉树**

手劈二叉树是一种常见的数据结构，用于存储和操作有序的元素集合。它通过将元素分成左右子树来实现高效的查找、插入和删除操作。

### 二叉树定义

class Node:
 def __init__(self, value):
 self.value = value self.left = None self.right = None

def insert(root, value):
 if root is None:
 return Node(value)
 # 如果当前值小于根节点的值，插入到左子树中 if value < root.value:
 root.left = insert(root.left, value)
 else:
 # 否则，插入到右子树中 root.right = insert(root.right, value)
 return root

def delete(root, value):
 if root is None:
 return root # 如果当前值等于根节点的值，则删除该节点 if value == root.value:
 # 如果该节点只有一个子树，直接返回另一个子树 if root.left is None:
 return root.right elif root.right is None:
 return root.left # 否则，找到最小值的父节点（即右子树中最左边的节点）
 min_node = find_min(root.right)
 # 将该最小值替换为当前根节点的值，然后删除最小值所在的子树 root.value = min_node.value root.right = delete(root.right, min_node.value)
 else:
 # 如果当前值小于根节点的值，则递归删除左子树中的该值 if value < root.value:
 root.left = delete(root.left, value)
 else:
 # 否则，递归删除右子树中的该值 root.right = delete(root.right, value)
 return rootdef find_min(node):
 while node.left is not None:
 node = node.left return node

def search(root, value):
 if root is None or root.value == value:
 return root # 如果当前值小于根节点的值，则递归查找左子树中的该值 if value < root.value:
 return search(root.left, value)
 # 否则，递归查找右子树中的该值 return search(root.right, value)

# 创建一个空的二叉树root = None# 插入一些元素root = insert(root,5)
root = insert(root,3)
root = insert(root,7)
root = insert(root,2)
root = insert(root,4)
root = insert(root,6)

# 查找某个元素print(search(root,4).value) # 输出:4# 删除某个元素root = delete(root,5)

# 查找某个元素（删除后该值不再存在）
print(search(root,5)) # 输出: None