利用C++,不用类函数编程实现实现一棵二叉排序树,包括插入、删除、查找等功能;
时间: 2023-06-25 19:05:50 浏览: 45
以下是基于指针的二叉排序树的实现,其中包括插入、删除、查找等功能的实现。
```cpp
#include <iostream>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}
};
// insert a new value into the binary search tree
void insert(TreeNode*& root, int val) {
if (root == nullptr) {
root = new TreeNode(val);
return;
}
if (val < root->val) {
insert(root->left, val);
} else if (val > root->val) {
insert(root->right, val);
}
}
// delete a value from the binary search tree
void del(TreeNode*& root, int val) {
if (root == nullptr) {
return;
}
if (val < root->val) {
del(root->left, val);
} else if (val > root->val) {
del(root->right, val);
} else {
if (root->left == nullptr) {
TreeNode* tmp = root->right;
delete root;
root = tmp;
} else if (root->right == nullptr) {
TreeNode* tmp = root->left;
delete root;
root = tmp;
} else {
TreeNode* cur = root->right;
while (cur->left != nullptr) {
cur = cur->left;
}
root->val = cur->val;
del(root->right, cur->val);
}
}
}
// search for a value in the binary search tree
bool search(TreeNode* root, int val) {
if (root == nullptr) {
return false;
}
if (val == root->val) {
return true;
} else if (val < root->val) {
return search(root->left, val);
} else {
return search(root->right, val);
}
}
// print the binary search tree in inorder traversal
void inorder(TreeNode* root) {
if (root == nullptr) {
return;
}
inorder(root->left);
cout << root->val << " ";
inorder(root->right);
}
int main() {
TreeNode* root = nullptr;
insert(root, 5);
insert(root, 3);
insert(root, 7);
insert(root, 1);
insert(root, 4);
insert(root, 6);
insert(root, 8);
inorder(root);
cout << endl;
del(root, 5);
inorder(root);
cout << endl;
cout << search(root, 3) << endl;
cout << search(root, 5) << endl;
return 0;
}
```
上述代码中,我们使用了指针来实现二叉排序树。其中,insert()函数用于向二叉树中插入新节点,del()函数用于删除节点,search()函数用于在二叉树中查找指定的值。最后,我们通过inorder()函数按照中序遍历的方式输出二叉排序树中的所有节点。