二叉排序树插入和删除操作C语言

二叉排序树（Binary Search Tree, BST）是一种特殊的二叉树，其中每个节点的值大于其左子树中的所有节点，小于其右子树中的所有节点。在C语言中，插入和删除操作通常涉及递归算法。

**插入操作**:
1. 从根节点开始比较要插入的值。
2. 如果新值小于当前节点，如果左子树为空则直接插入，否则继续在左子树中递归查找合适的位置。
3. 如果新值大于当前节点，同样，如果右子树为空则插入，否则继续在右子树递归。
4. 插入完成后，保持BST性质，即左右子树分别满足BST规则。

void insert(BSTNode* node, int value) {
   if (node == NULL) { // 如果为空，创建新节点
       node = (BSTNode*)malloc(sizeof(BSTNode));
       node->data = value;
       node->left = NULL;
       node->right = NULL;
   } else if (value < node->data) {
       node->left = insert(node->left, value); // 递归左子树
   } else {
       node->right = insert(node->right, value); // 递归右子树
   }
}

**删除操作**:
1. 查找要删除的节点，有三种情况：
- 节点无子节点：直接删除并释放内存。
- 只有一个子节点：将该子节点替换到当前节点位置。
- 有两个子节点：找到左子树的最大值（或右子树的最小值），替换当前节点，并删除这个最大值（或最小值）。

BSTNode* deleteNode(BSTNode* root, int key) {
   if (root == NULL) return root; // 没有找到节点，返回NULL

   // 分别处理三种情况
   if (key < root->data)
       root->left = deleteNode(root->left, key);
   else if (key > root->data)
       root->right = deleteNode(root->right, key);
   else { // 找到了要删除的节点
      // ...后续根据子节点情况处理...
   }

   // 保持BST结构，平衡删除后的树
   return root;
}