数据结构复习：二叉树-北京尧图网络

一、树一种递归定义的非线性结构树是由 nn ≥ 0个有限结点组成的具有层次关系的集合。之所以叫树是因为它看起来像一棵倒挂的树——根朝上叶朝下。1.1 定义的两个要点有一个特殊的根结点根结点没有前驱结点。除根结点外其余结点被分成 M(M 0) 个互不相交的集合 T1、T2……Tm其中每一个集合 Ti(1 ≤ i ≤ m) 本身又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱可以有 0 个或多个后继。因此树是递归定义的。⚠️ 注意树形结构中子树之间不能有交集否则就不是树形结构。1.2 术语速查以根 A 有 6 个孩子的树为例术语含义示例结点的度该结点含有子树的个数A 的度为 6叶结点 / 终端结点度为 0 的结点B、C、H、I分支结点 / 非终端结点度不为 0 的结点D、E、F、G双亲结点父结点含有子结点的那个结点A 是 B 的父结点孩子结点子结点结点所含子树的根结点B 是 A 的孩子兄弟结点具有相同父结点的结点B、C 是兄弟堂兄弟结点双亲在同一层的结点H、I 互为堂兄弟树的度树中最大的结点度树的度为 6结点的层次根为第 1 层往下递增根在第 1 层树的高度 / 深度树中结点的最大层次高度为 4祖先 / 子孙根到该结点路径上的所有结点 / 以某结点为根的子树中任一结点A 是所有结点的祖先森林m(m 0) 棵互不相交的树的集合多个目录树1.3 树的表示孩子兄弟表示法树既要保存值域又要保存结点之间的关系因此比线性表复杂。常见的表示法有双亲表示法、孩子表示法、孩子双亲表示法、孩子兄弟表示法。最常用的是孩子兄弟表示法——左指针指向第一个孩子右指针指向下一个兄弟。typedef int DataType; struct Node { struct Node* firstChild1; // 第一个孩子结点 struct Node* pNextBrother; // 指向其下一个兄弟结点 DataType data; // 结点中的数据域 };树在实际中最典型的应用就是文件系统的目录树结构。二、二叉树度不超过 2 的有序树二叉树是结点的一个有限集合该集合或者为空由一个根结点加上两棵分别称为左子树和右子树的二叉树组成。由此可得二叉树不存在度大于 2的结点二叉树的子树有左右之分次序不能颠倒因此二叉树是有序树。2.1 两类特殊的二叉树类型判定规则与其他类型的关系满二叉树每一层的结点数都达到最大值层数为 K 时结点总数为 2^K - 1满二叉树是一种特殊的完全二叉树完全二叉树深度为 K、有 n 个结点且每个结点都与深度为 K 的满二叉树中编号 1 至 n 的结点一一对应效率很高适合顺序存储2.2 二叉树的性质高频考点若规定根结点的层数为 1则一棵非空二叉树的第 i 层上最多有2^(i-1)个结点。若规定根结点的层数为 1则深度为 h 的二叉树的最大结点数是2^h - 1。对任何一棵二叉树若度为 0 的叶结点个数为 n0、度为 2 的分支结点个数为 n2则n0 n2 1。若规定根结点的层数为 1具有 n 个结点的满二叉树的深度h log2(n1)log 以 2 为底n1 为对数。对于具有 n 个结点的完全二叉树按从上至下、从左至右的顺序从 0 开始编号则序号为 i 的结点若 i 0双亲序号为(i-1)/2i 0 时是根结点无双亲若 2i1 n左孩子序号为2i1否则无左孩子若 2i2 n右孩子序号为2i2否则无右孩子。2.3 性质 3 的推导为什么 n0 n2 1/* * 假设二叉树有 N 个结点 * 从总结点数角度考虑N n0 n1 n2 ① * * 从边的角度考虑N 个结点的任意二叉树总共有 N-1 条边 * 因为每个结点都有双亲根结点除外每个结点向上与双亲之间存在一条边 * 因此 N 个结点的二叉树总共有 N-1 条边 * * 度为 0 的结点没有孩子不产生边 * 度为 1 的结点只有一个孩子产生 1 条边 * 度为 2 的结点有两个孩子产生 2 条边 * 所以总边数为n1 2*n2 * 故从边的角度考虑N-1 n1 2*n2 ② * * 结合 ① 和 ② 得n0 n1 n2 n1 2*n2 - 1 * 即n0 n2 1 */推导思路一句话同一棵树的结点数只有两种数法——按结点数n0n1n2和按边数边 n12n2且边结点数-1。两个式子对齐n1 自然消掉。2.4 配套练习某二叉树共有 399 个结点其中有 199 个度为 2 的结点则该二叉树中的叶子结点数为 A 不存在这样的二叉树 B 200 C 198 D 199下列数据结构中不适合采用顺序存储结构的是 A 非完全二叉树 B 堆 C 队列 D 栈在具有 2n 个结点的完全二叉树中叶子结点个数为 A n B n1 C n-1 D n/2一棵完全二叉树的结点数为 531 个那么这棵树的高度为 A 11 B 10 C 8 D 12一个具有 767 个结点的完全二叉树其叶子结点个数为 A 383 B 384 C 385 D 386答案题号答案简述1Bn0 n2 1 199 1 2002A非完全二叉树用数组存会大量浪费空间3A2n 个结点的完全二叉树n0 n4B2^9-1 511 531 ≤ 2^10-1 1023深度为 105B767 个结点n0 (7671)/2 384三、二叉树的两种存储结构3.1 顺序存储用数组物理存储用完全二叉树逻辑理解顺序结构存储就是使用数组来存储。一般只适合表示完全二叉树因为非完全二叉树会造成大量空间浪费。现实中通常只有堆会使用数组来存储。关键理解二叉树顺序存储在物理上是一个数组在逻辑上是一棵二叉树。3.2 链式存储用指针表达父子关系链表中每个结点由三个域组成数据域和左右指针域左右指针分别用来给出该结点左孩子和右孩子所在链结点的存储地址。链式结构又分为二叉链和三叉链。typedef int BTDataType; // 二叉链 struct BinaryTreeNode { struct BinTreeNode* left; // 指向当前结点左孩子 struct BinTreeNode* right; // 指向当前结点右孩子 BTDataType data; // 当前结点值域 }; // 三叉链 struct BinaryTreeNode { struct BinTreeNode* parent; // 指向当前结点的双亲 struct BinTreeNode* left; // 指向当前结点的左孩子 struct BinTreeNode* right; // 指向当前结点的右孩子 BTDataType data; // 当前结点值域 };当前学习阶段一般使用二叉链后续学到红黑树等高阶数据结构时会用到三叉链。四、堆完全二叉树的顺序存储应用4.1 堆的定义与性质如果有一个关键码的集合 K {k0, k1, k2, …, kn-1}把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中并满足ki ≤ k(2i1) 且 ki ≤ k(2i2) ——小堆或 ki ≥ k(2i1) 且 ki ≥ k(2i2) ——大堆则称为小堆或大堆。根结点最大的堆叫最大堆或大根堆根结点最小的堆叫最小堆或小根堆。堆的两条性质堆中某个结点的值总是不大于或不小于其父结点的值堆总是一棵完全二叉树。⚠️ 这里的堆和操作系统虚拟进程地址空间中的堆是两回事——一个是数据结构一个是操作系统中管理内存的一块区域分段。4.2 向下调整算法堆的基石给出一个数组逻辑上看做一棵完全二叉树。通过从根结点开始的向下调整算法可以把它调整成一个小堆。向下调整算法有一个前提左右子树必须是一个堆才能调整。int array[] {27,15,19,18,28,34,65,49,25,37};4.3 建堆从最后一个非叶子结点开始如果根结点左右子树都不是堆怎么调整答案是从倒数的第一个非叶子结点的子树开始调整最后一个非叶子结点下标 (n-1-1)/2一直调整到根结点的树就可以把整棵树调整成堆。int a[] {1,5,3,8,7,6};建堆时间复杂度因为堆是完全二叉树而满二叉树也是完全二叉树为简化证明可用满二叉树时间复杂度本来就是近似值多几个结点不影响结果。✅ 最终结论建堆的时间复杂度为 O(N)——不是 O(N·logN)这是最常被记错的结论。直觉解释越靠近叶子的结点越多但它们需要向下调整的层数越少两者相乘求和总量收敛到 O(N)。4.4 插入与删除插入先插入一个元素到数组的尾部保持完全二叉树形态再进行向上调整算法直到满足堆的性质。删除堆的删除固定是删除堆顶数据。做法是把堆顶数据与最后一个数据交换然后删除数组最后一个数据再进行向下调整算法。4.5 堆的接口设计typedef int HPDataType; typedef struct Heap { HPDataType* _a; int _size; int _capacity; }Heap; // 堆的构建 void HeapCreate(Heap* hp, HPDataType* a, int n); // 堆的销毁 void HeapDestory(Heap* hp); // 堆的插入 void HeapPush(Heap* hp, HPDataType x); // 堆的删除 void HeapPop(Heap* hp); // 取堆顶的数据 HPDataType HeapTop(Heap* hp); // 堆的数据个数 int HeapSize(Heap* hp); // 堆的判空 int HeapEmpty(Heap* hp);4.6 配套练习下列关键字序列为堆的是 A 100,60,70,50,32,65 B 60,70,65,50,32,100 C 65,100,70,32,50,60 D 70,65,100,32,50,60 E 32,50,100,70,65,60 F 50,100,70,65,60,32已知小根堆为 8,15,10,21,34,16,12删除关键字 8 之后需重建堆在此过程中关键字之间的比较次数是 A 1 B 2 C 3 D 4一组记录排序码为 (5 11 7 2 3 17)则利用堆排序方法建立的初始堆为 A (11 5 7 2 3 17) B (11 5 7 2 17 3) C (17 11 7 2 3 5) D (17 11 7 5 3 2) E (17 7 11 3 5 2) F (17 7 11 3 2 5)最小堆 [0,3,2,5,7,4,6,8]在删除堆顶元素 0 之后其结果是 A [3,2,5,7,4,6,8] B [2,3,5,7,4,6,8] C [2,3,4,5,7,8,6] D [2,3,4,5,6,7,8]答案1. A 2. C 3. C 4. C五、堆的两大应用堆排序与 Top-K5.1 堆排序两个步骤建堆升序建大堆降序建小堆利用堆删除思想进行排序每次把堆顶与末尾交换并缩小堆范围再向下调整。建堆和堆删除中都用到了向下调整因此掌握了向下调整就可以完成堆排序。为什么升序要建大堆因为大堆的堆顶是当前最大值把它换到数组末尾就是它的最终位置然后缩小范围继续——每轮都把一个「最大的」正确归位。5.2 TOP-K 问题TOP-K 问题求数据集合中前 K 个最大或最小的元素一般情况下数据量都比较大。例如专业前 10 名、世界 500 强、富豪榜、游戏中前 100 的活跃玩家。最简单直接的方式就是排序但如果数据量非常大排序就不可取了可能数据都不能一次性全部加载到内存中。最佳方式是用堆来解决基本思路用数据集合中前 K 个元素来建堆求前 K 个最大的元素 → 建小堆求前 K 个最小的元素 → 建大堆用剩余的 N-K 个元素依次与堆顶元素比较不满足则替换堆顶元素。遍历完之后堆中剩余的 K 个元素就是所求的前 K 个最小或最大的元素。为什么求「最大」的 K 个反而建「小」堆因为堆顶是这 K 个元素里最小的那个它才是「最容易被淘汰」的门槛——只有当新元素比门槛大才值得挤进来。void PrintTopK(int* a, int n, int k) { // 1. 建堆--用a中前k个元素建堆 // 2. 将剩余n-k个元素依次与堆顶元素交换不满则替换 } void TestTopk() { int n 10000; int* a (int*)malloc(sizeof(int)*n); srand(time(0)); for (size_t i 0; i n; i) { a[i] rand() % 1000000; } a[5] 1000000 1; a[1231] 1000000 2; a[531] 1000000 3; a[5121] 1000000 4; a[115] 1000000 5; a[2335] 1000000 6; a[9999] 1000000 7; a[76] 1000000 8; a[423] 1000000 9; a[3144] 1000000 10; PrintTopK(a, n, 10); }六、二叉树链式结构从建树到四种遍历6.1 前置说明先手动建一棵树学习二叉树基本操作前需要先创建一棵二叉树。为了降低学习成本此处先手动快速创建一棵简单的二叉树快速进入二叉树操作学习真正创建二叉树的方式按前序数组构建后面再详解。typedef int BTDataType; typedef struct BinaryTreeNode { BTDataType _data; struct BinaryTreeNode* _left; struct BinaryTreeNode* _right; }BTNode; BTNode* CreatBinaryTree() { BTNode* node1 BuyNode(1); BTNode* node2 BuyNode(2); BTNode* node3 BuyNode(3); BTNode* node4 BuyNode(4); BTNode* node5 BuyNode(5); BTNode* node6 BuyNode(6); node1-_left node2; node1-_right node4; node2-_left node3; node4-_left node5; node4-_right node6; return node1; }这棵树长这样1 / \ 2 4 / / \ 3 5 6再看二叉树基本操作前回顾一下概念二叉树要么是空树要么是非空根结点根结点的左子树根结点的右子树。从概念中可以看出二叉树定义是递归式的因此后续基本操作基本都是按照该概念实现的。6.2 前序 / 中序 / 后序遍历所谓二叉树遍历Traversal是按照某种特定的规则依次对二叉树中的结点进行相应的操作并且每个结点只操作一次。遍历是二叉树上最重要的运算之一也是二叉树上进行其它运算的基础。由于被访问的结点必是某子树的根所以 N(Node)、L(Left subtree) 和 R(Right subtree) 又可解释为根、根的左子树和根的右子树。NLR、LNR 和 LRN 分别又称为先根遍历、中根遍历和后根遍历。前序遍历Preorder Traversal亦称先序遍历——访问根结点的操作发生在遍历其左右子树之前即NLR中序遍历Inorder Traversal——访问根结点的操作发生在遍历其左右子树之中间即LNR后序遍历Postorder Traversal——访问根结点的操作发生在遍历其左右子树之后即LRN。// 二叉树前序遍历 void PreOrder(BTNode* root); // 二叉树中序遍历 void InOrder(BTNode* root); // 二叉树后序遍历 void PostOrder(BTNode* root); // 层序遍历 void LevelOrder(BTNode* root);6.3 三种递归遍历的实现三行骨架递归遍历的代码骨架只有三件事判空返回 → 访问根结点 → 递归左右子树。三种遍历换的只是「访问」这一步的位置。void PreOrder(BTNode* root) { if (root NULL) return; printf(%d , root-_data); // 访问根结点 PreOrder(root-_left); PreOrder(root-_right); } void InOrder(BTNode* root) { if (root NULL) return; InOrder(root-_left); printf(%d , root-_data); // 访问根结点 InOrder(root-_right); } void PostOrder(BTNode* root) { if (root NULL) return; PostOrder(root-_left); PostOrder(root-_right); printf(%d , root-_data); // 访问根结点 }6.4 上面那棵树的遍历结果务必对照验证遍历方式访问规则结果前序遍历根 → 左子树 → 右子树NLR1 2 3 4 5 6中序遍历左子树 → 根 → 右子树LNR3 2 1 5 4 6后序遍历左子树 → 右子树 → 根LRN3 2 5 6 4 1三个结果里最容易被忽视的是中序因为 1 的左子树只有 2 和 3所以先输出 3、2再输出根 1最后才是右子树 4 的「左 5、右 6、根 4」。6.5 层序遍历借一个队列设二叉树的根结点所在层数为 1层序遍历就是从根结点出发先访问第一层的根结点然后从左到右访问第 2 层的结点接着是第三层……自上而下、自左至右逐层访问。实现上需要借助一个队列根结点先入队出队时访问该结点并把其左右孩子依次入队。void LevelOrder(BTNode* root) { Queue q; QueueInit(q); if (root) QueuePush(q, root); while (!QueueEmpty(q)) { BTNode* front QueueFront(q); QueuePop(q); printf(%d , front-_data); if (front-_left) QueuePush(q, front-_left); if (front-_right) QueuePush(q, front-_right); } QueueDestroy(q); }6.6 配套练习某完全二叉树按层次输出同一层从左到右的序列为 ABCDEFGH该完全二叉树的前序序列为 A ABDHECFG B ABCDEFGH C HDBEAFCG D HDEBFGCA二叉树的先序遍历和中序遍历如下先序遍历 EFHIGJK中序遍历 HFIEJKG。则二叉树根结点为 A E B F C G D H设一棵二叉树的中序遍历序列为 badce后序遍历序列为 bdeca则二叉树前序遍历序列为 A adbce B decab C debac D abcde某二叉树的后序遍历序列与中序遍历序列相同均为 ABCDEF则按层次输出同一层从左到右的序列为 A FEDCBA B CBAFED C DEFCBA D ABCDEF答案1. A 2. A 3. D 4. A解题钥匙先序的第一个结点、后序的最后一个结点一定是根拿到根后回到中序序列根左边的就是左子树、右边的就是右子树然后对两段递归。七、结点个数、高度与销毁递归思维的统一模板这一组函数的共同思想把整棵树的问题拆成「根的贡献左子树的问题右子树的问题」边界条件是空树返回 0。// 二叉树结点个数 int BinaryTreeSize(BTNode* root) { if (root NULL) return 0; return 1 BinaryTreeSize(root-_left) BinaryTreeSize(root-_right); } // 二叉树叶子结点个数 int BinaryTreeLeafSize(BTNode* root) { if (root NULL) return 0; if (root-_left NULL root-_right NULL) return 1; return BinaryTreeLeafSize(root-_left) BinaryTreeLeafSize(root-_right); } // 二叉树第 k 层结点个数 int BinaryTreeLevelKSize(BTNode* root, int k) { if (root NULL) return 0; if (k 1) return 1; return BinaryTreeLevelKSize(root-_left, k - 1) BinaryTreeLevelKSize(root-_right, k - 1); } // 二叉树查找值为 x 的结点 BTNode* BinaryTreeFind(BTNode* root, BTDataType x) { if (root NULL) return NULL; if (root-_data x) return root; BTNode* ret BinaryTreeFind(root-_left, x); if (ret) return ret; return BinaryTreeFind(root-_right, x); } // 二叉树销毁后序 void BinaryTreeDestory(BTNode** root) { if (*root NULL) return; BinaryTreeDestory((*root)-_left); BinaryTreeDestory((*root)-_right); free(*root); *root NULL; }两个容易踩的点第 k 层结点个数用的是「往下走 k-1 层」而不是在第 k 层判叶子销毁必须用后序因为要先释放左右孩子再释放根。7.1 完整接口清单// 通过前序遍历的数组ABD##E#H##CF##G##构建二叉树 BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi); // 判断二叉树是否是完全二叉树 int BinaryTreeComplete(BTNode* root);OJ 练习清单单值二叉树、检查两棵树是否相同、对称二叉树、二叉树的前/中/后序遍历、另一棵树的子树、二叉树的构建及遍历。八、一页速查表最容易记错的结论知识点正确结论非空二叉树第 i 层最多结点数2^(i-1)根为第 1 层深度为 h 的二叉树最大结点数2^h - 1即满二叉树叶子数与度为 2 的结点数n0 n2 1n 个结点的满二叉树深度h log2(n1)完全二叉树下标 i 的双亲(i-1)/2i 0完全二叉树下标 i 的左 / 右孩子2i1 / 2i2越界则不存在建堆时间复杂度O(N)而非 O(N·logN)堆插入 / 堆删除的时间复杂度向上调整 O(logN) / 向下调整 O(logN)堆排序的建堆方向升序建大堆降序建小堆求前 K 个最大元素建小堆堆顶是可淘汰门槛适合顺序存储的二叉树完全二叉树堆非完全二叉树会浪费空间二叉树三种遍历的代码差异只差「访问根结点」那一行的位置

数据结构复习：二叉树

相关推荐

2026年不动产行业数据治理白皮书：数据资产管理的进阶之路与AI原生治理新范式

MCP爆火了！Nodejs用户也不能落后：用TaoToken统一Key打通MCP服务调用

成都学无人机维修，一个月左右到底够不够？别只盯着时间看

更多资讯

AI工程从零搭建：环境配置到模型部署的完整实践指南

企业私有化RAG知识库搭建实战：架构设计、技术选型与踩坑总结

PB 设置 lock_timeout 参数（当前连接生效）：TaoToken 统一 Key 接入 AI 工具配置骨架

法务AI与Agent工具：TaoToken统一Key接入合同审查自动化工作流

别再重复提示 Codex：用一个 Skill 固化你的代码检查工作流

Codex 401报错与配置不生效排查：config.toml加载顺序、auth.json冲突及TOML语法解析

今日更新

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

本周精选

如何彻底离线使用 Laya-CoreML：Hugging Face 下载、缓存机制与 local_files_only 详解

基于1Panel 部署MySQL MCP 服务：TaoToken 统一 Key 接入与 config.toml 配置实战

崇州园区营销网站建设避坑指南：5大注意事项保备案安全

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？