二叉树 (BST) 可视化工具
动态演示二叉搜索树的插入、删除与各种遍历算法，计算机专业与算法面试复习神器。
深入理解二叉搜索树 (Binary Search Tree) 及其算法原理
二叉搜索树（BST）是计算机科学和数据结构中最重要、最基础的树形结构之一。它不仅仅是考试和面试中的高频考点，其底层思想更是被广泛应用于数据库索引、文件系统目录等实际工程中。
1. 二叉搜索树的核心性质
一个标准的二叉搜索树必须满足以下极其严格的规则：
- 左小右大： 任何一个节点的左子树上的所有节点的值，都必须 小于 该节点的值。
- 右大左小： 任何一个节点的右子树上的所有节点的值，都必须 大于 该节点的值。
- 递归性： 它的任意左子树和右子树也必然是二叉搜索树。
- 无重复节点： 标准的BST中通常不允许出现两个值相等的节点。
由于这个“左小右大”的特性，我们在BST中进行
查找、插入或删除
时，可以通过比较节点的大小，每次直接排除掉一半的子树。这使得BST的平均时间复杂度可以达到惊人的
O(log n)
。但在最坏情况下（例如你依次插入 10, 20, 30, 40,
50，树会退化成一条向右倾斜的链表），时间复杂度会退化为
O(n)
。你可以使用本页左侧的“退化右斜树”模板来观察这种现象。
2. 四大遍历方式的奥秘
遍历（Traversal）是指按照某种规则访问树中的每一个节点且仅访问一次。由于树是非线性结构，遍历路径不止一条。理解以下遍历方式是刷算法题（如 LeetCode）的基础：
-
前序遍历 (Pre-order)：
根节点 -> 左子树 -> 右子树。 常用于在重新构建一棵树或者复制树时。 -
中序遍历 (In-order)：
左子树 -> 根节点 -> 右子树。 在二叉搜索树中，中序遍历有一个超级特性： 遍历结果必然是一个递增的有序序列！ 如果你想把一棵树排序输出，用中序遍历就对了。 -
后序遍历 (Post-order)：
左子树 -> 右子树 -> 根节点。 常用于需要先处理完子节点再处理父节点的场景，例如删除整棵树，或者计算树中某个文件夹的总大小。 -
层序遍历 (Level-order)：
从上到下，从左到右。 也被称为广度优先搜索（BFS），常使用队列（Queue）来实现。
3. 节点的删除（难点）
在BST中插入和查找都很简单，但 删除 却是一个痛点，因为要保证删除后依然维持“左小右大”的特性。删除节点通常分为三种情况：
- 叶子节点： 该节点没有左右子树，直接删除即可。
- 只有一个子节点： 直接让它的父节点指向它的那个独生子节点。
- 有两个子节点： 这是最复杂的！你需要找到该节点右子树中的 最小值节点 （即右子树中最左侧的节点）或者左子树中的 最大值节点 ，用它来替换被删除节点的值，然后再把那个最小值/最大值节点删掉。
你可以利用本工具顶部的“删除”功能，亲自删除一个带有两个子节点的节点，观察树形结构发生的巧妙变化！