ChatGPT体验 AI绘画体验

二叉排序树是一种特殊的二叉树，满足以下条件： 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是二叉树的遍历操作，这里不再赘述。