一、什么是二叉搜索树二叉搜索树Binary Search TreeBST也叫二叉排序树或二叉查找树是在普通二叉树的基础上增加了有序性约束的一种数据结构。它的核心规则很简单若左子树不空则左子树上所有结点的值均小于根结点的值若右子树不空则右子树上所有结点的值均大于根结点的值左右子树同样满足上述规则这个递归定义保证了整棵树的中序遍历结果是一个从小到大排好序的序列这也是二叉搜索树名字中“搜索”二字的由来。二、为什么需要二叉搜索树二叉搜索树最大的优势在于查找效率。我们可以在不进行中序遍历生成有序数组的情况下直接利用树的结构进行查找。查找的逻辑非常直观从根节点开始如果目标值等于当前节点值就找到了如果小于当前节点值就去左子树找如果大于就去右子树找。这个过程可以递归实现也可以非递归实现。但二叉搜索树并非完美无缺。它的查找效率取决于树的高度。在极端情况下如果插入的数据本身是有序的比如 1,2,3,4,5,6构造出的二叉搜索树会退化成单链表查找效率从 O(log n) 降为 O(n)。这也正是后面要讲的平衡二叉树AVL 树要解决的问题。三、二叉搜索树的代码实现下面我们结合完整的 C 语言代码来逐一讲解 BST 的核心操作。3.1 节点与树的结构定义typedef struct BS_Node { Element_t data; // 节点存储的数据 struct BS_Node* left; // 左子树指针 struct BS_Node* right; // 右子树指针 } BS_Node; typedef struct BSTree { int count; // 树中节点总数 BS_Node* root; // 根节点指针 } BSTree;3.2 创建树创建一棵空树初始化计数器为 0根节点置为 NULLBSTree* createBSTree() { BSTree* tree malloc(sizeof(BSTree)); if (tree NULL) { return NULL; } tree-count 0; tree-root NULL; return tree; }3.3 插入操作插入操作的核心思想是新节点一定插入在叶子节点的位置。static BS_Node* createBSNode(Element_t e) { BS_Node* node malloc(sizeof(BS_Node)); if (node NULL) { printf(malloc node failed!\n); return NULL; } node-data e; node-left node-right NULL; return node; } static BSTree* insertBSNodeRecur(BSTree* tree, BS_Node* node, Element_t e) { if (node NULL) { tree-count; return createBSNode(e); } if (e node-data) { node-left insertBSNodeRecur(tree, node-left, e); } else if (e node-data) { node-right insertBSNodeRecur(tree, node-right, e); } return node; } void insertBSTreeRecur(BSTree* tree, Element_t e) { if (tree) { tree-root insertBSNodeRecur(tree, tree-root, e); } }如果当前节点为空就在此创建新节点否则根据值的大小决定去左子树还是右子树继续递归。3.4 中序遍历中序遍历左-根-右会输出一个有序序列这是验证 BST 正确性的常用方法static void visitedBSTree(BS_Node* node) { if (node) { printf(%d , node-data); } } static void inOrderBSNode(BS_Node* node) { if (node) { inOrderBSNode(node-left); visitedBSTree(node); inOrderBSNode(node-right); } } void inOrderBSTree(BSTree* tree) { if (tree) { inOrderBSNode(tree-root); } }3.5 查找最值根据 BST 的性质最小值一定在树的最左节点一直往左走到底最大值一定在树的最右节点一直往右走到底static BS_Node* minElement(BS_Node* node) { while (node node-left) { node node-left; } return node; }3.6 删除操作删除是 BST 中最复杂的操作需要分三种情况处理情况一删除叶子节点— 直接删除即可不影响其他节点的排列规则。情况二删除度为 1 的节点— 该节点缺失左子树或右子树删除后让它的子节点直接接替它的位置。情况三删除度为 2 的节点— 需要找到该节点的前驱左子树中的最大值或后继右子树中的最小值来替换它然后删除那个前驱/后继节点。代码实现如下static BS_Node* deleteBSNode(BSTree* tree, BS_Node* node, Element_t e) { if (node NULL) { return NULL; } if (e node-data) { node-left deleteBSNode(tree, node-left, e); } else if (e node-data) { node-right deleteBSNode(tree, node-right, e); } else { BS_Node* tmp NULL; // 度为0叶子节点或度为1只有右子树 if (node-left NULL) { tmp node-right; free(node); tree-count--; return tmp; } // 度为1只有左子树 if (node-right NULL) { tmp node-left; free(node); tree-count--; return tmp; } // 度为2找后继节点右子树中的最小值来替换 tmp minElement(node-right); node-data tmp-data; node-right deleteBSNode(tree, node-right, tmp-data); } return node; } void deleteBSTree(BSTree* tree, Element_t e) { if (tree) { tree-root deleteBSNode(tree, tree-root, e); } }注意原代码中处理度为 2 的节点时node-left NULL和node-right NULL的判断顺序有先后——先判断左子树为空此时无论右子树是否为空都用右子树接替再判断右子树为空。3.7 计算树的高度树的高度决定了搜索效率的上限int heightBSTree(BS_Node* node) { if (node NULL) { return 0; } int leftHeight heightBSTree(node-left); int rightHeight heightBSTree(node-right); if (leftHeight rightHeight) { return leftHeight; } else { return rightHeight; } }3.8 完整测试void test01() { Element_t data[] { 50, 33, 25, 7, 91, 21, 35, 28, 55 }; BSTree* tree createBSTree(); if (tree NULL) { return; } for (int i 0; i sizeof(data) / sizeof(data[0]); i) { insertBSTreeRecur(tree, data[i]); } printf(中序遍历结果: ); inOrderBSTree(tree); printf(\ntree height: %d\n, heightBSTree(tree-root)); deleteBSTree(tree, 21); printf(删除21后: ); inOrderBSTree(tree); } int main() { test01(); return 0; }四、总结二叉搜索树通过有序性约束将查找、插入、删除的平均时间复杂度降到了 O(log n)。它的核心操作——查找、插入、删除——都可以用递归优雅地实现。不过正如前面提到的BST 在面对有序数据时会退化成链表。为了应对这种情况计算机科学家们发明了平衡二叉树AVL 树通过引入平衡因子左子树高度与右子树高度之差的概念确保任意节点的平衡因子不超过 1从而保证树的高度始终维持在 O(log n) 级别。