数据结构: 设计一个算法,它从二叉检索树中删除一个结点,并仍然保持二叉检索树的特性不变。 要求: (1)若*p结点为叶子结点,即PL(左子树)和PR(右子树)均为空树。由于删去叶子结点不破坏整棵树的结构,则只需修改其双亲结点的指针即可。 (2)若*p结点只有左子树PL或右子树PR,此时只要令PL或PR直接成为其双亲结点*f的左子树或右子树即可,作此修改也不破坏二叉检索树的特性。 (3)若*p结点的左子树和右子树均不空。在删去*p之后,为保持其它元素之间的相对位置不变,可按中序遍历保持有序进行调整,可以有两种做法:其一是令*p的左子树为*f的左子树,*s为*f左子树的最右下的结点,而*p的右子树为*s的右子树;其二是令*p的直接前驱或直接后继替代*p,然后再从二叉排序树中删去它的直接前驱或直接后继。 根据上述要求写出代码
时间: 2024-03-07 11:47:09 浏览: 81
以下是删除二叉搜索树中指定节点的代码实现(C++):
```cpp
#include<iostream>
using namespace std;
typedef struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
}TreeNode;
TreeNode* findMin(TreeNode* root) { // 查找以root为根节点的二叉搜索树中最小的节点
while (root->left) {
root = root->left;
}
return root;
}
TreeNode* deleteNode(TreeNode* root, int key) {
if (!root) return NULL; // 如果为空树,直接返回NULL
if (key < root->val) { // 如果需要删除的节点在左子树中
root->left = deleteNode(root->left, key); // 递归删除左子树中的节点
}
else if (key > root->val) { // 如果需要删除的节点在右子树中
root->right = deleteNode(root->right, key); // 递归删除右子树中的节点
}
else { // 找到了需要删除的节点
if (!root->left && !root->right) { // 如果该节点为叶子节点,直接删除
delete root;
root = NULL;
}
else if (root->left && !root->right) { // 如果该节点只有左子树,直接删除并用左子树替代该节点
TreeNode *tmp = root;
root = root->left;
delete tmp;
}
else if (!root->left && root->right) { // 如果该节点只有右子树,直接删除并用右子树替代该节点
TreeNode *tmp = root;
root = root->right;
delete tmp;
}
else { // 如果该节点既有左子树又有右子树
TreeNode *tmp = findMin(root->right); // 找到右子树中最小的节点,即该节点的直接后继
root->val = tmp->val; // 将该节点的值替换为直接后继的值
root->right = deleteNode(root->right, tmp->val); // 递归删除右子树中的直接后继节点
}
}
return root;
}
int main() {
TreeNode* root = new TreeNode(5);
root->left = new TreeNode(3);
root->right = new TreeNode(6);
root->left->left = new TreeNode(2);
root->left->right = new TreeNode(4);
root->right->right = new TreeNode(7);
cout << "Before deleting node: ";
inorderTraversal(root); // 中序遍历输出删除前的二叉搜索树
int key = 3; // 需要删除的节点的值
root = deleteNode(root, key);
cout << "After deleting node: ";
inorderTraversal(root); // 中序遍历输出删除后的二叉搜索树
return 0;
}
```
其中,`findMin`函数用于找到以root为根节点的二叉搜索树中最小的节点,`deleteNode`函数用于递归删除指定节点并保持二叉搜索树特性。最后,我们可以通过调用`deleteNode`函数来删除指定节点,并通过中序遍历输出删除前后的二叉搜索树。
阅读全文