二叉排序树（Binary Search Tree, BST）是一种重要的数据结构，其定义如下：
一棵二叉树若满足以下性质，则称为二叉排序树：
- 若左子树非空，则左子树上所有结点的值均小于根结点的值；
- 若右子树非空，则右子树上所有结点的值均大于根结点的值；
- 左、右子树本身也分别是二叉排序树。
这种结构使得中序遍历二叉排序树时，可以得到一个递增有序序列。
查找过程基于递归比较：
从根节点开始，将目标关键字与当前结点的关键字进行比较：
- 相等 → 查找成功；
- 目标值较小 → 在左子树中继续查找；
- 目标值较大 → 在右子树中继续查找；
- 若到达空指针，则表示查找失败。
存储结构通常采用二叉链表形式，C语言定义如下：
typedefstructTnode{intdata;// 结点关键字structTnode*lchild,*rchild;// 左、右孩子指针}BSTnode,*BSTree;查找算法实现示例（返回目标结点，并记录父结点）：
BSTnode*SearchBST(BSTree root,intkey,BSTnode*father,BSTnode**parent){if(root==NULL){*parent=father;returnNULL;// 查找失败}if(key==root->data){*parent=father;returnroot;// 查找成功}elseif(key<root->data){returnSearchBST(root->lchild,key,root,parent);// 向左查找}else{returnSearchBST(root->rchild,key,root,parent);// 向右查找}}二叉排序树支持高效的动态操作，插入新结点时总作为叶子插入正确位置。但最坏情况下（如按序插入），树可能退化为链表，导致时间复杂度升至 O(n)。为此，引申出平衡二叉树（AVL）、红黑树等改进结构。
- 二叉排序树的插入操作实现：
插入操作本质上是查找失败后在合适位置创建新结点。从根开始，比较待插关键字与当前结点值：
- 若小于当前结点值，进入左子树；
- 若大于，则进入右子树；
- 直到遇到空指针位置（即应插入的位置），分配内存并插入新结点。
C语言实现示例：
BSTnode*InsertBST(BSTree root,intkey){if(root==NULL){BSTnode*newNode=(BSTnode*)malloc(sizeof(BSTnode));newNode->data=key;newNode->lchild=newNode->rchild=NULL;returnnewNode;// 返回新结点作为子树根}if(key<root->data)root->lchild=InsertBST(root->lchild,key);// 插入左子树elseif(key>root->data)root->rchild=InsertBST(root->rchild,key);// 插入右子树// 若相等，不插入（避免重复）returnroot;}- 删除操作需考虑的三种情况：
删除一个结点时，必须保持二叉排序树的性质不变，分为以下三类：
- 叶子结点（无左右子树）：直接删除即可。
- 仅有左子树或右子树：用其子树替代其位置。
- 左右子树均存在：需找到中序前驱（左子树最大值）或中序后继（右子树最小值）来替换该结点，再递归删除替换结点。
中序遍历二叉排序树的结果：
中序遍历（左→根→右）会得到一个严格递增的有序序列。这是由二叉排序树的定义决定的，体现了其“排序”特性。极端情况下性能下降的原因：
当数据按有序或接近有序的方式插入时（如连续插入 1, 2, 3, 4, 5），二叉排序树会退化为单链（类似线性表）。此时树的高度为 n，查找、插入、删除的时间复杂度退化为 O(n)，失去了 O(log n) 的优势。平衡二叉树对二叉排序树的优化方式：
平衡二叉树（如 AVL 树）通过维护每个结点的平衡因子（左右子树高度差 ≤ 1）来防止树过度倾斜。每当插入或删除导致不平衡时，通过旋转操作（LL、RR、LR、RL 四种）调整结构，确保树高始终接近 log n，从而保证所有操作在 O(log n) 时间内完成。
