我要你用c或者c++生成排序二叉树,并写出详细的删除操作
时间: 2024-09-21 19:07:55 浏览: 33
C++写的数据结构算法源码,很详细的
4星 · 用户满意度95%
在C++中,我们可以使用二叉搜索树(Binary Search Tree, BST)的数据结构来实现排序。首先,我们需要定义一个简单的二叉节点结构:
```cpp
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
```
接下来,我们创建一个BST的类,包含插入、查找以及删除操作:
```cpp
class BST {
private:
TreeNode* root;
public:
BST() : root(nullptr) {}
// 插入操作
void insert(int val) {
if (!root) {
root = new TreeNode(val);
return;
}
TreeNode* current = root;
while (true) {
if (val < current->val)
current = current->left ? current->left : ¤t->left;
else if (val > current->val)
current = current->right ? current->right : ¤t->right;
else
break; // 如果值已经存在,就不再插入
}
current->val = val;
}
// 删除操作 - 采用递归实现,这里简化了对子树节点替换的情况
void remove(int val) {
root = removeNode(root, val);
}
private:
TreeNode* removeNode(TreeNode* node, int val) {
if (!node)
return nullptr;
if (val < node->val)
node->left = removeNode(node->left, val);
else if (val > node->val)
node->right = removeNode(node->right, val);
else {
// 找到要删除的节点
if (!node->left && !node->right) { // 节点无子节点,直接删除
delete node;
node = nullptr;
} else if (!node->left) { // 只有右子节点,将右子节点替换当前节点
TreeNode* temp = node;
node = node->right;
delete temp;
} else if (!node->right) { // 只有左子节点,将左子节点替换当前节点
TreeNode* temp = node;
node = node->left;
delete temp;
} else { // 节点有两个子节点,找到右子树最小的节点替换它
TreeNode* minNode = findMin(node->right);
node->val = minNode->val;
node->right = removeNode(node->right, minNode->val);
}
}
return node;
}
// 辅助函数,查找最小值节点
TreeNode* findMin(TreeNode* node) {
while (node->left) {
node = node->left;
}
return node;
}
};
```
以上代码实现了基本的排序二叉树的插入和删除功能。注意这只是一个简化的版本,实际应用中可能需要处理更复杂的情况,例如平衡二叉搜索树的删除操作会更复杂一些。
阅读全文