二叉搜索树
约 435 字大约 1 分钟
2026-03-22
性质
二叉搜索树:左子树 < 节点 < 右子树(注意,左子树所有节点都要小于根节点,而不仅仅是左节点)
核心知识:二叉搜索树的中序遍历序列是升序的。
查找节点
跟二分法类似,如果要查找的值比 curr 小,那么在左子树找,如果大,那么在右子树找
插入节点
从 root 节点开始, 一直循环查找,直到 curr 为 null 为止。
循环逻辑就是查找节点的逻辑。
注意在循环过程中要启临时变量 pre 来记录父节点,以便在循环结束后在父节点进行插入。
二叉搜索树不允许重复值,如果找到重复值直接返回。
删除节点
分三种情况讨论:
情况1:如果要删除的节点没有子节点,那么直接删除即可
parent.left= null ( 或 parent.right = null )情况2:如果要删除的节点只有一个子节点,那么将其子节点替换为它即可
parent.left = curr.left (或者 right)情况3:如果要删除的节点有两个子节点 ,则不可以直接删除,要让待删除节点的【左子树的最大节点】 或 【右子树的最小节点】 替换它,替换步骤如下:
- 查找要删除的节点
cur - 找到
cur在中序遍历的下一个节点nex(也就是它的右子树的最左叶子)
TreeNode nex = cur.right;
while (nex.left != null) {
tmp = tmp.left;
}- 用 nex 的值覆盖待删除节点的值,并在树中递归删除节点 nex
// 递归删除节点 nex
remove(nex .val);
// 用 nex 覆盖 cur
cur.val = nex .val;