BST删除节点的3种情况详解

一、先解答上次的思考题依次插入10 7 15 3 9 12 18中序遍历结果3 7 9 10 12 15 18查找 9存在二、今天学习目标BST 删除节点的3 种情况每种情况的处理逻辑完整可运行删除代码插入 删除 遍历综合测试三、BST 删除的 3 种情况设要删除的节点为cur情况 1cur 是叶子节点无孩子直接删掉父节点指向 NULL 即可。情况 2cur 只有一个孩子左或右让父节点直接接过它的孩子。情况 3cur 有两个孩子找左子树最大值或右子树最小值替换当前节点再删掉那个替换节点。 最简单做法用中序前驱 / 后继替换。四、完整代码含删除#include stdio.h #include stdlib.h struct TreeNode { int data; struct TreeNode *left; struct TreeNode *right; }; // 创建节点 struct TreeNode* createNode(int val) { struct TreeNode* node (struct TreeNode*)malloc(sizeof(struct TreeNode)); node-data val; node-left NULL; node-right NULL; return node; } // 插入 struct TreeNode* insert(struct TreeNode* root, int val) { if (root NULL) return createNode(val); if (val root-data) root-left insert(root-left, val); else if (val root-data) root-right insert(root-right, val); return root; } // 找最小值节点用于删除 struct TreeNode* minNode(struct TreeNode* root) { struct TreeNode* cur root; while (cur cur-left) cur cur-left; return cur; } // BST 删除核心 struct TreeNode* deleteNode(struct TreeNode* root, int key) { if (root NULL) return NULL; // 1. 找到要删除的节点 if (key root-data) root-left deleteNode(root-left, key); else if (key root-data) root-right deleteNode(root-right, key); // 2. 找到了开始删除 else { // 情况1无孩子 或 只有一个孩子 if (root-left NULL) { struct TreeNode* temp root-right; free(root); return temp; } else if (root-right NULL) { struct TreeNode* temp root-left; free(root); return temp; } // 情况3两个孩子都有 // 找右子树最小值替换 struct TreeNode* temp minNode(root-right); root-data temp-data; // 删除那个最小值节点 root-right deleteNode(root-right, temp-data); } return root; } // 中序遍历有序 void inOrder(struct TreeNode* root) { if (root NULL) return; inOrder(root-left); printf(%d , root-data); inOrder(root-right); } // 主函数测试 int main() { struct TreeNode* root NULL; int nums[] {10,7,15,3,9,12,18}; int n sizeof(nums)/sizeof(nums[0]); for (int i0; in; i) root insert(root, nums[i]); printf(删除前中序); inOrder(root); // 删除节点 10有两个孩子 root deleteNode(root, 10); printf(\n删除 10 后); inOrder(root); // 删除节点 3叶子 root deleteNode(root, 3); printf(\n删除 3 后); inOrder(root); return 0; }五、运行结果删除前中序3 7 9 10 12 15 18 删除 10 后3 7 9 12 15 18 删除 3 后7 9 12 15 18六、核心记忆口诀叶子节点直接删一个孩子爹接管孩子两个孩子找后继替换再删七、今日小练习对树10,7,15,3,9,12,18删除 15删除 7输出最终中序遍历可以直接用上面代码修改测试。