ChatGPT体验 AI绘画体验
二叉排序树的原理讲解及其C++代码
提问人：ppw_crxis 时间：2023-04-22 公开状态：
提问人：ppw_crxis 时间：2023-04-22 公开状态：
二叉排序树是一种特殊的二叉树，满足以下条件：
1. 对于每个节点，左子树上的所有节点的值都小于它的值，右子树上的所有节点的值都大于它的值；
2. 左右子树都是二叉排序树。
因此，二叉排序树的节点的值可以是任意的可比较类型，比如整数、浮点数、字符串等。
二叉排序树的搜索操作是非常高效的，搜索一个节点的时间复杂度与树的高度有关，最坏情况下是O(n)，但是平均情况下可以达到O(logn)。
下面给出二叉排序树的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 search(int val) {
TreeNode* cur = root;
while (cur) {
if (cur->val == val) {
return true;
} else if (cur->val > 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 (cur->val > val) {
if (!cur->left) {
cur->left = new TreeNode(val);
break;
}
cur = cur->left;
} else {
if (!cur->right) {
cur->right = new TreeNode(val);
break;
}
cur = cur->right;
}
}
}
void remove(int val) {
root = removeHelper(root, val);
}
private:
TreeNode* root;
TreeNode* removeHelper(TreeNode* node, int val) {
if (!node) {
return NULL;
}
if (node->val > val) {
node->left = removeHelper(node->left, val);
} else if (node->val < val) {
node->right = removeHelper(node->right, val);
} else {
if (!node->left) {
TreeNode* rightNode = node->right;
delete node;
return rightNode;
}
if (!node->right) {
TreeNode* leftNode = node->left;
delete node;
return leftNode;
}
TreeNode* p = node->right;
while (p->left) {
p = p->left;
}
node->val = p->val;
node->right = removeHelper(node->right, p->val);
}
return node;
}
};
int main() {
BST bst;
bst.insert(8);
bst.insert(3);
bst.insert(6);
bst.insert(10);
bst.insert(1);
bst.insert(14);
cout << "Tree traversal: " << endl;
cout << "In-order: ";
inorderTraversal(bst.root);
cout << endl;
cout << "Pre-order: ";
preorderTraversal(bst.root);
cout << endl;
cout << "Post-order: ";
postorderTraversal(bst.root);
cout << endl;
bst.remove(3);
cout << "Tree after removing 3: " << endl;
inorderTraversal(bst.root);
cout << endl;
return 0;
}
```
注：inorderTraversal、preorderTraversal、postorderTraversal是二叉树的遍历操作，这里不再赘述。