前驱后继节点查找逻辑：二叉搜索树变量定位的高阶技巧

你在学习文章相关的知识吗？本文《前驱后继节点查找逻辑：二叉搜索树变量定位的高阶技巧》，主要介绍的内容就涉及到，如果你想提升自己的开发能力，就不要错过这篇文章，大家要知道编程理论基础和实战操作都是不可或缺的哦！

前驱是左子树最右节点或不存在，后继是右子树最左节点或不存在；删除度为2节点时，用其前驱或后继替换可保持BST性质，且被替换节点至多一个子节点，便于递归删除。

在二叉搜索树（BST）中，前驱节点指比当前节点小的最大节点，后继节点指比当前节点大的最小节点。它们不是凭空出现的，而是严格由BST的结构性质决定的——左子树全小于根、右子树全大于根、子树本身也是BST。掌握前驱/后继的定位逻辑，是实现正确删除（尤其是度为2节点）、K大/K小查询、迭代遍历等高阶操作的核心基础。

前驱节点怎么找

对任意非空节点 cur：

• 若 cur 有左子树，则前驱一定在左子树中，且是左子树的“最右节点”——即从 cur->_left 出发，一直向右走到底（while (node->_right)），最后停下的那个节点就是前驱
• 若 cur 没有左子树，则前驱不存在（或需向上回溯父节点链判断，但标准BST删除中通常不依赖此路径）

后继节点怎么找

对任意非空节点 cur：

• 若 cur 有右子树，则后继一定在右子树中，且是右子树的“最左节点”——即从 cur->_right 出发，一直向左走到底（while (node->_left)），最后停下的那个节点就是后继
• 若 cur 没有右子树，则后继不存在（同理，标准场景下不依赖向上查找）

为什么必须用前驱或后继来替换

删除一个左右子树都非空的节点时，不能简单删掉它，否则会断开树结构并破坏BST性质。可行方案是：

• 用它的前驱（左子树最大）替换它：该值天然满足「小于原节点所有右子树节点，大于原节点所有左子树节点」
• 或用它的后继（右子树最小）替换它：该值天然满足「大于原节点所有左子树节点，小于原节点所有右子树节点」
• 替换后，只需递归删除被拿去替换的那个前驱/后继节点——而这个节点必然至多只有一个孩子（最左或最右节点不可能同时有左右孩子），从而降级为简单删除情形

实际编码中的关键细节

写查找前驱/后继代码时容易忽略三点：

• 必须保存父节点指针：替换完成后，要将前驱/后继从原位置摘除，需要知道它挂在谁的左或右指针上（如 parent->_right = successor->_right）
• 区分“找得到”和“能安全删”：找到后继不等于能直接删；要检查该后继是否就是 cur->_right 本身——若是，则它没有左孩子，可直接用其右子树顶上
• 空树或单节点要单独判：比如根节点无右子树时调用后继查找，应直接返回空，避免空指针解引用

到这里，我们也就讲完了《前驱后继节点查找逻辑：二叉搜索树变量定位的高阶技巧》的内容了。个人认为，基础知识的学习和巩固，是为了更好的将其运用到项目中，欢迎关注golang学习网公众号，带你了解更多关于的知识点！