问询：用链表实现Binary Search Tree（BST）与普通BST实现的差异及关系

API 探路者

2026-8-6

二叉搜索树（BST）与链表实现的疑问解答

核心概念区分

二叉搜索树（BST）是逻辑结构定义：它是一种基于节点的层级结构，核心规则是左子树所有节点值小于父节点，右子树所有节点值大于父节点。这个定义和具体用什么方式实现完全无关。
链表实现BST是物理实现方式：你提到的包含数据、左/右子节点的节点，本质就是链表节点的扩展——普通单链表节点只有一个next指针，而BST的链表节点有两个指针（左、右），用来指向子节点，以此构建树形结构。

你说的“实现BST”和“用链表实现BST”并非并列概念，而是逻辑定义与实现手段的关系。BST还可以用数组实现（比如完全二叉树常用数组存储），但链表是最常用的实现方式，因为它灵活，无需预先分配空间，适合动态增删节点。

结构上的扩展：BST的每个节点本质是多指针的链表节点。普通单链表是线性结构，每个节点只有一个后继；而BST的节点有两个“后继”（左、右子节点），把线性的链表结构扩展成了树形结构。
遍历的关联：BST的中序遍历会输出一个有序的线性序列，这和遍历有序链表的结果类似，但BST的优势在于查找、插入、删除操作的时间复杂度为O(logn)（平衡时），而普通链表的这些操作是O(n)。
代码对比（伪代码）：
普通单链表节点：
```
class ListNode {
    int val;
    ListNode next;
}
```
BST的链表实现节点：
```
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
}
```
不难看出，BST节点就是把单链表的next拆分成了left和right，用来维护树形的层级关系。