当前位置：首页 > news >正文

数据结构初阶｜二叉树入门，从零到一吃透基础

news 2026/5/12 2:31:40

文章目录

前言
一、先搞懂：二叉树的核心概念（不绕弯）
二、重中之重：二叉树的4种遍历方式（必掌握）
三、实战必刷：二叉树高频面试题（附思路+代码）
四、新手常见误区（避坑指南，少走弯路）
五、总结与学习建议

前言

作为数据结构领域的“入门进阶枢纽”，二叉树是每个程序员绕不开的知识点——它既是线性结构（数组、链表）的延伸，也是红黑树、B+树等高级结构的基础，更是面试高频考点（校招社招几乎必考遍历、构建、应用题）。

很多新手学二叉树时会陷入“抽象难懂”的困境，要么搞不清递归遍历的逻辑，要么混淆各种树的形态，其实核心就一句话：二叉树本质是“每个节点最多有两个子节点”的树形结构，所有复杂题型，都是“遍历”的延伸。

这篇博客不堆砌晦涩概念，用“人话+代码+实例”，从基础到实战，帮你彻底掌握二叉树，看完就能上手刷题，新手也能轻松跟上～

一、先搞懂：二叉树的核心概念（不绕弯）

官方定义很抽象，我们用通俗的话拆解：二叉树是由n（n≥0）个节点组成的有限集合，要么是空树，要么由一个根节点和两棵互不相交的左子树、右子树组成，且每个节点最多只有两个“孩子”——左孩子和右孩子，没有孩子的节点叫叶子节点。

可以用生活中的“家谱”类比理解核心术语：根节点是家谱里的“老祖宗”（树的起点，无父节点），叶子节点是“晚辈”（无孩子），节点的度就是“孩子的数量”（二叉树中最多为2），树的深度是从根到最远叶子的“步数”，高度则是从叶子到根的“步数”，二者方向相反。

1. 二叉树的3种常见形态（必区分）

日常学习和面试中，最常接触的就是以下3种，尤其是完全二叉树，是堆、B+树的基础：

满二叉树：除了叶子节点，每个节点都有两个子节点，每一层的节点数都达到最大值。比如深度为3的满二叉树，总节点数是7，公式为2^h - 1（h为深度），它是完全二叉树的“顶配版”。
完全二叉树：除了最后一层，每一层的节点数都达到最大值，且最后一层的节点全部集中在左侧，中间不能有空缺。满二叉树是特殊的完全二叉树，它也是顺序存储（数组）的核心适配结构，堆就是完全二叉树的典型应用。
普通二叉树：不满足满二叉树和完全二叉树的条件，节点分布无规律，是日常练习和面试题中最常见的形态。

2. 二叉树的核心性质（面试计算题常考）

二叉树的5个核心性质，不用死记硬背，理解推导逻辑更易掌握，尤其是性质3和性质5，高频考点：

性质1：二叉树的第i（i≥1）层上，最多有2^(i-1)个节点（根为第1层，第1层最多1个，第2层最多2个，以此类推）。
性质2：深度为h的二叉树，最多有2^h - 1个节点（即满二叉树的节点总数）。
性质3：对任何一棵二叉树，叶子节点数n₀ = 度为2的节点数n₂ + 1（推导核心：节点总数=叶子节点+度为1的节点+度为2的节点，总边数=节点总数-1，联立可证）。
性质4：具有n个节点的完全二叉树，其深度h为⌊log₂n⌋ + 1（比如n=7时，深度为3）。
性质5：完全二叉树的节点编号规则（数组存储的基础）：若节点编号为i（从1开始），则父节点编号为⌊i/2⌋，左孩子编号为2i，右孩子编号为2i+1（若超出节点总数，则无对应孩子）。

3. 二叉树的存储结构（两种常用方式）

二叉树有两种主流存储方式，分别适配不同场景，日常开发中链式存储更常用，顺序存储多用于完全二叉树（如堆）：

（1）链式存储（最灵活，推荐）

用链表节点串联，每个节点包含“数据域+左右指针”，适合各种形态的二叉树，插入、删除操作更便捷。以下是C语言和Java两种常用语言的节点定义：

// C语言：二叉树节点定义（链式存储） typedef struct TreeNode { int val; // 节点存储的数据 struct TreeNode* left; // 指向左子节点的指针 struct TreeNode* right; // 指向右子节点的指针 } TreeNode;

// Java：二叉树节点定义（链式存储） class TreeNode { int val; TreeNode left; // 左子节点 TreeNode right; // 右子节点 // 构造方法 public TreeNode(int val) { this.val = val; this.left = null; this.right = null; } }

（2）顺序存储（数组存储，适配完全二叉树）

用一组连续的数组单元存储节点，依托完全二叉树的编号规则（性质5），通过数组索引快速定位父节点和子节点。优点是查找关系高效（O(1)），空间利用率高（完全二叉树无浪费）；缺点是对非完全二叉树（如斜树）空间浪费严重，插入删除不便。

示例（数组索引从1开始）：根节点存在索引1，节点i的左孩子在2i，右孩子在2i+1，父节点在⌊i/2⌋。

二、重中之重：二叉树的4种遍历方式（必掌握）

遍历是二叉树的灵魂——所谓遍历，就是“按一定顺序访问树的所有节点，且每个节点只访问一次”。常见的有4种，其中前序、中序、后序属于深度优先遍历（DFS，用递归或栈实现），层序属于广度优先遍历（BFS，用队列实现），记住核心：“先中后”指的是根节点的访问时机，左右子树的顺序永远是左在前、右在后。

我们用一棵固定示例树，统一讲解4种遍历的顺序和代码，示例树结构：根节点（1）→ 左子树（2）→ 2的左孩子（4）、2的右孩子（5）；根节点右子树（3）→ 3的右孩子（6）。

1. 前序遍历（根 → 左 → 右）

核心顺序：先访问根节点，再递归遍历左子树，最后递归遍历右子树。

示例遍历结果：1 → 2 → 4 → 5 → 3 → 6

应用场景：快速获取树的根节点，构建二叉树（前序+中序可唯一确定一棵二叉树）。

// Java 递归实现（最简洁，面试首选） public void preorderTraversal(TreeNode root) { // 终止条件：节点为空，直接返回（避免栈溢出） if (root == null) return; // 1. 访问根节点 System.out.print(root.val + " "); // 2. 递归遍历左子树 preorderTraversal(root.left); // 3. 递归遍历右子树 preorderTraversal(root.right); }

补充：迭代实现（面试常考，避免递归栈溢出），核心用栈存储节点，先压右孩子，再压左孩子（保证左子树先访问）。

// Java 迭代实现（前序遍历） public void preorderIterate(TreeNode root) { if (root == null) return; Stack&lt;TreeNode&gt; stack = new Stack<>(); stack.push(root); while (!stack.isEmpty()) { TreeNode node = stack.pop(); // 访问根节点 System.out.print(node.val + " "); // 先压右孩子，再压左孩子（栈先进后出） if (node.right != null) stack.push(node.right); if (node.left != null) stack.push(node.left); } }

2. 中序遍历（左 → 根 → 右）

核心顺序：先递归遍历左子树，再访问根节点，最后递归遍历右子树。

示例遍历结果：4 → 2 → 5 → 1 → 3 → 6

关键特性：如果是二叉搜索树（BST），中序遍历的结果是升序序列（面试高频考点，比如判断一棵树是不是二叉搜索树），这也是二叉搜索树排序、去重的核心原理。

// Java 递归实现 public void inorderTraversal(TreeNode root) { if (root == null) return; // 1. 遍历左子树 inorderTraversal(root.left); // 2. 访问根节点 System.out.print(root.val + " "); // 3. 遍历右子树 inorderTraversal(root.right); }

3. 后序遍历（左 → 右 → 根）

核心顺序：先递归遍历左子树，再递归遍历右子树，最后访问根节点。

示例遍历结果：4 → 5 → 2 → 6 → 3 → 1

应用场景：删除二叉树（先删子节点，再删根节点，避免内存泄漏）、求树的深度、后续遍历序列与中序序列结合构建二叉树。

4. 层序遍历（从上到下，从左到右）

核心顺序：按层次访问，先访问根节点（第1层），再访问第2层的所有节点，依次类推，属于广度优先遍历，必须用队列实现。

示例遍历结果：1 → 2 → 3 → 4 → 5 → 6

应用场景：求树的层数、找某一层的节点、判断是否为完全二叉树、打印树形结构（如部门树、菜单树）。

// Java 迭代实现（队列） public void levelOrder(TreeNode root) { if (root == null) return; // 队列存储当前层的节点 Queue&lt;TreeNode&gt; queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { // 取出当前层的节点数（避免遍历过程中队列长度变化） int size = queue.size(); // 遍历当前层的所有节点 for (int i = 0; i < size; i++) { TreeNode node = queue.poll(); System.out.print(node.val + " "); // 左孩子入队（先左后右，保证层序顺序） if (node.left != null) queue.offer(node.left); // 右孩子入队 if (node.right != null) queue.offer(node.right); } } }

三、实战必刷：二叉树高频面试题（附思路+代码）

掌握遍历后，大部分二叉树题目都能迎刃而解，这里整理3道面试最常考的题型，帮你举一反三，覆盖递归、层序等核心思路。

题型1：求二叉树的最大深度

思路：后序遍历（左、右、根），根节点的深度 = 左右子树深度的最大值 + 1（+1是因为根节点本身算一层）；也可以用层序遍历，统计层数即为最大深度。

// Java 递归实现（后序遍历思路） public int maxDepth(TreeNode root) { // 空树深度为0 if (root == null) return 0; // 左子树深度 int leftDepth = maxDepth(root.left); // 右子树深度 int rightDepth = maxDepth(root.right); // 根节点深度 = 左右最大值 + 1 return Math.max(leftDepth, rightDepth) + 1; }

题型2：判断两棵二叉树是否相同

思路：前序遍历（根、左、右），同时遍历两棵树，判断每个节点的值是否相等，且左右子树结构是否一致，只要有一个节点不满足，就返回false。

public boolean isSameTree(TreeNode p, TreeNode q) { // 两棵树都为空，相同 if (p == null && q == null) return true; // 一棵空、一棵非空，不同 if (p == null || q == null) return false; // 节点值不相等，不同 if (p.val != q.val) return false; // 递归判断左子树和右子树，必须都相同才返回true return isSameTree(p.left, q.left) && isSameTree(p.right, q.right); }

题型3：找二叉树的最近公共祖先（LCA，高频压轴题）

思路：后序遍历，核心逻辑：如果当前节点是p或q，直接返回当前节点；否则递归左右子树，左子树找不到就返回右子树的结果，右子树找不到就返回左子树的结果，若左右子树都找到，则当前节点就是最近公共祖先。

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { // 终止条件：节点为空，或找到p/q if (root == null || root == p || root == q) return root; // 递归左子树 TreeNode left = lowestCommonAncestor(root.left, p, q); // 递归右子树 TreeNode right = lowestCommonAncestor(root.right, p, q); // 左子树没找到，返回右子树的结果 if (left == null) return right; // 右子树没找到，返回左子树的结果 if (right == null) return left; // 左右都找到，当前节点是公共祖先 return root; }

四、新手常见误区（避坑指南，少走弯路）

误区1：混淆“深度”和“高度”——深度是从根到当前节点的步数（根深度=1），高度是从当前节点到最远叶子的步数（叶子高度=0），二者方向相反，面试常考辨析题。
误区2：混淆“前中后序”的顺序——记住核心：“先中后”指的是根节点的访问时机，不是方向，左右子树的顺序永远是左在前、右在后，比如中序是“左→根→右”，不是“根→左→右”的颠倒。
误区3：递归遍历忘记写终止条件——必然导致栈溢出，所有递归遍历的终止条件都是“节点为空时返回”，这是新手最容易犯的错误。
误区4：层序遍历用栈实现——层序是广度优先，必须用队列；栈是深度优先（前中后序迭代实现用栈），二者不可混淆。
误区5：认为“二叉树就是度为2的树”——正解：二叉树的节点度可以是0（叶子）、1（只有一个孩子）或2（两个孩子），并非所有节点都有两个孩子。
误区6：忽视空树的处理——空树是合法的二叉树，代码中必须处理root==null的情况，否则会出现空指针异常。