二叉搜索树算法：能否从非根节点开始执行查找操作？

完全没问题——二叉搜索树（BST）的查找逻辑核心是利用它的节点值排序性质，而不是必须从整棵树的根节点出发。只要你从任意一个节点开始，遵循BST的基本规则，就能在以该节点为根的子树范围内完成查找。

为什么可行？ #

BST的核心性质决定了这一点：

• 任意节点的左子树中，所有节点的值都小于该节点的值
• 任意节点的右子树中，所有节点的值都大于该节点的值
• 左右子树本身也都是合法的BST

这意味着，树中的每一个节点本身就是一棵子BST的根。所以从第三层的某个节点开始查找，本质上就是在这棵子BST里执行标准的BST查找，逻辑和从整棵树的根查找完全一致。

举个实际例子 #

假设我们有一棵BST，第三层有个节点值为10，它的左子树是值为8的节点，右子树是值为12的节点（12的右子树还有15）。现在我们从这个10节点开始查找15：

1. 15 > 10，所以转向它的右子树（节点12）
2. 15 > 12，再转向12的右子树（节点15）
3. 找到目标节点，返回结果

如果找的是7，那会走到8的左子树（不存在），最终返回“未找到”——这和从根节点查找的流程完全一样，只是范围被限定在了10的子树里。

代码实现示例 #

这里用Python写一个通用的、从任意起始节点开始的BST查找函数：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def search_from_node(start_node, target):
    current = start_node
    while current:
        if current.val == target:
            return current  # 找到目标节点
        elif target < current.val:
            current = current.left  # 去左子树找
        else:
            current = current.right  # 去右子树找
    return None  # 目标不在该子树中

注意事项 #

这种查找的范围仅限起始节点的子树，整棵树中不在这个子树范围内的节点是无法被找到的。比如起始节点是第三层的某个节点，它的父节点、父节点的另一子树里的节点，都不在查找范围内——这点一定要明确。

内容的提问来源于stack exchange，提问作者Greg