发表更新2 分钟读完 (大约269个字)
删除一个二叉搜索树的节点
三种情况
- Case 1
删除的节点没有子节点(即该节点为叶节点)
操作:直接delete
- Case 2
删除的节点下有一个子节点
操作:用左/右子树代替该节点
- Case 3
删除的节点有两个子节点
操作:
- 找到右子树中的最小值
- 复制该值到删除的节点处
- (如果树中的数据都各不相同的话)我们需要删去右子树中的最小值,因为右子树的最小值没有左子树,所以删去它的情况就降为Case1或Case2
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
| BstNode* FindMin(BstNode* root) { if (root->left == NULL)return root; else return FindMin(root->left); } struct BstNode* Delete(BstNode* root, int data) { if (root == NULL)return root; else if (data < root->data)root->left = Delete(root->left, data); else if (data > root->data)root->right = Delete(root->right, data); else { if (root->left == NULL && root->right == NULL) { delete root; root = NULL; } else if (root->left == NULL) { BstNode* temp = root; root = root->right; delete temp; } else if (root->right == NULL) { BstNode* temp = root; root = root->left; delete temp; } else { BstNode* temp = FindMin(root->right); root->data = temp->data; root->right = Delete(root->right, temp->data); } } return root; }
|