当前位置：首页 > news >正文

数据结构学习之路(八)----二叉搜索树（BST）：从原理到代码实现

news 2026/7/13 3:13:33

一、什么是二叉搜索树

二叉搜索树（Binary Search Tree，BST），也叫二叉排序树或二叉查找树，是在普通二叉树的基础上增加了有序性约束的一种数据结构。

它的核心规则很简单：

若左子树不空，则左子树上所有结点的值均小于根结点的值
若右子树不空，则右子树上所有结点的值均大于根结点的值
左右子树同样满足上述规则

这个递归定义保证了整棵树的中序遍历结果是一个从小到大排好序的序列，这也是二叉搜索树名字中“搜索”二字的由来。

二、为什么需要二叉搜索树

二叉搜索树最大的优势在于查找效率。我们可以在不进行中序遍历生成有序数组的情况下，直接利用树的结构进行查找。

查找的逻辑非常直观：从根节点开始，如果目标值等于当前节点值就找到了；如果小于当前节点值就去左子树找；如果大于就去右子树找。这个过程可以递归实现，也可以非递归实现。

但二叉搜索树并非完美无缺。它的查找效率取决于树的高度。在极端情况下，如果插入的数据本身是有序的（比如 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，根节点置为 NULL：

BSTree* 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; }