用C++编程实现读入一串字符创建一棵二叉排序树,然后分别实现:二叉排序树的查找;二叉排序树的插入;二叉排序树的删除等操作。
时间: 2023-12-05 15:40:52 浏览: 112
以下是C++实现读入一串字符创建一棵二叉排序树,并实现二叉排序树的查找、插入和删除操作的代码:
```cpp
#include <iostream>
using namespace std;
// 二叉排序树结点定义
struct BSTNode {
int data;
BSTNode* left;
BSTNode* right;
};
// 创建二叉排序树
void createBST(BSTNode*& root, int data) {
if (root == NULL) {
root = BSTNode;
root->data = data;
root->left = NULL;
root->right = NULL; }
else if (data < root->data) {
createBST(root->left, data);
}
else {
createBST(root->right, data);
}
}
// 查找二叉排序树
BSTNode* searchBST(BSTNode* root, int data) {
if (root == NULL || root->data == data) {
return root;
}
else if (data < root->data) {
return searchBST(root->left, data);
}
else {
return searchBST(root->right, data);
}
}
// 插入二叉排序树
void insertBST(BSTNode*& root, int data) {
if (root == NULL) {
root = new BSTNode;
root->data = data;
root->left = NULL;
root->right = NULL;
}
else if (data < root->data) {
insertBST(root->left, data);
}
else {
insertBST(root->right, data);
}
}
// 删除二叉排序树
void deleteBST(BSTNode*& root, int data) {
if (root == NULL) {
return;
}
if (data < root->data) {
deleteBST(root->left, data);
}
else if (data > root->data) {
deleteBST(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 = root->right;
while (temp->left != NULL) {
temp = temp->left;
}
root->data = temp->data;
deleteBST(root->right, temp->data);
}
}
}
int main() {
BSTNode* root = NULL;
int n, data;
cout << "请输入二叉排序树结点个数:";
cin >> n;
cout << "请输入" << n << "个结点的值:" << endl;
for (int i = 0; i < n; i++) {
cin >> data;
createBST(root, data);
}
// 测试查找操作
int searchData;
cout << "请输入要查找的结点值:";
cin >> searchData;
BSTNode* searchResult = searchBST(root, searchData);
if (searchResult == NULL) {
cout << "未找到该结点" << endl;
}
else {
cout << "已找到该结点" << endl;
}
// 测试插入操作
int insertData;
cout << "请输入要插入的结点值:";
cin >> insertData;
insertBST(root, insertData);
cout << "插入后的二叉排序树为:" << endl;
// 遍历二叉排序树
// ...
// 测试删除操作
int deleteData;
cout << "请输入要删除的结点值:";
cin >> deleteData;
deleteBST(root, deleteData);
cout << "删除后的二叉排序树为:" << endl;
// 遍历二叉排序树
// ...
return 0;
}
```
阅读全文