任意给定一组数据,设计一个算法,建立一棵二叉排序树,对它进行查找、插入、删除等操作,给出C++代码
时间: 2023-10-27 08:05:52 浏览: 99
以下是二叉排序树的实现,包括查找、插入、删除操作的C++代码:
```c++
#include <iostream>
using namespace std;
//定义二叉排序树节点
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
//查找节点
TreeNode* search(TreeNode* root, int val) {
if (root == NULL || root->val == val) {
return root;
}
if (root->val < val) {
return search(root->right, val);
}
return search(root->left, val);
}
//插入节点
TreeNode* insert(TreeNode* root, int val) {
if (root == NULL) {
return new TreeNode(val);
}
if (val < root->val) {
root->left = insert(root->left, val);
} else {
root->right = insert(root->right, val);
}
return root;
}
//删除节点
TreeNode* deleteNode(TreeNode* root, int val) {
if (root == NULL) {
return root;
}
if (val < root->val) {
root->left = deleteNode(root->left, val);
} else if (val > root->val) {
root->right = deleteNode(root->right, val);
} else {
//找到了要删除的节点
if (root->left == NULL) {
TreeNode* temp = root->right;
delete root;
return temp;
} else if (root->right == NULL) {
TreeNode* temp = root->left;
delete root;
return temp;
}
//如果左右子树都不为空,则找到右子树中最小的节点
TreeNode* temp = root->right;
while (temp->left != NULL) {
temp = temp->left;
}
root->val = temp->val;
root->right = deleteNode(root->right, temp->val);
}
return root;
}
int main() {
TreeNode* root = NULL;
root = insert(root, 5);
root = insert(root, 3);
root = insert(root, 7);
root = insert(root, 2);
root = insert(root, 4);
root = insert(root, 6);
root = insert(root, 8);
TreeNode* node = search(root, 3);
if (node != NULL) {
cout << "Found node: " << node->val << endl;
}
root = deleteNode(root, 5);
node = search(root, 5);
if (node == NULL) {
cout << "Node 5 not found" << endl;
}
return 0;
}
```
以上代码中,我们使用了递归的方式实现了查找、插入、删除操作。对于删除操作,如果要删除的节点有两个子节点,我们先找到右子树中最小的节点,将其值赋给要删除的节点,然后再递归删除这个最小的节点。
阅读全文