怎么用c++写一个二叉搜索树
时间: 2023-08-10 17:05:22 浏览: 48
二叉搜索树是一种特殊的二叉树,它满足以下性质:
- 左子树上所有节点的值均小于它的根节点的值。
- 右子树上所有节点的值均大于它的根节点的值。
- 左右子树也分别为二叉搜索树。
下面是一个使用 C++ 实现的简单二叉搜索树:
```cpp
#include <iostream>
using namespace std;
struct Node {
int data;
Node* left;
Node* right;
Node(int value) {
data = value;
left = nullptr;
right = nullptr;
}
};
class BinarySearchTree {
private:
Node* root;
Node* insert(Node* node, int value) {
if (node == nullptr) {
node = new Node(value);
} else if (value < node->data) {
node->left = insert(node->left, value);
} else if (value > node->data) {
node->right = insert(node->right, value);
}
return node;
}
Node* search(Node* node, int value) {
if (node == nullptr || node->data == value) {
return node;
} else if (value < node->data) {
return search(node->left, value);
} else {
return search(node->right, value);
}
}
Node* remove(Node* node, int value) {
if (node == nullptr) {
return node;
} else if (value < node->data) {
node->left = remove(node->left, value);
} else if (value > node->data) {
node->right = remove(node->right, value);
} else {
if (node->left == nullptr && node->right == nullptr) {
delete node;
node = nullptr;
} else if (node->left == nullptr) {
Node* temp = node;
node = node->right;
delete temp;
} else if (node->right == nullptr) {
Node* temp = node;
node = node->left;
delete temp;
} else {
Node* minNode = findMin(node->right);
node->data = minNode->data;
node->right = remove(node->right, minNode->data);
}
}
return node;
}
Node* findMin(Node* node) {
while (node->left != nullptr) {
node = node->left;
}
return node;
}
public:
BinarySearchTree() {
root = nullptr;
}
void insert(int value) {
root = insert(root, value);
}
bool search(int value) {
return search(root, value) != nullptr;
}
void remove(int value) {
root = remove(root, value);
}
void print() {
printInorder(root);
}
private:
void printInorder(Node* node) {
if (node == nullptr) {
return;
}
printInorder(node->left);
cout << node->data << " ";
printInorder(node->right);
}
};
int main() {
BinarySearchTree bst;
bst.insert(5);
bst.insert(3);
bst.insert(7);
bst.insert(1);
bst.insert(4);
bst.insert(6);
bst.insert(8);
bst.print(); // 输出:1 3 4 5 6 7 8
bst.remove(3);
bst.print(); // 输出:1 4 5 6 7 8
return 0;
}
```
在这个实现中,我们使用了一个 `Node` 结构体来表示二叉搜索树中的节点,每个节点包含一个 `data` 字段表示节点的值,以及 `left` 和 `right` 指针分别指向左右子节点。
我们也定义了一个 `BinarySearchTree` 类来管理二叉搜索树。在这个类中,我们定义了一些私有方法来实现插入、查找和删除节点的功能,同时也定义了一些公有方法供外部使用。
在 `insert` 方法中,我们首先判断当前节点是否为空,如果是的话,我们就创建一个新节点并将它插入到这个位置。如果不为空,我们就根据节点的值与当前节点的值的大小关系,递归地向左或向右寻找插入的位置。
在 `search` 方法中,我们首先判断当前节点是否为空或者是否等于要查找的值。如果是的话,我们就返回这个节点。否则,我们就根据节点的值与要查找的值的大小关系,递归地向左或向右查找。
在 `remove` 方法中,我们首先判断当前节点是否为空,如果是的话,我们就直接返回这个节点。如果不为空,我们就根据节点的值与要删除的值的大小关系,递归地向左或向右查找要删除的节点。如果找到了要删除的节点,我们就需要考虑以下三种情况:
- 要删除的节点没有子节点。在这种情况下,我们直接删除这个节点并将它的父节点指向空指针。
- 要删除的节点只有一个子节点。在这种情况下,我们将要删除的节点的子节点替换到要删除的节点的位置上。
- 要删除的节点有两个子节点。在这种情况下,我们需要找到要删除节点右子树中的最小值节点,将它的值复制到要删除的节点中,并递归地删除这个最小值节点。
最后,我们定义了一个 `print` 方法来按照中序遍历的顺序输出二叉搜索树中所有节点的值。