首先编程实现读入一串字符创建一棵二叉排序树,然后分别实现:二叉排序树的查找;二叉排序树的插入;二叉排序树的删除等操作。C++写
时间: 2023-11-28 09:45:36 浏览: 125
二叉排序树的基本操作-创建,查找,删除,插入(C++)
4星 · 用户满意度95%
以下是C++实现读入一串字符创建一棵二叉排序树,并实现二叉排序树的查找、插入、删除等操作的代码:
```cpp
#include <iostream>
using namespace std;
// 二叉排序树结点的定义
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
// 二叉排序树的查找
bool searchBST(TreeNode* root, int val) {
if (root == NULL) {
return false;
}
if (root->val == val) {
return true;
} else if (root->val > val) {
return searchBST(root->left, val);
} else {
return searchBST(root->right, val);
}
}
// 二叉排序树的插入
TreeNode* insertBST(TreeNode* root, int val) {
if (root == NULL) {
return new TreeNode(val);
}
if (root->val > val) {
root->left = insertBST(root->left, val);
} else {
root->right = insertBST(root->right, val);
}
return root;
}
// 二叉排序树的删除
TreeNode* deleteBST(TreeNode* root, int val) {
if (root == NULL) {
return NULL;
}
if (root->val == val) {
if (root->left == NULL) {
return root->right;
} else if (root->right == NULL) {
return root->left;
} else {
TreeNode* p = root->right;
while (p->left != NULL) {
p = p->left;
}
root->val = p->val;
root->right = deleteBST(root->right, p->val);
}
} else if (root->val > val) {
root->left = deleteBST(root->left, val);
} else {
root->right = deleteBST(root->right, val);
}
return root;
}
// 读入一串字符创建一棵二叉排序树
TreeNode* createBST() {
TreeNode* root = NULL;
int val;
while (cin >> val) {
root = insertBST(root, val);
}
return root;
}
int main() {
// 创建二叉排序树
TreeNode* root = createBST();
// 查找二叉排序树
int val1;
cout << "请输入要查找的值:";
cin >> val1;
if (searchBST(root, val1)) {
cout << "查找成功!" << endl;
} else {
cout << "查找失败!" << endl;
}
// 插入二叉排序树
int val2;
cout << "请输入要插入的值:";
cin >> val2;
root = insertBST(root, val2);
cout << "插入成功!" << endl;
// 删除二叉排序树
int val3;
cout << "请输入要删除的值:";
cin >> val3;
root = deleteBST(root, val3);
cout << "删除成功!" << endl;
return 0;
}
```
阅读全文