🌳 树

程序里的「树」可不是种在花园里的树，而是一张从顶上往下分叉的关系图：最上面一个根，根下长枝，枝上长叶。电脑里的文件夹、家里的家族谱、公司的上下级，全都是树的模样。

考纲知识点：树的基本概念
哈夫曼树
完全二叉树
二叉排序树

📖

考纲 · 知识点详述

摘自《CCF编程能力等级认证 C++&Python 认证标准》C++ 六级

(1)掌握树的基本概念，掌握其构造与遍历的相关算法。
(2)掌握哈夫曼树、完全二叉树、二叉排序树的相关概念和应用。

📚

先学一学

花 6 分钟读完下面 5 课，再去闯关就不慌啦

🏡 树的基本样子：家族谱一样的关系图

一棵树倒着画：最顶上叫根，根往下连出的每个点叫节点。直接连在某个节点下面的叫它的孩子，它自己是孩子的爸爸（父节点）；没有孩子的节点叫叶子。看家族谱就懂啦：太爷爷是根，下面有爷爷、爸爸、你——你还可以有自己的孩子，越分越多。

🗂️ 生活类比：电脑里的文件夹树

打开电脑的「我的文档」，里面装「照片」文件夹，照片里又装「暑假」「生日」两个小文件夹，小文件夹里才是文件。「我的文档」就是根，「暑假」文件夹是它的子孙，文件是最底下的叶子。文件管理器画出的就是一棵倒着的树！

💡 口诀：树倒着长，根在顶、叶在底；一层一层往下分，永远不绕成圈。

🧪 读代码：树的一个节点怎么记？

看得懂就好，不用背——用四年级学的指针，把「左孩子、右孩子」的门牌号记下来：

struct Node {
  int val; // 自己放的数据
  Node* left; // 指向左孩子的门牌号
  Node* right; // 指向右孩子的门牌号
};

💡 口诀：节点像小盒子，除了装自己，还要记住左孩子和右孩子住在哪。

🚶 遍历：把树从头到尾逛一遍

想把这棵树里每个节点都看一遍，就叫遍历。最常用的三种叫法记在「根」放哪里：

🔤 前序 / 中序 / 后序

· 前序：先看根，再看左，最后看右（根左右）。
· 中序：先看左，再看根，最后看右（左根右）。
· 后序：先看左，再看右，最后看根（左右根）。

💡 口诀：前中后看的是「根」的位置——根在前叫前序，根在中间叫中序，根在最后叫后序。

🆚 小例子：根 A，左孩子 B，B 又有左孩子 D；根 A 还有右孩子 C

· 前序（根左右）：先 A，再钻进左子树 B，B 又先自己再 D，最后回来看右 C → A B D C
· 中序（左根右）：先 D，再 B，再 A，最后 C → D B A C
· 后序（左右根）：先 D，再 B，再 C，最后 A → D B C A

💡 口诀：每个小树都按同一句口诀来，先把自己这个小树处理完，再往外走。

🧱 完全二叉树：站队整整齐齐，不许跳空

想象老师带全班站队拍合照：先站第一排，一排满了才站第二排，每一排都从左边开始挨着站，中间绝不空位——这样站出来的队形叫完全二叉树。程序里它常用来当「优先级队列」的底层（六年级下册会见到）。

🆚 易混对比：完全二叉树 vs 满二叉树

· 满二叉树：每一层都站得满满当当，一个空位都没有，是最「完美」的队形。
· 完全二叉树：允许最后一层没站满，但必须从左边一个挨一个站，不能右边站了左边空。
满二叉树一定是完全二叉树；完全二叉树不一定是满二叉树。

💡 口诀：满=每层全满；完全=从上到下、从左到右，一层满了才站下一层。

🗂️ 二叉排序树：左边小、右边大，像会自我整理的抽屉

二叉排序树（也叫二叉搜索树 BST）有一条铁规矩：每个节点左边的孩子都比它小，右边的孩子都比它大。放数字时，比它小就往左钻，比它大就往右钻。因为一直这样排，最后用中序遍历逛一遍，吐出来的数字正好从小到大！

🧪 读代码：在二叉排序树里找 35

看得懂就好，不用背——像查字典一样一路问「比根大还是小」：

int find(Node* root, int x) {
  if (!root) return -1; // 找空了，没找到
  if (x == root->val) return x; // 正好等于根，找到！
  if (x < root->val) // 比根小
    return find(root->left, x); // 到左边找
  return find(root->right, x); // 比根大，到右边找
}

每次都能丢掉一半方向，所以找得很快。四年级学的二分查找也是这个思路——每次砍一半。

💡 口诀：左小右大不乱放；中序一逛，小到大排排站。

⚖️ 哈夫曼树：让常客住得离根近，总路程最短

哈夫曼树是一棵会「省力气」的树。给每个字符一个「重量」（它出现多少次），出现越多的字符，越要放在离根近的地方；出现越少的，放得越远。这样整棵树从根到所有叶子的带权路径长度最小——就像超市把最畅销的牛奶放在收银台最近的位置，顾客拿得最快。

🛒 生活类比：超市货架摆位

牛奶人人都买，放在进门第一排；榴莲只有少数人买，放在超市最里面。每个人逛超市走的总路程就最短。哈夫曼树做的就是这件「把常客放近处」的数学安排，后面学哈夫曼编码时会用到它。

💡 口诀：谁出现多谁靠根近；整棵树的带权总长就最短。

🎯

闯关小锦囊 · 考点提醒

树倒着画：根在顶、叶在底、一层层往下分，不绕成圈。
遍历三兄弟：前序=根左右、中序=左根右、后序=左右根，看「根」放哪。
完全二叉树：从上到下、从左到右挨着站满，不许跳空；满二叉树一定完全。
完全二叉树用数组按层序存：根在下标 0 时，下标 i 的左孩子是 2i+1、右孩子是 2i+2。
二叉排序树：左小右大，中序遍历结果就是从小到大。
哈夫曼树：出现多的靠根近，整棵树的带权路径最短。

🎮

学完了？来闯关！

下面 16 个小挑战，点一点就能玩

Demo 原型 · 每个知识点独立页面 · 暂不含真实编译与进度存储。