任意给定一组数据,设计一个算法,建立一棵二叉排序树,对它进行查找、插入、删除等操作。写出完整代码
时间: 2024-03-16 20:43:38 浏览: 70
好的,以下是二叉排序树的完整代码实现(使用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 {
private:
TreeNode* root;
public:
//构造函数
BST() {
root = NULL;
}
//向树中插入一个节点
void insert(int val) {
root = insertNode(root, val);
}
//删除树中的一个节点
void remove(int val) {
root = removeNode(root, val);
}
//查找树中是否存在某个节点
bool search(int val) {
return searchNode(root, val);
}
private:
//向树中插入一个节点(递归实现)
TreeNode* insertNode(TreeNode* node, int val) {
if (node == NULL) {
node = new TreeNode(val);
}
else if (val < node->val) {
node->left = insertNode(node->left, val);
}
else {
node->right = insertNode(node->right, val);
}
return node;
}
//删除树中的一个节点(递归实现)
TreeNode* removeNode(TreeNode* node, int val) {
if (node == NULL) {
return NULL;
}
if (val < node->val) {
node->left = removeNode(node->left, val);
}
else if (val > node->val) {
node->right = removeNode(node->right, val);
}
else {
if (node->left == NULL) {
TreeNode* temp = node->right;
delete node;
return temp;
}
else if (node->right == NULL) {
TreeNode* temp = node->left;
delete node;
return temp;
}
TreeNode* temp = findMin(node->right);
node->val = temp->val;
node->right = removeNode(node->right, temp->val);
}
return node;
}
//查找树中是否存在某个节点(递归实现)
bool searchNode(TreeNode* node, int val) {
if (node == NULL) {
return false;
}
if (node->val == val) {
return true;
}
else if (val < node->val) {
return searchNode(node->left, val);
}
else {
return searchNode(node->right, val);
}
}
//找到树中最小节点(非递归实现)
TreeNode* findMin(TreeNode* node) {
while (node->left != NULL) {
node = node->left;
}
return node;
}
};
int main() {
BST tree;
//插入节点
tree.insert(5);
tree.insert(2);
tree.insert(3);
tree.insert(8);
tree.insert(1);
tree.insert(7);
//查找节点
cout << tree.search(5) << endl; //1
cout << tree.search(6) << endl; //0
//删除节点
tree.remove(2);
cout << tree.search(2) << endl; //0
return 0;
}
```
以上代码实现了二叉排序树的基本操作,包括插入节点、删除节点、查找节点等。需要注意的是,二叉排序树的插入、删除、查找等操作都是递归实现的。
阅读全文