用c++编程实现读入一串字符创建一棵二叉排序树,然后分别实现:二叉排序树的查找;二叉排序树的插入;二叉排序树的删除等操作。
时间: 2023-10-16 10:31:23 浏览: 90
好的,下面是C++代码实现:
```c++
#include <iostream>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class BST {
public:
BST() {
root = NULL;
}
void insert(int val) {
root = insertHelper(root, val);
}
TreeNode* search(int val) {
return searchHelper(root, val);
}
void remove(int val) {
root = removeHelper(root, val);
}
private:
TreeNode* root;
TreeNode* insertHelper(TreeNode* node, int val) {
if (!node) {
return new TreeNode(val);
}
if (val < node->val) {
node->left = insertHelper(node->left, val);
} else if (val > node->val) {
node->right = insertHelper(node->right, val);
}
return node;
}
TreeNode* searchHelper(TreeNode* node, int val) {
if (!node || node->val == val) {
return node;
}
if (val < node->val) {
return searchHelper(node->left, val);
} else {
return searchHelper(node->right, val);
}
}
TreeNode* removeHelper(TreeNode* node, int val) {
if (!node) {
return NULL;
}
if (val < node->val) {
node->left = removeHelper(node->left, val);
} else if (val > node->val) {
node->right = removeHelper(node->right, val);
} else {
if (!node->left && !node->right) {
delete node;
return NULL;
} else if (!node->left) {
TreeNode* temp = node->right;
delete node;
return temp;
} else if (!node->right) {
TreeNode* temp = node->left;
delete node;
return temp;
} else {
TreeNode* temp = findMin(node->right);
node->val = temp->val;
node->right = removeHelper(node->right, temp->val);
}
}
return node;
}
TreeNode* findMin(TreeNode* node) {
while (node->left) {
node = node->left;
}
return node;
}
};
int main() {
BST* tree = new BST();
string s;
cout << "请输入一串数字,用空格分隔:" << endl;
getline(cin, s);
int start = 0;
for (int i = 0; i < s.size(); i++) {
if (s[i] == ' ') {
int num = stoi(s.substr(start, i - start));
tree->insert(num);
start = i + 1;
}
}
int num;
cout << "请输入要查找的数字:" << endl;
cin >> num;
TreeNode* res = tree->search(num);
if (res) {
cout << "数字 " << num << " 在树中" << endl;
} else {
cout << "数字 " << num << " 不在树中" << endl;
}
cout << "请输入要插入的数字:" << endl;
cin >> num;
tree->insert(num);
cout << "请输入要删除的数字:" << endl;
cin >> num;
tree->remove(num);
return 0;
}
```
以上代码实现了二叉排序树的插入、查找和删除操作。用户可以输入一串数字,程序自动创建一棵二叉排序树,然后用户可以输入要查找、插入、删除的数字。程序输出对应的结果。
阅读全文