c++任意给定一组数据,设计一个算法,建立一棵二叉排序树,对它进行查找、插入、删除等操作
时间: 2024-02-29 17:51:56 浏览: 80
好的,下面是一个使用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;
}
// 查找操作
bool find(int val) {
TreeNode* cur = root;
while (cur) {
if (val == cur->val) {
return true;
} else if (val < cur->val) {
cur = cur->left;
} else {
cur = cur->right;
}
}
return false;
}
// 插入操作
void insert(int val) {
if (!root) {
root = new TreeNode(val);
return;
}
TreeNode* cur = root;
while (cur) {
if (val < cur->val) {
if (cur->left) {
cur = cur->left;
} else {
cur->left = new TreeNode(val);
break;
}
} else {
if (cur->right) {
cur = cur->right;
} else {
cur->right = new TreeNode(val);
break;
}
}
}
}
// 删除操作
void remove(int val) {
root = remove_helper(root, val);
}
private:
TreeNode* root;
// 递归删除操作
TreeNode* remove_helper(TreeNode* node, int val) {
if (!node) {
return NULL;
}
if (val < node->val) {
node->left = remove_helper(node->left, val);
} else if (val > node->val) {
node->right = remove_helper(node->right, val);
} else {
if (!node->left && !node->right) {
delete node;
node = NULL;
} else if (!node->left) {
TreeNode* temp = node;
node = node->right;
delete temp;
} else if (!node->right) {
TreeNode* temp = node;
node = node->left;
delete temp;
} else {
TreeNode* temp = node->right;
while (temp->left) {
temp = temp->left;
}
node->val = temp->val;
node->right = remove_helper(node->right, temp->val);
}
}
return node;
}
};
int main() {
BST bst;
bst.insert(5);
bst.insert(3);
bst.insert(1);
bst.insert(4);
bst.insert(7);
bst.insert(6);
bst.insert(8);
cout << bst.find(5) << endl;
cout << bst.find(2) << endl;
bst.remove(5);
cout << bst.find(5) << endl;
return 0;
}
```
在这个程序中,我们定义了一个二叉排序树的类BST,其中包含了查找、插入、删除操作。在查找操作中,我们从根节点开始遍历二叉排序树,并根据比较大小的结果不断向左或向右移动指针,直到找到目标值或者遍历到空节点为止。在插入操作中,我们从根节点开始遍历二叉排序树,并根据比较大小的结果不断向左或向右移动指针,直到找到空节点为止,然后在该位置上插入新节点。在删除操作中,我们首先找到要删除的节点,如果该节点没有子节点,则直接删除该节点;如果该节点只有一个子节点,则将该子节点替换为该节点;如果该节点有两个子节点,则找到该节点右子树中的最小值节点,将该节点的值替换为最小值节点的值,并递归删除该最小值节点。
这个程序的时间复杂度取决于二叉排序树的深度,最坏情况下,二叉排序树可能退化为链表,时间复杂度为O(n),其中n为节点数。如果二叉排序树比较平衡,则时间复杂度为O(log n)。
阅读全文