二分搜索树深度优先遍历（手把手讲解）

💡一则或许对你有用的小广告

欢迎加入小哈的星球 ，你将获得：专属的项目实战 / 1v1 提问 / Java 学习路线 / 学习打卡 / 每月赠书 / 社群讨论

• 新项目:《从零手撸：仿小红书（微服务架构）》 正在持续爆肝中，基于 Spring Cloud Alibaba + Spring Boot 3.x + JDK 17...，点击查看项目介绍 ;
• 《从零手撸：前后端分离博客项目（全栈开发）》 2 期已完结，演示链接： http://116.62.199.48/ ;

截止目前， 星球 内专栏累计输出 82w+ 字，讲解图 3441+ 张，还在持续爆肝中.. 后续还会上新更多项目，目标是将 Java 领域典型的项目都整一波，如秒杀系统, 在线商城, IM 即时通讯，权限管理，Spring Cloud Alibaba 微服务等等，已有 2900+ 小伙伴加入学习 ，欢迎点击围观

前言

在数据结构与算法的学习中，二分搜索树（Binary Search Tree, BST）因其高效的搜索、插入和删除特性，成为编程中常见的工具。而深度优先遍历（Depth-First Search, DFS）作为 BST 的核心操作之一，能够帮助开发者系统性地访问树中所有节点。本文将通过循序渐进的方式，结合生动的比喻和代码示例，深入解析二分搜索树的深度优先遍历方法。无论是编程初学者还是希望巩固基础知识的中级开发者，都能在本文中找到适合自己的知识切入点。

二分搜索树的基础概念

什么是二分搜索树？

二分搜索树是一种特殊的二叉树结构，其核心特性是：

• 每个节点的左子树中所有节点的值均小于该节点的值；
• 每个节点的右子树中所有节点的值均大于该节点的值。

这一特性使得 BST 在搜索、插入和删除操作时，能够通过路径的快速收敛，将时间复杂度控制在接近 O(log N) 的水平。

形象比喻：BST 是一座“智能迷宫”

想象一座迷宫，每个岔路口都有明确的指引：向左走遇到的数字都会比当前值小，向右则更大。这样的迷宫结构让探索者能通过有限的路径快速找到目标节点，这正是 BST 的精髓所在。

树结构的遍历需求

遍历（Traversal）是指按照特定规则访问树中每个节点的过程。在 BST 中，遍历不仅是展示数据的方式，更是实现其他复杂操作（如查找最小值、合并树等）的基础。

深度优先遍历的核心思想

深度优先遍历（DFS）的核心策略是：优先深入探索当前节点的子树分支，直到触达叶子节点后回溯。这种“一条路走到黑”的策略，通过递归或栈结构实现。

三种经典的 DFS 遍历方式

1. 前序遍历（Pre-order）：访问当前节点 → 遍历左子树 → 遍历右子树
2. 中序遍历（In-order）：遍历左子树 → 访问当前节点 → 遍历右子树
3. 后序遍历（Post-order）：遍历左子树 → 遍历右子树 → 访问当前节点

形象比喻：旅行中的不同路线选择

• 前序遍历：像旅行者先在起点拍照，再依次探索左路和右路；
• 中序遍历：像先探索左路，到达终点后返回起点拍照，再探索右路；
• 后序遍历：像彻底探索完所有分支后，最后才返回起点记录。

实现二分搜索树深度优先遍历的代码示例

以下以 Python 语言为例，逐步展示 BST 的构建和三种 DFS 遍历的实现：

步骤 1：构建二分搜索树

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

class BST:  
    def __init__(self):  
        self.root = None  

    def insert(self, value):  
        if not self.root:  
            self.root = TreeNode(value)  
        else:  
            self._insert_recursive(self.root, value)  

    def _insert_recursive(self, current_node, value):  
        if value < current_node.value:  
            if current_node.left is None:  
                current_node.left = TreeNode(value)  
            else:  
                self._insert_recursive(current_node.left, value)  
        else:  
            if current_node.right is None:  
                current_node.right = TreeNode(value)  
            else:  
                self._insert_recursive(current_node.right, value)  

步骤 2：实现三种 DFS 遍历

    def pre_order_traversal(self):  
        return self._pre_order(self.root, [])  

    def _pre_order(self, node, result):  
        if node:  
            result.append(node.value)  
            self._pre_order(node.left, result)  
            self._pre_order(node.right, result)  
        return result  

    def in_order_traversal(self):  
        return self._in_order(self.root, [])  

    def _in_order(self, node, result):  
        if node:  
            self._in_order(node.left, result)  
            result.append(node.value)  
            self._in_order(node.right, result)  
        return result  

    def post_order_traversal(self):  
        return self._post_order(self.root, [])  

    def _post_order(self, node, result):  
        if node:  
            self._post_order(node.left, result)  
            self._post_order(node.right, result)  
            result.append(node.value)  
        return result  

示例运行与输出

bst = BST()  
values = [10, 5, 15, 3, 7, 12, 18]  
for val in values:  
    bst.insert(val)  

print("前序遍历:", bst.pre_order_traversal())  # 输出: [10, 5, 3, 7, 15, 12, 18]  
print("中序遍历:", bst.in_order_traversal())   # 输出: [3, 5, 7, 10, 12, 15, 18]  
print("后序遍历:", bst.post_order_traversal()) # 输出: [3, 7, 5, 12, 18, 15, 10]  

深度优先遍历的复杂度分析

时间复杂度

• 最优/平均情况：O(N)，其中 N 是树中的节点总数。
• 最坏情况：当树退化为链表时（例如所有节点仅存在左子树或右子树），时间复杂度仍为 O(N)，但实际效率会显著降低。

空间复杂度

• 递归实现：O(H)，H 是树的高度。最坏情况下 H = N（链表结构），导致栈溢出风险。
• 迭代实现：通过栈结构手动模拟递归，空间复杂度与递归版本相同。

深度优先遍历的实际应用场景

场景 1：计算树的高度

def get_tree_height(node):  
    if node is None:  
        return 0  
    return 1 + max(get_tree_height(node.left), get_tree_height(node.right))  

通过递归的后序遍历逻辑，可高效计算树的高度。

场景 2：验证二分搜索树的有效性

def is_valid_bst(node, left=float('-inf'), right=float('inf')):  
    if not node:  
        return True  
    if not (left < node.value < right):  
        return False  
    return (is_valid_bst(node.left, left, node.value) and  
            is_valid_bst(node.right, node.value, right))  

通过中序遍历的特性（BST 的中序遍历结果应为升序序列），可进一步优化验证逻辑。

场景 3：序列化与反序列化

def serialize(node):  
    if not node:  
        return '#,'  
    return f"{node.value}," + serialize(node.left) + serialize(node.right)  

通过前序遍历的序列化结果，可唯一确定一棵 BST 的结构。

常见问题与调试技巧

问题 1：递归导致栈溢出

当树的高度极大时，递归可能导致栈溢出。解决方案包括：

1. 改用迭代实现：通过栈结构手动管理遍历路径；
2. 平衡树结构：例如使用 AVL 树或红黑树，将树高控制在 O(log N) 级别。

问题 2：遍历顺序不符合预期

可能原因包括：

• 节点插入逻辑错误：导致 BST 的结构不符合预期；
• 遍历代码顺序写反：例如混淆了前序和后序的访问顺序。

调试技巧

• 打印遍历路径：在访问节点时输出其值，观察执行流程；
• 可视化工具：使用在线 BST 可视化网站（如 VisuAlgo）辅助理解遍历过程。

结论

二分搜索树的深度优先遍历不仅是数据结构的基础操作，更是算法设计中的重要工具。通过本文的讲解，读者可以掌握：

1. BST 的核心特性与构建方法；
2. 三种 DFS 遍历的实现逻辑及代码示例；
3. 实际应用场景与问题调试技巧。

无论是优化现有代码性能，还是解决 LeetCode 等平台上的算法题，理解二分搜索树深度优先遍历的底层原理，将帮助开发者在编程道路上走得更稳、更远。