二叉搜索树详解：从原理到实战-育师

文章目录

一、什么是二叉搜索树（BST）？
二、BST 的基本操作
- 1. 节点定义
- 2. 查找操作
- 3. 插入操作
- 4. 删除操作
三、经典例题分析
- 例题 1：验证二叉搜索树（LeetCode 98）
- 例题 2：二叉搜索树的最近公共祖先（LeetCode 235）
四、C 语言实现注意事项与总结
- 1. 核心要点回顾
- 2. 避坑指南

一、什么是二叉搜索树（BST）？

核心定义
二叉搜索树是一种有序二叉树，满足以下性质：
- 左子树中所有节点的值 < 根节点的值
- 右子树中所有节点的值 > 根节点的值
- 左、右子树也必须是二叉搜索树
关键特性
- 中序遍历结果为升序序列
- 查找、插入、删除操作的时间复杂度：O (h)（h 为树的高度）

二、BST 的基本操作

1. 节点定义

C 语言中通过结构体定义树节点，需手动管理指针和内存：

#include<stdio.h>#include<stdlib.h>#include<stdbool.h>// 用于bool类型（C99及以上）// 二叉搜索树节点结构体typedefstructTreeNode{intval;structTreeNode*left;structTreeNode*right;}TreeNode;// 新建节点（封装内存分配）TreeNode*createNode(intval){TreeNode*node=(TreeNode*)malloc(sizeof(TreeNode));node->val=val;node->left=NULL;node->right=NULL;returnnode;}

2. 查找操作

思路：利用 BST 有序性迭代查找，避免递归栈开销：

// 查找指定值的节点，返回节点指针（未找到返回NULL）TreeNode*searchBST(TreeNode*root,intval){TreeNode*current=root;while(current!=NULL){if(val==current->val){returncurrent;// 找到目标节点}elseif(val<current->val){current=current->left;// 左子树查找}else{current=current->right;// 右子树查找}}returnNULL;// 未找到}

3. 插入操作

思路：递归找到空位置插入，需注意指针的地址传递：

// 插入节点（递归实现）TreeNode*insertIntoBST(TreeNode*root,intval){// 递归终止：空位置插入新节点if(root==NULL){returncreateNode(val);}// 左子树插入if(val<root->val){root->left=insertIntoBST(root->left,val);}// 右子树插入elseif(val>root->val){root->right=insertIntoBST(root->right,val);}// 重复值不处理（本文默认无重复）returnroot;}

4. 删除操作

思路：分 3 种情况处理：

// 找到以node为根的树的最小节点（用于删除操作）TreeNode*findMin(TreeNode*node){while(node->left!=NULL){node=node->left;}returnnode;}// 删除指定值的节点TreeNode*deleteNode(TreeNode*root,intkey){if(root==NULL){returnNULL;}// 1. 找到要删除的节点if(key<root->val){root->left=deleteNode(root->left,key);}elseif(key>root->val){root->right=deleteNode(root->right,key);}// 2. 找到目标节点，处理删除逻辑else{// 情况1：叶子节点/只有右子树if(root->left==NULL){TreeNode*temp=root->right;free(root);// 释放当前节点内存returntemp;}// 情况2：只有左子树elseif(root->right==NULL){TreeNode*temp=root->left;free(root);// 释放当前节点内存returntemp;}// 情况3：有两个子树（找右子树最小节点替代）TreeNode*minRight=findMin(root->right);root->val=minRight->val;// 替换值root->right=deleteNode(root->right,minRight->val);// 删除替代节点}returnroot;}// 辅助：销毁整棵树（避免内存泄漏）voiddestroyTree(TreeNode*root){if(root==NULL)return;destroyTree(root->left);destroyTree(root->right);free(root);}

三、经典例题分析

例题 1：验证二叉搜索树（LeetCode 98）

boolisValidBST(structTreeNode*root){// 定义栈数组，模拟递归栈（存储树节点指针），长度10000适配大部分测试用例structTreeNode*stack[10000];intstk_top=-1;// 栈顶指针，初始为-1表示栈空structTreeNode*cur=root;// 遍历指针，初始指向根节点intmax=-2147483648;// 记录中序遍历的前一个节点值，初始为int最小值（INT_MIN）intbegin=0;// 标记是否是第一个节点（处理根节点为INT_MIN的边界情况）// 迭代中序遍历核心循环：当前节点非空 或 栈非空时继续遍历while(cur!=NULL||stk_top>=0){// 内层循环：将当前节点的所有左子节点依次入栈（中序遍历先访问左子树）while(cur!=NULL){stack[++stk_top]=cur;// 节点入栈，栈顶指针上移cur=cur->left;// 继续遍历左子树}// 出栈：访问当前栈顶节点（中序遍历的"根"节点）cur=stack[stk_top--];// 栈顶节点出栈，栈顶指针下移// 核心验证：当前节点值需严格大于前一个节点值（max）if(cur->val<=max){// 特殊处理：仅当max是初始值（INT_MIN）且是第一个节点时，允许等于（避免误判根节点为INT_MIN的情况）// 若不是第一个节点 或 max已更新过，直接判定为无效BSTif(max!=-2147483648||begin!=0)returnfalse;begin++;// 标记第一个节点已处理}else{max=cur->val;// 更新max为当前节点值（作为下一个节点的比较基准）}cur=cur->right;// 遍历右子树（中序遍历：左→根→右）}// 所有节点遍历完成且满足升序，判定为有效BSTreturntrue;}

例题 2：二叉搜索树的最近公共祖先（LeetCode 235）

structTreeNode*lowestCommonAncestor(structTreeNode*root,structTreeNode*p,structTreeNode*q){// 递归终止条件：当前节点为空（遍历到叶子节点的子节点，无LCA）if(!root)returnNULL;// 核心判断：当前节点值在p和q的值之间（包含等于）→ 当前节点就是LCA// 两种情况：1. p≤root≤q 2. q≤root≤p（兼容p/q值大小不确定的情况）if((root->val>=p->val&&root->val<=q->val)||(root->val>=q->val&&root->val<=p->val))returnroot;// 递归查找左子树的LCAstructTreeNode*left=lowestCommonAncestor(root->left,p,q);// 递归查找右子树的LCAstructTreeNode*right=lowestCommonAncestor(root->right,p,q);// 左子树找到LCA → 返回左子树的结果if(left)returnleft;// 右子树找到LCA → 返回右子树的结果if(right)returnright;// 左右子树均未找到（理论上BST中p/q存在时不会走到这一步）returnNULL;}