c++二叉查找树增删查改
时间: 2023-11-24 07:50:27 浏览: 26
以下是C++实现二叉搜索树的增删查改的示例代码:
1. 结点类的实现:
```c++
class Node {
public:
int val;
Node* left;
Node* right;
Node(int val) {
this->val = val;
this->left = nullptr;
this->right = nullptr;
}
};
```
2. 二叉搜索树类的实现:
```c++
class BST {
public:
Node* root;
BST() {
root = nullptr;
}
// 插入操作
void insert(int val) {
root = insertNode(root, val);
}
// 删除操作
void remove(int val) {
root = removeNode(root, val);
}
// 查找操作
bool search(int val) {
return searchNode(root, val);
}
// 修改操作
void modify(int oldVal, int newVal) {
remove(oldVal);
insert(newVal);
}
private:
// 插入结点
Node* insertNode(Node* node, int val) {
if (node == nullptr) {
return new Node(val);
}
if (val < node->val) {
node->left = insertNode(node->left, val);
} else if (val > node->val) {
node->right = insertNode(node->right, val);
}
return node;
}
// 删除结点
Node* removeNode(Node* node, int val) {
if (node == nullptr) {
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 == nullptr && node->right == nullptr) {
delete node;
node = nullptr;
} else if (node->left == nullptr) {
Node* temp = node;
node = node->right;
delete temp;
} else if (node->right == nullptr) {
Node* temp = node;
node = node->left;
delete temp;
} else {
Node* temp = findMin(node->right);
node->val = temp->val;
node->right = removeNode(node->right, temp->val);
}
}
return node;
}
// 查找结点
bool searchNode(Node* node, int val) {
if (node == nullptr) {
return false;
}
if (val == node->val) {
return true;
} else if (val < node->val) {
return searchNode(node->left, val);
} else {
return searchNode(node->right, val);
}
}
// 查找最小值
Node* findMin(Node* node) {
while (node->left != nullptr) {
node = node->left;
}
return node;
}
};
```