二叉树入门：遍历、递归与层序搜索

摘要二叉树是树形数据结构的基础模型搜索树、堆、语法树和文件目录等结构都可以从树的思想延伸出来。二叉树的核心学习内容包括节点、左右子树、递归遍历和层序遍历。本文从二叉树的基本概念开始介绍前序、中序、后序和层序遍历并使用 Python 实现树节点、递归遍历、迭代遍历、最大深度和层序搜索为后续学习二叉搜索树、堆和图打下基础。一、背景与问题数组和链表适合表达线性关系但很多数据天然具有层级结构文件夹和文件。组织架构。商品分类。HTML 文档结构。编译器语法树。评论回复关系。如果把层级数据强行放入一个线性列表查询父子关系需要额外维护索引。树结构通过节点之间的连接直接表达层级。A / \ B C / \ \ D E F二叉树规定每个节点最多有两个子节点通常称为左子节点和右子节点。二、核心概念1. 节点和边树由节点和边组成根节点树的起点。子节点由其他节点连接而来的下层节点。父节点直接连接上层的节点。叶子节点没有子节点的节点。边连接两个节点的关系。2. 深度和高度节点深度从根节点到该节点经过的边数。树的高度从根节点到最深叶子节点的最大深度。层深度相同的节点集合。这些概念用于分析树的查找、遍历和空间消耗。3. 二叉树的形态类型特征满二叉树每个非叶子节点都有两个子节点完全二叉树除最后一层外都填满最后一层从左到右排列平衡二叉树左右子树高度差保持在较小范围退化树结构接近链表同样数量的节点不同形态会产生不同的查询性能。4. 遍历顺序树的遍历是访问所有节点的过程前序根、左、右。中序左、根、右。后序左、右、根。层序按层从上到下访问。三、工作原理1. 深度优先遍历前序、中序和后序都属于深度优先遍历。它们通常使用递归或显式栈实现。前序先处理当前节点再处理子树 中序先处理左子树再处理当前节点 后序先处理子树最后处理当前节点递归写法简洁但本质上仍然依赖调用栈保存待处理的子树。2. 广度优先遍历层序遍历使用队列访问根节点 → 把根的子节点加入队列 → 取出队首节点 → 加入其子节点 → 重复直到队列为空广度优先适合查找距离根节点最近的目标或者按层处理数据。3. 遍历复杂度设树中有n个节点时间复杂度O(n)每个节点访问一次。递归空间O(h)h为树高。层序队列空间最坏情况下为O(n)。平衡树的高度接近log n退化树的高度可能接近n。四、实战示例1. 定义节点from__future__importannotationsfromdataclassesimportdataclassdataclassclassTreeNode:value:intleft:TreeNode|NoneNoneright:TreeNode|NoneNone2. 构造示例树rootTreeNode(1,leftTreeNode(2,leftTreeNode(4),rightTreeNode(5),),rightTreeNode(3,rightTreeNode(6),),)3. 前序遍历defpreorder(root:TreeNode|None)-list[int]:ifrootisNone:return[]return[root.value,*preorder(root.left),*preorder(root.right),]print(preorder(root))前序结果为[1, 2, 4, 5, 3, 6]。4. 中序遍历definorder(root:TreeNode|None)-list[int]:ifrootisNone:return[]return[*inorder(root.left),root.value,*inorder(root.right),]如果二叉树满足二叉搜索树性质中序遍历会得到有序序列。5. 后序遍历defpostorder(root:TreeNode|None)-list[int]:ifrootisNone:return[]return[*postorder(root.left),*postorder(root.right),root.value,]后序遍历适合先处理子树、再处理父节点的场景例如计算目录大小或删除树结构。6. 迭代前序遍历defpreorder_iterative(root:TreeNode|None)-list[int]:ifrootisNone:return[]result:list[int][]stack[root]whilestack:nodestack.pop()result.append(node.value)ifnode.rightisnotNone:stack.append(node.right)ifnode.leftisnotNone:stack.append(node.left)returnresult栈后进先出因此先压入右子节点再压入左子节点才能先处理左子树。7. 层序遍历fromcollectionsimportdequedeflevel_order(root:TreeNode|None)-list[list[int]]:ifrootisNone:return[]result:list[list[int]][]queuedeque([root])whilequeue:level_values:list[int][]for_inrange(len(queue)):nodequeue.popleft()level_values.append(node.value)ifnode.leftisnotNone:queue.append(node.left)ifnode.rightisnotNone:queue.append(node.right)result.append(level_values)returnresult结果为[[1], [2, 3], [4, 5, 6]]。8. 计算树的最大深度defmax_depth(root:TreeNode|None)-int:ifrootisNone:return0return1max(max_depth(root.left),max_depth(root.right),)递归定义直接表达了树高当前节点的高度等于左右子树最大高度加一。9. 查找目标值defcontains(root:TreeNode|None,target:int)-bool:ifrootisNone:returnFalseifroot.valuetarget:returnTruereturncontains(root.left,target)orcontains(root.right,target)普通二叉树没有排序性质因此最坏需要遍历所有节点。10. 判断两棵树是否相同defsame_tree(left:TreeNode|None,right:TreeNode|None,)-bool:ifleftisNoneorrightisNone:returnleftisrightifleft.value!right.value:returnFalsereturnsame_tree(left.left,right.left)andsame_tree(left.right,right.right,)递归比较结构和节点值是树问题中常见的分解方式。五、常见问题与实践建议1. 为什么树遍历容易写错通常是因为没有先明确遍历顺序或者忽略了空节点。写递归函数前先定义空树返回什么。当前节点什么时候处理。子树按什么顺序处理。2. 递归会不会栈溢出如果树退化成很深的链表递归深度可能超过 Python 限制。数据规模大或树形态不可控时使用显式栈更安全。3. 为什么层序遍历要记录当前队列长度记录当前长度可以区分不同层。如果只持续取队首仍然能遍历全部节点但无法直接得到每层的分组结果。4. 普通二叉树可以快速查找吗不能保证。只有增加排序、平衡或索引等结构约束才能获得更稳定的查找性能。5. 删除树节点为什么常用后序遍历删除一个节点前先处理子树可以确保子树资源或状态已经处理完毕。文件目录删除就是一个典型例子。六、进阶思考1. 二叉搜索树二叉搜索树满足左子树所有值 当前节点 右子树所有值 当前节点在树高较小时查找、插入和删除接近O(log n)退化后可能降为O(n)。2. 平衡树AVL 树、红黑树等结构通过旋转保持树高避免频繁操作后退化。Python 内置字典不是二叉搜索树而是哈希结构。3. 序列化与反序列化树可以转换为列表或字符串用于存储、传输和缓存。序列化时要保留空节点信息否则可能无法还原原始结构。4. 树与图的关系树是一种没有环的连通图。学习树的遍历后可以自然过渡到图的 DFS、BFS、最短路径和拓扑排序。结论二叉树通过节点和左右子树表达层级关系。前序、中序、后序属于深度优先遍历层序遍历使用队列实现广度优先访问。掌握递归定义、显式栈和队列后就能解决大量树结构问题。下一篇将介绍排序算法比较不同排序方法的思想、复杂度、稳定性和适用场景。参考资料Python 官方文档https://docs.python.org/3/Introduction to Algorithmshttps://mitpress.mit.edu/9780262046305/introduction-to-algorithms/Open Data Structureshttps://opendatastructures.org/