写在前面在前面的数据结构学习中我们已经完整梳理了线性数据结构部分顺序表与链表研究数据元素之间的一对一关系栈与队列研究操作受限制的线性结构。这些结构有一个共同特点数据元素之间存在一条明确的线性关系每个元素最多只有一个前驱和一个后继形如A → B → C → D。但在实际开发中很多数据并不是简单的一条线文件系统的目录结构、公司的组织架构、数据库的索引结构、搜索引擎的层级关系……它们更符合“层层向下展开”的形态。因此从这一篇开始我们正式进入非线性数据结构的世界——树Tree。 而在所有树结构中最经典、应用最广泛、也是整个数据结构体系核心的就是二叉树Binary Tree。前置知识推荐在正式开始二叉树学习之前非常建议先补一篇 C 语言底层原理内容C语言底层函数栈帧的创建与销毁一从汇编视角看懂函数调用的本质简述-CSDN博客这篇内容不属于数据结构专题但它讲解的「函数调用栈帧机制」是理解二叉树递归的关键底层支撑。为什么要先懂栈帧后续二叉树的学习中我们会大量接触递归遍历、深度优先搜索DFS、树高计算、分治思想。而这些算法的底层本质上都在依赖函数调用栈。比如最经典的前序遍历void PrevOrder(TreeNode* root) { if(root NULL) return; printf(%d , root-data); PrevOrder(root-left); PrevOrder(root-right); }表面上是几行简单的递归代码但程序真正执行时每一次递归调用都会在系统栈中创建新的函数栈帧PrevOrder(A) ↓ PrevOrder(B) ↓ PrevOrder(D) ↓ 逐层返回每进入一层递归系统都会保存当前函数的局部变量、下一步执行位置开辟新栈帧继续执行递归结束时再按照后进先出的顺序逐层销毁回到上一层继续执行。理解了函数栈帧你才能真正明白为什么递归可以独立保存每一层的数据为什么递归深度过大会导致栈溢出为什么二叉树遍历可以天然用递归实现。如果对 C 语言内存、函数调用机制还比较陌生建议先看完栈帧相关内容再来学习二叉树递归会顺畅很多。一、树的概念与基础特点1.1 什么是树树是由nn ≥ 0个有限节点组成的非线性数据结构节点之间通过连接形成清晰的层次关系。当 n0 时称为空树。比如一棵简单的树A / | \ B C D / \ E F其中 A 是根节点B、C、D 是 A 的子节点E、F 是 B 的子节点。数据结构里的树和现实中的树形态一致只不过是倒过来画的根在上叶子在下。1.2 树的三个核心特点有且仅有一个根节点它是整棵树的最顶层节点没有父节点。除根节点外每个节点有且仅有一个父节点不存在一个节点有多个上层节点。不存在环树中任意两个节点之间有且只有一条路径。如果出现闭环结构就不再属于树而是图。二、树的核心术语这些术语是树结构的基础语言必须逐个理解节点的度一个节点直接拥有的子节点数量称为该节点的度。叶节点终端节点度为 0 的节点也就是没有子节点、处于最底层的节点。分支节点非终端节点度不为 0 的节点也就是有子节点、可以继续分叉的节点。父节点双亲节点如果一个节点包含子节点该节点就是其子节点的父节点。子节点孩子节点一个节点直接下属的节点称为该节点的子节点。兄弟节点拥有同一个父节点的节点互称为兄弟节点。堂兄弟节点父节点位于同一层的节点互称为堂兄弟节点。树的度整棵树中所有节点度的最大值。节点的层次从根节点开始计数根为第 1 层根的子节点为第 2 层以此类推。树的高度深度树中节点的最大层次数也就是这棵树总共有多少层。节点的祖先从根节点到该节点的路径上所有经过的节点都是它的祖先。子孙以某个节点为根的子树中所有节点都称为该节点的子孙。森林由 mm≥0棵互不相交的树组成的集合称为森林。三、树的常见表示方法普通树最大的特点是一个节点可能有任意多个孩子。因此不同的表示方法本质上都是在解决「如何存储多个孩子指针」的问题。3.1 指针数组表示法C 语言基础写法最直观的思路每个节点存放数据再用一个固定长度的指针数组存储所有孩子节点的地址。#define MAX_CHILD 10 // 预设最大孩子数量 typedef struct TreeNode { int data; struct TreeNode* child[MAX_CHILD]; // 孩子指针数组 int childNum; // 实际孩子个数 } TreeNode;优点结构简单容易理解。 缺点孩子数量有上限固定数组会造成空间浪费树的度不确定时很难设定合适的数组大小。3.2 动态数组表示法C vector 写法为了解决固定数组的缺陷C 中通常用vector动态数组来存放孩子指针底层逻辑和指针数组完全一致只是数组可以按需自动扩容。struct TreeNode { int data; vectorTreeNode* child; // 动态数组存储孩子指针 };优点无需提前预估孩子数量空间利用率更高。 本质上仍然是「孩子指针数组」的思路。3.3 孩子兄弟表示法最经典通用孩子兄弟表示法也叫「左孩子右兄弟」表示法是工业界最通用的树表示方式。它的核心思想是把任意多叉树统一转换成二叉结构。每个节点只保存两个指针firstChild指向第一个孩子节点nextBrother指向右边第一个兄弟节点typedef struct TreeNode { int data; struct TreeNode* firstChild; // 第一个孩子 struct TreeNode* nextBrother; // 下一个兄弟 } TreeNode;比如一棵普通树A / | \ B C D用孩子兄弟表示法转换后结构变为A | B \ C \ D这种写法的优势非常突出无论树的度是多少每个节点都只存两个指针空间固定无浪费可以表示任意度数的树也是多叉树转二叉树的核心方法——这正是我们重点研究二叉树的原因只要把二叉树吃透所有普通树都可以通过这种方式转化后处理。四、二叉树的概念与特殊结构4.1 什么是二叉树二叉树是树的特殊形式每个节点最多有两棵子树节点的度最大为 2。 两个子节点有严格的左右顺序分别称为左孩子和右孩子次序不能颠倒。即使节点只有一个孩子也要明确区分是左还是右。比如下面两棵树是完全不同的二叉树A A / \ B B4.2 满二叉树如果一棵二叉树的每一层节点数都达到最大值所有叶子节点都在最底层所有分支节点的度都为 2这就是满二叉树。A / \ B C / \ / \ D E F G核心特点第 i 层的节点数为2^(i-1)高度为 h 的满二叉树总节点数为2^h - 1没有度为 1 的节点叶子全部在最底层这里有一个很直观的结论满二叉树的节点数量是指数级增长的。比如高度只有 30 的满二叉树总节点数就超过了 10 亿。看似不高的层数能容纳的数据量极其庞大这也是树结构查询效率极高的底层原因。4.3 完全二叉树完全二叉树是满二叉树的“前半段”前 h-1 层全部填满最后一层的节点从左到右连续排列中间没有空缺。A / \ B C / \ / D E F核心特点前 h-1 层一定是满的最后一层节点从左向右连续不能有空隙满二叉树是特殊的完全二叉树但完全二叉树不一定是满二叉树。完全二叉树最大的意义就是它非常适合用数组顺序存储——空间利用率高并且可以通过下标公式快速定位父子节点。五、二叉树的核心性质性质1每层最大节点数二叉树的第 i 层上最多有2^(i-1)个节点i ≥ 1。性质2整棵树最大节点数高度为 h 的二叉树最多有2^h - 1个节点对应满二叉树的总节点数。性质3叶子节点与度为2节点的关系对任意一棵二叉树设度为 0 的叶子节点数为n₀度为 2 的节点数为n₂则一定满足n₀ n₂ 1叶子节点的数量永远比度为 2 的节点多 1 个。性质4顺序存储下的父子下标关系这是完全二叉树数组实现最核心的公式也是后续堆结构的基础。把完全二叉树按层序遍历存入数组根节点下标为 0 时若父节点下标为i左孩子下标 2*i 1右孩子下标 2*i 2反过来已知孩子节点下标为i父节点下标 (i - 1) / 2整数除法向下取整正是因为有这个公式我们不需要指针仅凭数组下标就能快速定位任意节点的父子关系这也是完全二叉树适合顺序存储的根本原因。六、二叉树的存储结构简介二叉树主要有两种存储方式分别对应不同的场景选择的核心依据是空间利用率 操作效率。6.1 顺序存储数组实现实现方式将二叉树按层序遍历的顺序依次存入一个连续数组中通过下标公式计算父子节点的位置。适用场景满二叉树、完全二叉树对于满二叉树和完全二叉树来说节点是连续排布的数组中几乎没有空位空间利用率极高满二叉树数组空间 100% 利用没有任何浪费完全二叉树只有最后一层右侧可能有空缺浪费极少。同时配合父子下标公式定位父节点、子节点都只需要一次算术运算效率极高。这也是堆选择数组作为底层实现的核心原因。不适用场景普通二叉树如果是形态不规则的普通二叉树用数组存储会造成极其严重的空间浪费。 举个极端例子一棵只有左孩子的单支树斜树高度为 h按照满二叉树的数组长度需要开辟2^h - 1个空间但实际有效节点只有 h 个绝大多数位置都是空的。因此普通二叉树几乎不会采用顺序存储更适合用链式结构。6.2 链式存储指针实现实现方式每个节点存储数据 左孩子指针 右孩子指针和链表的思路类似。typedef struct TreeNode { int data; struct TreeNode* left; struct TreeNode* right; } TreeNode;适用场景普通二叉树对于形态不确定、节点分布不规则的二叉树链式存储按需申请节点没有多余的空间浪费灵活性极高。 后续我们学习的二叉树遍历、二叉搜索树、平衡树等内容基本都采用链式存储实现。七、初识堆Heap既然完全二叉树的顺序存储兼具空间紧凑和父子定位高效的优势工业界就基于这种结构设计出了一种非常经典实用的数据结构——堆Heap。7.1 什么是堆堆是一种特殊的完全二叉树它除了满足完全二叉树的结构要求还额外满足父子节点之间的大小关系。主要分为两类小根堆满足父节点的值 ≤ 所有子节点的值1 / \ 3 5 / 7根节点一定是整棵堆中的最小值。大根堆满足父节点的值 ≥ 所有子节点的值9 / \ 7 8 / 3根节点一定是整棵堆中的最大值。7.2 常见误区堆不是排序结构这是学习堆最容易踩的坑堆 ≠ 有序结构。堆只保证父节点和子节点之间的大小关系并不保证左子树全部小于右子树同一层的节点有序遍历结果有序。比如下面这棵小根堆1 / \ 5 3 / 8它满足15、13、58完全符合小根堆规则但5 3兄弟节点之间并没有顺序关系。一句话总结堆的核心目标是快速获取最大值或最小值而不是让所有数据有序。7.3 堆的典型应用优先级队列普通队列是先进先出而优先级队列让优先级高的元素先出队底层通常由堆实现常用于操作系统任务调度、网络请求处理等场景。堆排序利用堆的特性实现的排序算法时间复杂度 O(NlogN)。注意堆本身不是排序结构堆排序是通过反复删除堆顶元素的过程完成排序。Top K 问题比如找出海量数据中最大的前 K 个数用堆可以把复杂度优化到 O(NlogK)是面试高频考点。写在最后本篇作为二叉树专题的开篇我们沿着「 线性结构 → 树结构 → 二叉树 → 完全二叉树 → 顺序存储 → 堆」的脉络把基础概念、术语、性质和应用场景完整串了一遍。理解这些前置知识后再去学堆的实现、二叉树的递归遍历就不会只是机械地背代码而是能明白“为什么这么设计”。下一篇我们继续学习堆相关的知识进一步熟悉完全二叉树在工程上的实际运用。