首先C++语言编程实现读入一串字符创建一棵二叉排序树,然后分别实现:二叉排序树的查找;二叉排序树的插入;二叉排序树的删除等操作。
时间: 2023-10-13 21:24:14 浏览: 132
数据结构实验:判断一棵二叉树是否是二叉排序树
好的,下面是C++代码实现。
```cpp
#include <iostream>
using namespace std;
// 二叉排序树的结点
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
// 二叉排序树的插入
void insert(TreeNode*& root, int val) {
if (!root) {
root = new TreeNode(val);
return;
}
if (root->val > val) {
insert(root->left, val);
} else {
insert(root->right, val);
}
}
// 二叉排序树的查找
bool search(TreeNode* root, int val) {
if (!root) {
return false;
}
if (root->val == val) {
return true;
}
if (root->val > val) {
return search(root->left, val);
} else {
return search(root->right, val);
}
}
// 二叉排序树的删除
void remove(TreeNode*& root, int val) {
if (!root) {
return;
}
if (root->val == val) {
if (!root->left && !root->right) {
delete root;
root = nullptr;
} else if (!root->left || !root->right) {
TreeNode* temp = root;
root = root->left ? root->left : root->right;
delete temp;
} else {
TreeNode* temp = root->right;
while (temp->left) {
temp = temp->left;
}
root->val = temp->val;
remove(root->right, temp->val);
}
} else if (root->val > val) {
remove(root->left, val);
} else {
remove(root->right, val);
}
}
// 中序遍历二叉排序树
void inorder(TreeNode* root) {
if (!root) {
return;
}
inorder(root->left);
cout << root->val << " ";
inorder(root->right);
}
int main() {
TreeNode* root = nullptr;
string str;
cout << "请输入一串数字,用空格分隔:";
getline(cin, str);
int val;
for (int i = 0; i < str.size(); i++) {
if (str[i] >= '0' && str[i] <= '9') {
val = val * 10 + (str[i] - '0');
} else {
insert(root, val);
val = 0;
}
}
insert(root, val);
cout << "中序遍历二叉排序树:" << endl;
inorder(root);
cout << endl;
cout << "请输入要查找的数字:";
cin >> val;
if (search(root, val)) {
cout << val << " 存在于二叉排序树中" << endl;
} else {
cout << val << " 不存在于二叉排序树中" << endl;
}
cout << "请输入要删除的数字:";
cin >> val;
remove(root, val);
cout << "中序遍历二叉排序树:" << endl;
inorder(root);
cout << endl;
return 0;
}
```
输入一串数字,用空格分隔,程序会根据这些数字创建一棵二叉排序树,然后进行中序遍历。接着提示输入要查找的数字和要删除的数字,程序会分别在二叉排序树中进行查找和删除,并且输出删除后的中序遍历结果。
阅读全文