C++首先编程实现读入一串字符创建一棵二叉排序树,然后分别实现:二叉排序树的查找;二叉排序树的插入;二叉排序树的删除等操作。
时间: 2023-11-28 21:45:36 浏览: 136
以下是C++实现读入一串字符创建一棵二叉排序树,并实现二叉排序树的查找、插入和删除操作的代码:
```c++
#include <iostream>
using namespace std;
// 二叉排序树结点定义
struct BSTNode {
int data;
BSTNode* left; BSTNode* right;
};
// 创建二叉排序树
void createBST(BSTNode*& root, int data) {
if (root == NULL) {
root = new 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);
}
cout << "请输入要查找的结点值:";
cin >> data;
BSTNode* searchResult = searchBST(root, data);
if (searchResult == NULL) {
cout << "未找到该结点" << endl;
}
else {
cout << "已找到该结点" << endl;
}
cout << "请输入要插入的结点值:";
cin >> data;
insertBST(root, data);
cout << "请输入要删除的结点值:";
cin >> data;
deleteBST(root, data);
return 0;
}
```
阅读全文