树系列第 1 篇：从数组、链表到树——为什么我们需要层次结构

嘿，朋友，欢迎来到”树系列”的第一篇文章。

在正式动笔之前，我想先和你确认一件事：你不需要任何基础。哪怕你只听说过数组是”一排数据”，链表是”一个接一个”，哪怕你连这两个词都没见过，也完全没关系。这一篇我会从你最熟悉的场景出发，一步一步陪你把”树”这个概念”长”出来。你只需要带着好奇心，像听朋友讲课一样往下读，读到哪里卡住了，就在哪里停一停，想一想，再继续。

先问你一个特别普通的问题：你的电脑里，文件是怎么组织的？你打开”此电脑”，看到 C 盘、D 盘；点开 C 盘，里面是一堆文件夹；点开”用户”，里面有”桌面""文档""下载”；点开”桌面”，里面又有几十个文件。你有没有发现，这种”文件夹套文件夹、一层又一层”的结构，和你家族里”爷爷生爸爸、爸爸生我”的结构特别像？这种结构，就是今天的主角——树。

接下来的二十篇文章，我们会把”树”这个家族从头到尾看个遍：从最基本的术语，到二叉搜索树、红黑树、堆、字典树、B 树，再到线段树和实战项目。你会看到，树不只是教科书上的一个章节，它是整个计算机世界的骨架之一：文件系统用它，网页浏览器用它，数据库用它，编译器用它，搜索引擎也用它。学会了树，你再看很多”高级”话题，会突然觉得它们都亲切起来了。

在出发之前，先给你一个阅读指南。每一篇文章我会尽量做到三件事：第一，从问题出发，先让你感受到”为什么要这个东西”，再讲”它是什么”；第二，每个新术语第一次出现时，我都会用大白话解释，绝不让你一边读一边翻字典；第三，每篇结尾都有小结和练习题，练习题一定要动手做，哪怕只做一道，也比只看不做强十倍。

好，我们正式开始。第一篇的路线是这样的：先回忆两个老朋友——数组和链表，看看它们各自擅长什么、不擅长什么；然后去生活里转一圈，你会发现树无处不在；接着给树下一个朴素的定义，再看它到底帮我们解决了什么问题；最后预告一下整个系列二十篇的路线图。

第 1 章 我们的起点：数组——排成一排的储物柜

让我们从一个最简单的场景开始。

假设你开了一家小小的奶茶店，想把今天卖出的每一杯奶茶的价格记下来。最自然的做法是什么？找一张纸，从上往下写：第一杯 12 元，第二杯 15 元，第三杯 13 元……写完一列，你还能数一数一共卖了多少杯。这张”从上往下写”的纸，就是程序员眼里最基础、最常用的数据结构——数组。

1.1 数组是什么：一排带编号的柜子

数组，说穿了就是一组排好队的数据，每个数据占据一个带编号的位置，编号从 0 开始。你可以把它想象成火车站旁边的那种储物柜：几十个小柜子并排站成一排，每个柜门上都贴着号码，0 号、1 号、2 号……每个柜子里放一样东西。

为什么编号从 0 开始，而不是从 1 开始？这里有个小故事：在计算机内部，数组就是一段连续的内存，编号其实表示”距离第一个柜子有多远”。第 0 号柜子就是第一个柜子，第 1 号柜子紧挨着它，第 2 号柜子再往右一格。从 0 开始数，恰好和”偏移量”对上，程序写起来最直接。你现在不需要记住这个原因，只需要习惯它，就像习惯”星期日”不是一周的第一天一样。

在 JavaScript 里，数组长这样：

// 一杯杯奶茶的价格，按卖出顺序排好
const prices = [12, 15, 13, 18, 14];

// 想取第 4 杯的价格？直接报编号
console.log(prices[3]); // 18

注意，prices[3] 是第 4 个元素，因为编号从 0 开始。新手在这里几乎都会卡一下，卡完就习惯了，这不算什么大事。

1.2 数组最大的优点：按编号一步到位

数组最让人喜欢的地方，是”随机访问”：只要知道编号，马上就能拿到那个位置的数据，不需要一个个找。

回到储物柜的比喻：你想取 57 号柜子里的行李，不需要从 0 号柜子开始一个一个打开看。你直接走到 57 号柜子前面，掏出钥匙打开就行。柜子们是挨个排列的，57 号柜子就在”第一个柜子往右 57 个位置”的地方，位置是确定的，一步就到。

在计算机术语里，这种”一步到位”的能力叫 O(1) 时间复杂度。O 是英文 Order（阶）的缩写，后面括号里的内容表示”数据量变大时，操作时间增长的速度”。O(1) 的意思是：不管数组里有 10 个元素还是 1000 万个元素，按编号取一个元素花的时间都差不多，几乎可以忽略不计。这个特性极其宝贵，很多程序之所以快，就是因为底层用了数组。

1.3 数组的缺点：插队和离队都要搬家

可惜，天下没有十全十美的数据结构。数组最大的毛病是：在中间插入或删除一个元素，代价非常大。

想象一排已经塞满行李的储物柜，10 个柜子都有主了。这时候来了一个客人，想把自己的箱子塞进 3 号柜子。3 号柜子已经有东西了，怎么办？你只能把 3 号柜子里的东西挪到 4 号柜子，再把原来 4 号柜子的东西挪到 5 号柜子……一路挪到最后一个柜子，才能腾出 3 号柜子。如果柜子有 100 万个，你就得挪 100 万次。

删除也是一样的麻烦：删掉 3 号柜子里的东西，4 号、5 号……一直到最后一个，全都要往前挪一位，把空位补上。所以数组是”取东西飞快、改动非常费劲”的典型。

程序员给这种”数据越多、操作越慢”的现象起了个名字，叫 O(n)：n 表示数据的数量，O(n) 表示操作时间随着 n 成正比增长。数据翻一倍，时间也翻一倍；数据有一百万，最坏就要搬一百万次。后面你会频繁见到这个符号，现在先有个感觉就行。

1.4 数组还有一个更隐蔽的问题：它天生是”平”的

前面两个缺点——插入删除慢——虽然麻烦，但程序员有办法绕开（下一章讲的链表就是为此发明的）。但数组还有一个更深的问题：它只能表达”前后顺序”。

想一想，数组里第 3 个元素和第 7 个元素之间是什么关系？答案仅仅是”第 3 个在第 7 个前面”。不管数组里装的是奶茶价格、学生名字还是文件夹，元素之间只有一种关系——谁先谁后。

可是现实中，很多数据之间的关系根本不是”谁先谁后”，而是”谁包含谁""谁属于谁”。比如”文档”文件夹里有一个”项目”文件夹，“项目”文件夹里又有代码和配置文件——这是包含关系，一条直线画不出来。又比如你爸爸的爸爸是你爷爷，你爷爷还生了你叔叔——这是血缘关系，同样一条直线画不出来。

数组就像一个只有一条街道的小镇：所有房子只能沿街排开，门牌号是唯一的地址。这样的世界太”平”了，容不下”小区里还有小区”这种结构。计算机科学把”排成一条线”的数据结构统称为线性结构，数组是其中最有名的一员。今天这篇的使命，就是带你从”一条线”走向”一棵树”。

1.5 数组小结：三个关键词

让我们把数组压缩成三个关键词，方便你记住它：连续、编号、搬移。连续，指元素在内存里紧挨着排；编号，指每个元素有固定下标，可以一步定位；搬移，指插入删除时后面的元素必须集体移动。记住这三个词，你就抓住了数组的骨架。

那么问题来了：如果我不想频繁搬移元素，有没有别的办法？有，那就是链表。让我们马上认识它。

第 2 章 链表——手拉手的一队人

数组”搬移”问题的根源在于：所有元素必须紧挨着放。于是程序员想：如果我不要求元素紧挨着，而是让每个元素自己记住”下一个元素在哪里”，不就不用搬了吗？这个想法，就是链表。

2.1 链表是什么：一场寻宝游戏

链表的思想特别朴素。你可以把它想象成一场寻宝游戏：你手里只有一张纸条，上面写着”下一条线索在 3 号房间”；你走到 3 号房间，又找到一张纸条，写着”下一条线索在 7 号房间”；到了 7 号房间，纸条写着”这里是终点”。你不需要知道所有房间的位置，只需要跟着纸条一站一站走下去。

链表里的每一个”房间”，专业叫法叫节点（Node）；每张写着”下一站在哪”的纸条，专业叫法叫指针（Pointer）。节点装着两样东西：自己的数据，以及指向下一个节点的指针。用代码表示，极其简单：

// 链表的节点：一个数据 + 一个指向下一站的箭头
class ListNode {
  constructor(value) {
    this.value = value; // 这个节点装的数据
    this.next = null;   // 下一站在哪里，先留空
  }
}

// 串一条三个节点的链：A -> B -> C
const a = new ListNode("A");
const b = new ListNode("B");
const c = new ListNode("C");
a.next = b; // A 知道 B 在哪
b.next = c; // B 知道 C 在哪

你看，a 只认识 b，b 只认识 c。最后一个节点 c 的 next 是空，表示”到这里就没有了”。整个链表就像一列火车：每节车厢只和前后两节相连，但整列火车可以开得很远。

顺便说一句，数组和链表在计算机里还有一个很直观的区别：数组的元素在内存里是连续的一整块，像一排紧挨着的房子；链表的节点可以散落在内存的各个角落，像一座城市里零散分布的秘密据点，每个据点只告诉你下一个据点的地址。正因为不要求连续，链表才能做到”插入不用搬移”。

2.2 链表的优点：插队只需改两条关系

现在来看链表最得意的地方：插入和删除。

还是奶茶店排队的故事。你排队买奶茶，队伍排得老长。突然你朋友来了，想插到你前面。在”数组版”的队伍里，这等于要把你后面所有人都往后推一个位置，太可怕了。但在”链表版”的队伍里，只需要两步：先让排在你前面的那个人，不再指向你，而是指向你的朋友；再让你的朋友指向你。两条”关系”一改，队伍就排好了，其他人一动不动。

删除也是类似的：想让你身后那个人出列，只需要让前面的人直接指向他后面的人，把他”跳过去”就行。他本人还在原地，但已经没有谁指向他了，他就从逻辑上离开了队伍。

在计算机术语里，链表的插入和删除是 O(1) 的——不管链表有多长，都只需要改动常数个指针，和总长度无关。这是链表送给程序员的礼物：如果你的程序需要频繁地、在任意位置插入删除数据，链表通常比数组合适。比如浏览器里维护”最近访问的页面”历史记录，又比如很多编辑器的”撤销”记录，都是链表的好用武之地。

2.3 链表的缺点：找东西必须从头走

但是，天下没有免费的午餐。链表用”插入删除快”换来了”查找慢”。

你想一想寻宝游戏：如果线索藏在第 57 号房间，你能像数组那样直接报编号瞬移过去吗？不能。你必须从第一张纸条开始，一张一张往下追，走完 56 步才能到第 57 号房间。链表没有”编号”这个概念——节点们散落在各处，你只知道第一个节点在哪，想知道”第几个”节点是什么，只能从头数过去。

所以链表的随机访问是 O(n) 的：链表越长，找一个元素平均要走的步数就越多。数据有一百万个，最坏就要走一百万个节点。这正是数组和链表互相对着干的地方：数组”按位置取”快得离谱，链表”按位置取”慢得离谱。

链表还有个隐藏的麻烦：容易”断”。寻宝游戏的纸条如果弄丢一张，后面的线索就全断了；链表里如果某个指针被错误地改动，后面的节点就再也找不回来了。新手写链表代码，最常见的 bug 就是”丢节点”——改指针的时候先把节点弄丢了。所以链表代码看着短，写对却需要格外细心。

2.4 数组和链表：一对互补的难兄难弟

把数组和链表放在一起看，你会发现它们像跷跷板的两端：

操作	数组	链表
按位置取元素	O(1)，一步到位	O(n)，从头走
在中间插入	O(n)，集体搬移	O(1)，改指针
在中间删除	O(n)，集体搬移	O(1)，改指针
内存布局	连续一整块	分散，靠指针连接
额外空间	基本不浪费	每个节点多存一个指针
适合场景	频繁按位置读取	频繁在任意位置增删

看到没有：数组的优势恰好是链表的劣势，链表的优势恰好是数组的劣势。于是聪明的程序员想：能不能把它们组合起来？当然能，很多高级数据结构（比如哈希表、跳表）都是”组合”思想的产物。但请注意——无论怎么组合，数组和链表都依然是一条”线”：数据之间的关系永远是前后相邻，永远是一条直线。

2.5 线性结构的天花板：一条线装不下世界

现在，让我们退后一步，问一个更根本的问题：生活里的数据，真的都是一条线吗？

你电脑里的文件是一条线吗？不是。C 盘里有”用户”和”Program Files”，“用户”里有”桌面""文档""下载”，“桌面”里又有几十个文件。这是一个”一层套一层”的结构，一条直线装不下。

你的家人是一条线吗？不是。你爸爸有爸爸，你妈妈有妈妈，你有兄弟姐妹，你的叔叔阿姨又有他们的孩子。这更像一棵不断分叉的树。

你要整理的知识是一条线吗？也不是。一个主题下面有多个分主题，每个分主题下面又有更细的点，这就是思维导图的样子。

所以，现实世界至少存在两种截然不同的关系：一种是”先后关系”（时间线、播放列表、排队顺序），一条线就能表达；另一种是”包含/从属关系”（文件夹包含文件、公司管辖部门、父母生育孩子），一条线根本画不出来。

更让程序员头疼的是查找的效率问题。假设你有一个装了一亿条记录的数组，想找其中某一条。最坏的情况下，你得从头比到尾，做一亿次比较。就算计算机每秒能比一亿次，那也要一秒，而真实系统的数据往往远不止一亿条，用户可等不了一秒。如果数据能按照”分叉”的方式组织起来，每次比较都能排除一半的候选者，那一亿条数据最多只需要约 27 次比较——从一亿次到 27 次，这就是树带来的奇迹，我们在第 5 章会详细算这笔账。

现在，你已经知道了线性结构的两大天花板：表达不了层次，搜索不够快。是时候去生活里转一圈了。你会发现，树根本不需要”学”，你早就天天在用。

第 3 章 生活里的树：你早就见过它

接下来的内容，我保证你会看得频频点头，因为这些例子全是你每天接触的东西。我们暂时不背任何术语，只用眼睛和直觉去感受：原来树就在身边。这一章我们会一口气看六个例子：文件系统、公司组织架构、族谱、网页 DOM、思维导图、比赛淘汰赛。看完之后你会发现，树不是计算机发明的新东西，它只是把人类早就习惯的”层次感”变成了程序可以处理的结构。

3.1 文件系统：你最熟悉的树

打开电脑，双击”此电脑”，你会看到 C 盘、D 盘。点开 C 盘，里面是 Windows、Program Files、用户等文件夹。点开”用户”，里面有”桌面""文档""下载”。点开”桌面”，里面是一个个项目文件夹和照片。你发现了吗？这个结构就是一棵倒过来的树：树根在最上面（此电脑或者某个盘），树根长出几个粗壮的大树枝（文件夹），大树枝再长出小树枝（子文件夹），最后挂着许多叶子（文件）。

用 SVG 示意图把它画出来，长这样：

把图里的节点依次连起来，就是一条从根走到叶子的路径：每经过一个斜杠，就从父文件夹进入一个子文件夹，直到最终的文件。 如果你用过命令行，你一定见过这样的路径：`D:\文档\项目\代码\main.js`。这条路本身就是在树上行走的路线图：从根出发，进入"文档"，进入"项目"，进入"代码"，最后到达文件。每一个斜杠，就是往下走了一层。也就是说，你每次在资源管理器里点开一个文件夹，都是在树上爬来爬去，只是你从没意识到。

这里还有一个有意思的语言细节：为什么我们把上一级文件夹叫”父文件夹”，把里面的叫”子文件夹”？因为文件系统本质上就是一棵树，文件夹之间的包含关系就是父子关系。父在上、子在下，一个父文件夹可以有多个子文件夹，但一个子文件夹只有一个直接的父文件夹。这两个词，就是树的语言，我们在下一章会正式介绍。

文件系统树还有一个特点值得留意：它通常很深。你可能见过套了十几层文件夹的”套娃路径”，比如”文档\大学\大三下\课程设计\数据结构\实验三\代码\src\main”。树越深，表示层次越多。也正因为如此，程序员在设计数据结构时总在琢磨怎么让树”矮”一点——这个概念后面会反复出现，因为树的”高度”直接决定了查找要走多少步。

另外，你在命令行里输入 tree 命令（Windows 上有些终端支持），就能看到当前目录的完整”树形图”：文件夹下面缩进排列着子文件夹和文件。那个画面，就是文件系统树最直观的写真。所以下次你再用电脑整理文件，可以悄悄地想：我手里握着的，正是一棵活生生的树。

3.2 公司组织架构：汇报关系的树

第二个例子，随便走进一家公司，墙上往往挂着一张组织架构图。最上面是总经理，总经理下面是研发部、市场部、财务部；研发部下面又有前端组、后端组、测试组；每个组里坐着几名工程师。这张图，也是一棵树。

总经理是树的根，各部门是根的孩子，各小组是部门的子节点，工程师是叶子。汇报关系就是树上的父子关系：工程师向组长汇报，组长向部门经理汇报，部门经理向总经理汇报。公司越大，这棵树就越深、越宽；组织架构调整，本质上就是在对这棵树做”剪枝”和”嫁接”。

组织架构图能帮你理解树的一个奇妙性质：随便拎出树上的一个节点，它和它的所有"手下"合在一起，本身又是一棵完整的树。比如把"研发部"单独拎出来，研发部经理是根，各组是枝干，工程师是叶子。这种"大树里面套小树、小树里面再套更小的树"的性质，计算机科学里叫递归（Recursion）。树是最能体现递归思想的数据结构，后面我们写树的代码时，你会看到代码本身也长成"自己调用自己"的样子。

公司树还提醒我们一个现实：并不是所有关系都适合用树。比如”同事之间互相借东西”这种关系就画不成树，因为关系是网状的、互相交叉的。树只适合”每个节点只有一个上级”的场合。这个特点我们讲完族谱之后会看得更清楚：树之所以能保持清晰，正是因为它规定了一个人只能有一个爸爸。

我们再看一个更古老的例子——军队。古代军队的编制是”军、师、旅、团、营、连、排、班”，一层套一层，每层都有明确的上下级。指挥官从统帅部发出的命令，一级一级往下传达，最后到达每一个士兵。这种指挥链，本质上也是一棵树。你能从任何一本历史书或战争片里找到它的影子。所以你看，“层次”这个需求，从人类组织起大型群体的那天起就存在了，树只是它最标准的图画。

3.3 族谱：血缘的树

第三个例子，不用去公司，也不用开电脑，看看你自己的家就知道了。你的爸爸有爸爸（爷爷），你的妈妈有妈妈（外婆）；爷爷、奶奶生了你爸爸和你的叔叔；叔叔又生了你堂弟。如果把每一代人的关系画出来，你会得到一棵标准的家族树。

注意这棵树的画法和前面两棵有点不一样：爷爷同时连着爸爸和叔叔，奶奶也同时连着爸爸和叔叔。在树的语言里，这非常正常：一个父亲可以有很多孩子，但每个孩子只有一个父亲。这个"每个节点最多只有一个父节点"的约束，正是树区别于更复杂结构（比如图）的关键。如果出现"两个爸爸共同拥有一个孩子"这种关系，那它就不是树，而是一张网了——这个区别我们以后再展开，今天你只需要记住"一人一父"这条铁律。

家族树还给我们带来了几个重要的概念。往上走，爷爷、奶奶、太爷爷、太奶奶，都是你的祖先；往下走，你的孩子、孙子，都是你的后代；和你同一辈分的，比如堂弟、表妹，是你的同辈。你在族谱里从自己往上数，数到第几层，就叫”第几代”。树术语里的”深度""层数”，跟”几代”几乎是一回事——你看，你早就懂树了，只是不知道这些术语而已。

还有一个有趣的问题：为什么叫”族谱树”而不是”族谱线”？因为一个家族会不断开枝散叶：一对夫妻生三个孩子，三个孩子又各自成家生子。如果把”你”当作起点，你往下的后代永远在增加，画出来必然是一棵不断分叉的树。而如果你只看”我爷爷、我爸爸、我”这一条线，那只是一条链，它只能记录”直系”，记录不了”旁系”。树比线多出来的，正是”同一层可以有多个分支”的自由。

3.4 网页 DOM：浏览器里的树

第四个例子稍微专业一点，但你每天都在用——网页。当你打开任何一个网页，浏览器都会把网页的内容组织成一棵树，这棵树有个专门的名字，叫文档对象模型，英文缩写是 DOM（Document Object Model）。

这是什么意思呢？网页是用 HTML 写出来的，而 HTML 本身就是层层嵌套的：<body> 里面装着 <div>，<div> 里面又装着 <h1> 标题和 <p> 段落。浏览器拿到 HTML 之后，把这层层嵌套翻译成一棵树，好让程序知道”谁在谁里面”。你可以按 F12 打开开发者工具，随便点开一个网页，看看 Elements 面板——你看到的那个可以一层层展开、收起的结构，就是一棵 DOM 树。

为什么浏览器要费劲建这么一棵树？因为"谁包含谁"这个信息太重要了。你想给"段落一"的文字加红色，你得先知道它在哪个 `div` 里面；你想让弹窗覆盖整个页面，你得知道它该挂到 `body` 下的什么位置。CSS 的选择器（比如 `div p` 表示"div 里的 p"）、JavaScript 的 `document.querySelector`，本质上都是在树上"找节点"。可以说，不懂树，你就永远只是"会用"网页，而不是"懂"网页。

更有意思的是，DOM 树是可以”活”的：JavaScript 往页面里加一个元素，本质上就是在 DOM 树的某个节点下面”长”出一个新节点；删掉一个元素，就是把这根树枝连根剪掉。前端工程师每天做的事情，一半是在和这棵树打交道。所以树这一系列文章，对写网页的朋友来说不是选修课，而是必修课。

3.5 思维导图：大脑里的树

第五个例子，是思维导图。不管你是学生还是上班族，大概率用过或者至少见过思维导图：一张纸的中央写着一个主题，从主题伸出几条粗粗的主干，写着”是什么""为什么""怎么做”；每条主干再长出分支，分支上还可以再长小分支；最末端是一些具体的词条。

比如说，“如何学好数据结构”这张思维导图可以这样画：中心是”学好数据结构”；伸出三条主干，分别叫”概念""刷题""复习”；“概念”下面分出”数组""链表""树""图”；“刷题”下面分出”每日一题""专题训练""错题复盘”；“复习”下面分出”周总结""画知识图谱”。你看，这就是一棵标准的树：主题是根，主干是孩子，分支是孙子，最末端的小词条是叶子。

为什么人类整理复杂信息的时候，天然就喜欢这种”总分”结构？因为大脑处理信息的方式本来就是分层的：先抓住一个中心，再一层层展开细节。上课记笔记是这样，做项目规划是这样，写文章列提纲还是这样。树不是计算机发明的，它是人类思维方式的投影。这也是为什么学会树之后，你会觉得很多领域一下子都通了——因为你终于给这种早已熟悉的思维模式找到了一个精确的、可计算的形状。

思维导图还给我们一个启发：树可以是”画出来的”，也可以只是”想出来的”。你不需要真的在纸上画一棵树，只要你的脑子里有一个”中心、分支、再分支”的结构，你就是在用树的思维方式思考。程序员写代码时，经常在脑子里画这种树，只是把它叫做”结构”或者”层级”而已。

3.6 比赛淘汰赛：对抗的树

最后一个生活例子，足球世界杯。32 支球队先踢小组赛，进入淘汰赛阶段后：16 强赛、8 强赛、4 强赛、决赛，最后只有一个冠军。如果把整个淘汰赛程画出来，它也是一棵树：决赛在最上面，是树的根；决赛的两个参赛者是它的两个孩子；再往下一层，是四分之一决赛的四个胜者；最下面，是 32 支参赛队伍，也就是 32 片叶子。

别小看这个例子，它藏着树的两个重要秘密。

第一个秘密是”边数”：32 支球队参加单败淘汰赛，一共要踢多少场才能决出冠军？每场比赛恰好淘汰一支球队，最后只剩一个冠军，所以一共淘汰了 31 支球队，也就是要踢 31 场。推广到一般情况：n 个节点的树，恰好有 n-1 条边。这个规律看起来平平无奇，但后面我们推导树的很多性质时都要用到它，你先记住”节点比边多一个”这句话。

第二个秘密是”效率”：每一轮淘汰赛，参赛队伍的数量都减半。32 支球队，第一轮变 16，第二轮变 8，第三轮变 4，第四轮变 2，第五轮决出冠军——只需要 5 轮。而 5 正好是 32 取以 2 为底的对数，也就是”32 连续除以 2，除以几次能变成 1”的答案。这个”每层减半”的思想，正是后面二叉搜索树能飞快查找的根源：每走一步，都排除一半的可能性。现在你只要在脑海里留一个印象：树的分叉越多，每次决策排除的候选者就越多，查找就越快。

3.7 六个例子，一个骨架

现在，让我们把六个例子摆在一起，仔细端详一下：

• 文件系统：盘符是根，文件夹是枝，文件是叶子。
• 公司组织架构：总经理是根，部门是枝，员工是叶子。
• 族谱：祖先是根，父母是枝，你是叶子（在你还没有孩子的时候）。
• 网页 DOM：html 是根，标签层层嵌套。
• 思维导图：中心主题是根，主干和分支层层展开。
• 淘汰赛：冠军是根，每轮比赛层层选拔。

它们长得完全不一样，但骨架完全一致：都有一个起点，专业说法叫根；从根往下分出一些分支，分支再往下分；越分越细；最后是末端，叫叶子。而且注意，所有例子都有一个共同点：每个”孩子”都只有一个”爸爸”——每个文件只属于一个父文件夹，每个员工只有一个直接上级，每个人只有一个生父。这个”一人一父”的规矩，让整棵树永远清清楚楚、不打架。

3.8 怎么从生活里”认出”一棵树：四步法

看了这么多例子，你可能会想：道理我都懂，可遇到一个陌生的场景，我怎么判断它是不是树呢？我送你一套四步法，以后遇到任何”关系型”的问题，都可以拿出来用。

第一步，找起点：这个结构里，有没有一个”最上面""最根源”的东西？文件系统的”此电脑”、公司的总经理、网页的 html 标签、思维导图的中心主题，都是起点。如果找不到这样的起点，或者有多个互不相干的起点，那它可能不是一棵树，而是多棵树（这种多棵树并存的形态，有个专门的名字叫”森林”，第 2 篇会提一句）。

第二步，找父子：每个元素是不是都清清楚楚地属于某个”上级”？文件属于一个文件夹，员工属于一个部门，节点属于它的父节点。如果某个元素有两个互不相关的上级（比如一个文件同时挂在两个不同的文件夹下面），那它就不是树，而是图或者其他结构。

第三步，看方向：关系是不是只朝一个方向流动？从根出发，一路往下，只能越走越深，不能绕一圈又回到自己头上。换句话说，树里不能有”环”。如果你发现顺着关系走，走了一圈还能回到起点，那它一定是图，不是树。

第四步，看末端：这个结构有没有”到头了”的地方？文件系统的文件、公司的基层员工、族谱里还没有孩子的那一代，都是末端。如果没有末端，说明每一层都永远往下套，这种结构在现实里几乎不存在；有末端，才符合”树有叶子”的样子。

我们拿几个新例子练练手。

第一个：图书馆的分类。中国图书馆分类法把图书分成二十二个大类，每个大类下面又有二级类目、三级类目，最后是一本本具体的书。起点是”全部图书”，父子关系是”大类包含小类”，末端是具体的书。毫无疑问，这是一棵树。你去图书馆找书时看到的”索书号”路径，和电脑里的文件路径本质上是一回事。

第二个：电商网站的商品分类。“数码”下面有”手机""电脑""耳机”，“手机”下面又有”华为""苹果""小米”。这也是树。而且电商的分类树是真实代码里的树——前端菜单、搜索筛选、后台的类目管理，全是围着这棵树转。

第三个：行政区划。国家下面有省，省下面有市，市下面有区县，区县下面有乡镇。这也是树。你填收货地址时选的那一串下拉框，就是在这棵树上逐层下钻。

再来看两个反例。第一个反例：地铁线路。一号线、二号线互相交叉换乘，一个站点可以属于多条线路，站点之间的关系有分叉也有汇合，甚至有环线绕一圈回到起点。这不是树，是图。第二个反例：社交网络。你的朋友列表里有张三，张三的朋友列表里也有你，关系互相指向，还可能有共同好友，这也是图。遇到这两种情况，别硬往树上套，树不是万能的，这恰恰是它可爱的诚实之处。

四步法总结成一句话就是：一个起点、一层层分下去、每个孩子只有一个爸爸、最后都有叶子。只要四个条件同时满足，你就可以放心地说：这是树。

恭喜你，你已经凭直觉认识树了。接下来的第 4 章，我们把这些生活词汇翻译成计算机科学里的正式术语。你会发现，术语一点都不吓人，它们只是给老朋友起的正式名字。

第 4 章 树到底是什么：从直觉到定义

前面我们一直在用”树枝""叶子""根”这些生活词汇。现在，是时候把它们翻译成计算机科学里正式的术语了。别紧张，术语只是给老朋友起个正式名字，一个都不难。

4.1 一张图看懂树的全部零件

假设我们要记录一个学习小组的组织方式：组长小美，下面有算法组和前端组两个方向；算法组有阿强和小刚，前端组有小丽和小楠。画出来就是这样一棵树：

看这棵树，我们来认零件。

节点：树上的每一个”小圆点”都叫节点（Node）。小美是节点，阿强是节点，小楠也是节点。节点是树的基本单位，它装着数据——可以是一个名字、一个数字、一个文件，也可以是任意对象。

边：连接两个节点的那条线叫边（Edge），也叫分支。边表示两个节点之间有关系：小美和算法组之间有边，表示”小美管着算法组”；爸爸和你之间有边，表示”爸爸生了你”。没有边，节点就只是散落的孤点；有了边，它们才连成一个整体。

根：最上面那个节点叫根（Root），它是整棵树的起点，没有父节点。就像文件系统里的”此电脑”，或者公司里的总经理。一棵树有且只有一个根。为什么叫”根”而不是”顶”？因为计算机科学里的树习惯”倒着画”：根在上面，枝叶朝下长。你在生活里画树是根在下面，但程序员画树、写代码时，几乎都让根在顶部。这是一种约定，习惯了就好。

父节点和子节点：有边直接相连、并且更靠近根的那一个叫父节点（Parent），另一个叫子节点（Child）。小美是算法组的父节点，算法组是小美的子节点。注意”直接相连”四个字：小美和阿强虽然也在同一条路上，但中间隔着算法组，所以小美不是阿强的父节点，而是阿强的”祖先”。

祖先和后代：顺着边往上走能到达的节点，都是你的祖先（Ancestor）；顺着边往下走能到达的节点，都是你的后代（Descendant）。对小楠来说，前端组和小美都是祖先；对前端组来说，小丽和小楠都是后代。

兄弟节点：有同一个父节点的节点互称兄弟（Sibling）。算法组和前端组都是小美的孩子，所以它俩是兄弟；阿强和小刚也是兄弟。

叶子：没有子节点的节点叫叶子（Leaf），也叫叶节点。阿强、小刚、小丽、小楠都是叶子。叶子通常是”末端”，就像文件系统里的文件，或者族谱里还没有孩子的那一代。

内部节点：有子节点的节点叫内部节点（Internal Node）。它既是别人的孩子，又是别人的父母。算法组、前端组、小美都是内部节点。整棵树里，除了根以外的内部节点都”上有老下有小”。

子树：树上任何一个节点，连同它所有的后代，构成一棵”小树”，叫子树（Subtree）。比如”算法组”连同阿强和小刚，就是一棵以算法组为根的子树。这是树最重要的递归性质：树由一棵根和若干棵子树组成，而子树自己也是树。你可以把子树理解成”从树上剪下来的一根完整树枝，它自己仍然是一棵小树”。

层数和深度：根在第 1 层（有的教材从第 0 层开始，别被吓到，只是约定不同）；根的孩子在第 2 层；再往下依次类推。一个节点的深度（Depth），就是从根到这个节点所经过的边的条数。比如小美深度是 0，算法组深度是 1，阿强深度是 2。

高度：一个节点到它最远叶子的距离叫高度（Height）。整棵树的高度，就是树最长的那条路线有多长。深度是”从根往下数”，高度是”从下往上数”，方向相反，初学者最容易搞混。这里你先记住方向，第 2 篇我们会专门把它们掰开揉碎讲清楚。

你看，这些术语没有一个超出”家谱”和”文件夹”的范围。你只要记住”父、子、兄弟、祖先、后代、叶子”这几个词，树的术语就已经掌握一半了。

4.2 树 vs 线性结构：一张对比表

现在我们手里有两类结构：数组、链表这类线性结构，和树这类层次结构。把它们放一起对比，你会看得更清楚：

对比维度	数组	链表	树
形状	一条直线	一条链条	分叉的层次
节点之间的关系	只有前后	只有前后	父子、兄弟、祖先、后代
能否表达”包含关系”	不能	不能	天生擅长
按位置随机访问	O(1)，一步到位	O(n)，从头走	视树的类型而定
中间插入/删除	O(n)，集体搬移	O(1)，改指针	通常与树的高度有关
数据变多时查找	越来越慢	越来越慢	设计得好时接近对数级
适合的场景	顺序数据、频繁按位置读取	频繁增删的序列	层次数据、快速查找

表格里出现了 O(1)、O(n)、O(log n) 这些符号，我们简单解释一下：它们描述的是”数据量变大时，操作时间怎么变”。O(1) 表示不管数据多少，时间几乎不变；O(n) 表示数据翻倍，时间也翻倍；O(log n) 表示数据翻倍，时间只增加一点点。现在你不需要精确理解，只要建立这个感觉：O(1) 最好，O(log n) 也很好，O(n) 一般，O(n²) 就要小心了。这些符号是数据结构领域的”通用语言”，后面的文章我们会反复用到。

4.3 一句话预告：树是图的一种特殊情况

如果你听说过”图”（Graph），我提前给你打个预防针：树是图的一种，只不过树有两条严格的规矩——每个节点最多只有一个父节点，而且整个结构必须连通、不能有环。这两条规矩保证了树永远”不打架”：从根到任何一个节点，有且只有一条路。也正是因为这一条路，树才能被高效地搜索。

如果你还没听说过图，直接把这一小节跳过，不影响阅读。我们以后讲到图的时候，还会回头和树做对比。

4.4 用代码给树拍一张”身份证”

讲了这么多术语，你可能会问：树在程序里到底长什么样？我们以最常用的二叉树为例，看看它的”身份证”。

一段极简的 JavaScript 代码就够了：

// 二叉树节点：一个数据 + 左孩子 + 右孩子
class TreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;  // 左孩子，先留空
    this.right = null; // 右孩子，先留空
  }
}

// 手动搭一棵小树：2 是根，左边挂 1，右边挂 3
const root = new TreeNode(2);
root.left = new TreeNode(1);
root.right = new TreeNode(3);

你有没有发现，这段代码和第 2 章链表的节点代码几乎一模一样，只是把 next 换成了 left 和 right？这说明什么？说明树的代码一点都不神秘，它只是”节点 + 指针”的另一种排列方式：链表每个节点有一个 next，二叉树每个节点有两个孩子指针，多叉树每个节点有一个装着很多孩子的数组。整个树家族的代码，本质上是同一套零件（节点和指针）的不同组装方式。

再看一眼我们是怎么搭树的：先造一个根节点，再把新的节点挂到根的左边或右边。这个动作有个专门的词，叫”建树”，也叫”构造树”。你每次写 root.left = new TreeNode(1)，就是在让树长出一根新枝。等你读到第 3、4 篇，我们还会学会怎么从零长出一整棵大树；到了第 5、6 篇，再学会怎么把树完整地走一遍——那将是你的第一个”树的算法”。

顺便说一个很多初学者会困惑的点：代码里的树，真的像示意图那样”长”在屏幕上吗？不是的。树在程序里只是内存中的一堆对象，靠引用互相连接，并没有可见的形状。你在调试器里看到的可以展开、折叠的树形视图，只是调试工具顺着引用关系画出来的示意图。所以，判断一棵代码里的树长什么样，不要靠想象，而要靠”从根出发，顺着 left、right 或者 children 走一遍”。这个”走一遍”的动作，就是下一篇文章要讲的”遍历”——它是所有树算法的起点。

第 5 章 树的价值：它到底帮我们解决了什么

认识了树的样子，现在回答最关键的问题：树到底好在哪？为什么全世界的数据结构教科书，都要花大量篇幅讲树？我认为，树的三大价值可以浓缩成三句话：表达层次、加速查找、组织数据。我们一条一条说清楚。

5.1 价值一：表达层次，让”包含”和”从属”一目了然

第一种价值最直白：世界上的很多数据天生就有层次，而树是表达层次的最自然方式。

想象一下，如果不用树，你怎么在程序里表达一个文件夹系统？最笨的办法，是给每个文件夹和文件都记一条”路径”字符串，比如 D:/文档/项目/main.js。这种办法能用，但非常脆弱：我想列出某个文件夹下的所有文件，就得把所有路径翻一遍，找出以这个前缀开头的；我想把”项目”文件夹整体改名为”工程”，就得把所有路径挨个改一遍；我想知道两个文件是不是在同一个文件夹里，又得反复比较字符串。麻烦不麻烦？

如果用树来表达，一切都变得顺理成章：文件夹是节点，父子关系就是”包含关系”。想列出子文件？直接看这个节点的孩子列表。想整体改名？改一个节点的名字就够了，所有子孙自动”换了路径”。想判断归属？顺着父节点往上走两步就到。数据结构和问题本身对齐了，代码自然就简单了。

打个比方：树就像一张地图，而路径字符串就像一段”从 A 出发走 200 米、左转、再走 100 米”的文字描述。地图本身是道路的层次结构，你想去哪里都能重新规划；文字描述则是一次性的，路况一变就废了。树给程序带来的，正是这种”结构化的、可重用的”表达力。

同样的道理适用于公司架构、商品分类、网页元素、语言语法。举一个程序员都绕不开的例子：你写的每一行代码，在编译器眼里都不是一串字符，而是一棵树——抽象语法树（Abstract Syntax Tree，简称 AST）。比如 1 + 2 * 3 会被解析成一棵”乘号是根、左边是 2、右边是 3，加号是更大的根、左边是 1、右边是那棵乘号子树”的树。编译器之所以要费劲造这棵树，就是为了明确表达”先算 2*3，再加 1”这个层次关系。没有树，程序连”运算顺序”都没法表达。这个系列会从数据结构的角度把树讲透，等你以后再看到编译器里的 AST、浏览器里的 DOM，就会多一层”老朋友重逢”的亲切感。

所以，只要你的问题里有”整体包含部分、大类包含小类”的结构，树就是最贴合的答案。这不是喜好问题，而是”数据形状”决定的：一条线的数据用线性结构，一层套一层的数据用树。

5.2 价值二：加速查找，二叉搜索树的预告

第二种价值，是树最让程序员兴奋的地方：它能让查找快得离谱。这一节是全文的重头戏，我会带你亲手算一遍，让你亲眼看到”从一亿次到三十次”是怎么发生的。

我们先回忆一下数组查找的困境。一个排好序的数组 [1, 3, 5, 7, 9, 11, 13, 15]，让你找 13，你会怎么找？正常人当然不会从头看到尾，而是先看中间的数——7。13 比 7 大，说明目标在右半边；再看右半边的中间——11。13 比 11 大，说明目标还在右边；再看 13——找到了。三次比较就搞定。这个技巧叫二分查找，它的核心思想是：每次比较都排除掉一半候选者。

二叉搜索树（Binary Search Tree，简称 BST）就是把二分查找”物化”成一棵树。它的规矩特别简单：每个节点最多有两个孩子，一个左、一个右；左子树里的所有节点都比父节点小，右子树里的所有节点都比父节点大。于是，查找一个数就变成了一场走迷宫：从根出发，目标比当前节点小就走左边，比当前节点大就走右边，每次迈出一步，搜索范围就砍掉一半。

在这棵树上找 6：8 比 6 大？走左边。3 比 6 小？走右边。到了 6——找到了，两步半。如果这是一棵"身材匀称"的树，查找任何一个数都只需要大约"树的高度"那么多次比较。而一棵有 10 亿个节点的平衡树，高度只有大约 30，意味着最多 30 次比较就能找到目标。对比数组线性扫描的最坏 10 亿次比较，这是天壤之别。

让我再给你算一笔更直观的账。假设图书馆有 100 万本书，每本书有一个唯一的编号，编号是排好序的。用数组顺序查找，平均要比较 50 万次；用二叉搜索树查找，最多只需要 20 次（因为 2 的 20 次方约等于 100 万）。从 50 万次到 20 次，这就是树的力量。数据库索引、搜索引擎、路由表这些”必须快”的系统，底层几乎都离不开树，原因就在这里。

当然，二叉搜索树有个小脾气：如果插入的数据恰好是排好序的，比如依次插入 1、2、3、4、5，树就会退化成一棵”歪脖子树”，变成一条斜线，查找又回到 O(n)。怎么防止退化？这就是第 9、10 篇的 AVL 树、第 11、12 篇的红黑树要解决的问题。今天你只需要记住一个结论：树的效率来自”分支”——有分支，才有”每次排除一半”的机会。

5.3 价值三：组织数据，让程序世界和现实世界对齐

第三种价值听起来有点”虚”，但其实是前两种的合体：树是现实世界在计算机里的投影，它让程序员可以按照人类的思维方式去组织数据。

想想你手机里的”设置”应用：一级菜单是”网络与连接""显示与亮度""电池""存储”；点进”网络与连接”，又有”Wi-Fi""蓝牙""飞行模式”；点进”Wi-Fi”，才是具体的网络列表。这种菜单就是一棵树。产品经理这么设计，不是因为树很酷，而是因为用户的大脑就是这么组织的：先大类，再小类，最后是具体项。程序里的菜单、导航、商品分类、权限体系，几乎都是树。

再看看更底层的地方：操作系统管理内存，用的是树；数据库管理索引，用的是 B+ 树；编译器分析代码，用的是抽象语法树；路由器转发数据，查找的是树状的路由表；人工智能里的决策树、随机森林，名字里就带着”树”；甚至你玩过的游戏，AI 的”行为树”决定着一个角色什么时候该进攻、什么时候该逃跑。树不是某个领域的偏方，它是整个计算机世界的基本骨架之一。

所以学树，学的不只是一堆数据结构，更是一种”如何思考复杂关系”的方式。当你遇到一个新问题，如果发现里面有”一层套一层""大类管小类”的结构，你的第一反应就应该是：这里是不是可以用一棵树？这种条件反射，就是这一系列文章想送给你的礼物。

5.4 树的代价：没有免费的午餐

讲了这么多树的好处，我想诚实地给你泼一盆温水：树不是万能的，它也有自己的代价。了解代价，你才不会在面试里、在真实项目里盲目”为了树而树”。

第一个代价是空间。树的每个节点除了存数据，还要存指向孩子的指针（或者一个装着孩子的数组）。数据量小的时候无所谓，但如果有十亿个节点，每个节点多存两个指针，那就是几十 GB 的额外开销。所以工程上经常用”紧凑”的存储方式，比如把树放进数组（堆就是这么干的，第 16 篇会看到），或者用磁盘友好的 B 树。

第二个代价是实现复杂度。数组的插入删除虽然慢，但代码简单、出错率低；链表和树的代码则要小心处理各种指针，稍不注意就会写出”丢节点""成环”的 bug。初学者写树，十个里有八个栽在”递归忘写终止条件”上。所以”用树”永远是一个权衡：收益是层次和速度，成本是复杂度和空间。

第三个代价是”快”是有条件的。我们前面说二叉搜索树查找是”约三十次比较”，前提是树长得匀称。如果数据恰好有序插入，树退化成一条斜线，“约三十次”就会变回”约十亿次”。所以真实系统要么精心设计插入顺序，要么使用自平衡树（AVL、红黑树），让树永远保持匀称。这就像健身：树的效率不是天生的，是需要”维持身材”的。

第四个代价是很多场景其实不需要树。如果你的数据只有几百个，顺序查找也无所谓；如果你只需要”按编号取元素”，数组永远是最好的选择；如果你只需要”精确查找某个键”，哈希表（一种靠计算位置而不是比较来查找的结构）往往比树更快——树真正的优势在于”有序性""范围查询""层次关系”，这些才是它的主场。

说这些，不是劝你别用树，而是想让你成为一个”会选型”的程序员：知道每把锤子的长处和短板，才知道什么时候该抡起它。树是一把好锤子，但锤子不负责解决所有问题。

第 6 章 树的常见形态预览：原来树有这么多亲戚

说了这么多树的好处，你可能会想：那树是不是只有一种？当然不是。树是一个大家族。今天这一章，我们就像逛动物园一样，远远地看一眼几位著名的”亲戚”。别急着深入研究，后面每一篇都会专门招待它们。这一章的目标只有一个：让你知道”树”这个家族有多丰富，以及每种树大概解决什么问题。等你以后读到对应的篇目时，会有一种”老朋友重逢”的亲切感。

6.1 二叉树：最流行、最基础的树

第一种是二叉树（Binary Tree）。规则一句话：每个节点最多有两个孩子，而且分左右——左孩子和右孩子。为什么”二”这么特殊？因为”二”是最小的分支数，却又足够表达”二分”的决策：向左还是向右，大还是小，是还是否，真还是假。前面提到的二叉搜索树，就是二叉树的一种。

二叉树是树家族里被研究得最透彻、面试考得最多、应用最广的成员。你可以把任何多叉树改写成二叉树，这个技巧（左孩子右兄弟）在图形学等领域很常用；很多高级结构（堆、哈夫曼树、线段树）也都是二叉树。所以学树，二叉树是绝对的主角，我们系列的第 3 到第 6 篇都会围绕它展开。

顺便教你一个小知识点：二叉树分”满”和”完全”两种特殊形态。满二叉树是”每一层都长满了”的树；完全二叉树是”最后一层可以缺右边的，但左边必须补齐”的树。这两个词听起来差不多，但定义不同，第 2 篇我们会配图讲清楚，今天先混个脸熟。

6.2 多叉树：更贴近生活的树

第二种是多叉树，也叫 N 叉树。每个节点可以有任意多个孩子。你回头看文件系统、公司架构、DOM，它们其实都是多叉树：一个文件夹下可以有几十个子文件夹，一个 div 里可以套很多个兄弟元素。

多叉树更贴近生活，但”孩子数量不定”也带来一个小麻烦：在代码里，你没法像二叉树那样固定写死 left 和 right 两个指针，而是需要用一个数组来装所有的孩子。比如前端组件树里的 children 数组，就是多叉树在真实代码里的样子。多叉树的代码长这样：

// 多叉树节点：数据 + 一个装着所有孩子的数组
class TreeNode {
  constructor(value) {
    this.value = value;
    this.children = []; // 孩子的数量不固定，用数组装
  }
}

const root = new TreeNode("根");
const child1 = new TreeNode("孩子 1");
const child2 = new TreeNode("孩子 2");
root.children.push(child1, child2); // 根有两个孩子

你看，概念还是那个概念：节点装着数据，指着它的孩子。只是从”两个孩子”变成了”一堆孩子”。这也印证了我们在第 4 章说的递归性质：一棵多叉树由根和若干棵子树组成，而每一棵子树自己又是一棵多叉树。

6.3 堆：会自己排队的树

第三种叫堆（Heap）。它是一棵特殊的完全二叉树，专门用来解决”快速拿到最大（或最小）元素”的问题。

想象一下医院急诊室：病人不断进来，病情有轻有重，医生每次都要先处理最重的病人。如果每次来一个新病人，都把整个队伍重新排一次序，代价太高；如果完全不排序，医生又不知道先救谁。堆就像一个自动维护的优先队列：新病人进来，插入的成本很低；医生需要时，最紧急的病人立刻就能出来，不需要扫描整个队伍。

堆在现实里的应用到处都是：操作系统的任务调度（CPU 先跑优先级高的任务）、网络路由（先转发最紧急的包）、大数据里的”求前 100 名”（TopK 问题）、还有堆排序。我们第 16 篇会专门讲它。这里你只需要记住一句话：堆是一棵”有纪律”的树——每个父节点都比孩子”更优先”（要么更大，要么更小），所以最优先的那个永远在根上。

6.4 字典树 Trie：为字符串而生的树

第四种叫字典树，英文是 Trie，读作”try”，不要读成”tree”。它专门用来存储和查找字符串。

它的思想特别巧妙：不把每个单词当作一个整体存起来，而是把单词拆成一个一个字符，按顺序挂在树上。比如 “cat” 和 “car” 这两个单词，共享前两个字符 c、a，在 Trie 里，它们走同一条树枝，到了第三个字符才分开：一个走 t，一个走 r。这样，拥有相同前缀的单词在树上共享路径，既省空间，又让”前缀查询”变得极快。

你每天在用 Trie 而不自知：搜索引擎的搜索框，你每敲一个字，底下候选词”唰”地更新一次；输入法的联想词；拼写检查器；路由器的 IP 前缀匹配。这些场景的共同点是”以某个前缀开头的所有词”——这正是 Trie 最擅长的查询。我们第 17 篇会亲手实现一个简单的搜索联想。

6.5 B 树：数据库和文件系统的幕后英雄

第五种叫 B 树（以及它的改良版 B+ 树）。它的名字不是”B 级树”的意思，B 的来历有争议，你只需要记住：它是专门为磁盘存储设计的多路搜索树。

为什么需要它？因为普通二叉树在内存里很高效，但数据库的数据存在磁盘上，而磁盘读取一次很慢——比内存慢几万倍。所以数据库里的树要尽量”矮胖”：一个节点里放很多个键，分出很多个孩子，让同样的数据量对应更少的层数，从而减少磁盘读取次数。一棵能存上亿条索引的 B+ 树，高度往往只有三四层，这意味着查询任何一条记录，最多只读三四次磁盘。

MySQL 的索引、文件系统的目录结构、各种 NoSQL 数据库，幕后都是 B 树家族。这一位我们放到系列第 13、14 篇再正式介绍，今天你只需要知道：树家族的”高个子”（二叉树）适合内存，“矮胖子”（B 树）适合磁盘。

6.6 其他值得一提的成员

除了上面五位，树家族还有不少成员：哈夫曼树（文件压缩算法的基础，第 20 篇）、线段树和树状数组（处理区间查询，第 19 篇）、并查集（用树表达”哪些元素属于同一组”，第 18 篇）、红黑树（Java 的 TreeMap、Linux 内核里都在用，第 11、12 篇）、AVL 树（第一种被发明的平衡树，第 9、10 篇）……每一个都有自己的绝活。

6.7 一张速查表：谁是谁，干什么用

逛完动物园，我们做一张速查表。以后你听到任何一个”某某树”的名字，都可以回来查一眼，看看它是谁、干什么用、我们第几篇讲它：

树的种类	核心特点	典型用途	对应篇目
二叉树	每个节点最多两个孩子	一切树的地基	第 3 篇
二叉搜索树	左小右大，查找快	有序数据的查找	第 7、8 篇
AVL 树	自动保持平衡的 BST	需要稳定性能的查找	第 9、10 篇
红黑树	工程里最常用的平衡树	TreeMap、内核调度	第 11、12 篇
堆	父节点永远比孩子优先	优先队列、TopK	第 16 篇
Trie	按字符共享前缀	搜索联想、拼写检查	第 17 篇
并查集	用树表达”同一组”	连通性判断	第 18 篇
哈夫曼树	让高频字符编码更短	数据压缩	第 20 篇
B 树 / B+ 树	又矮又胖的多路树	数据库、文件系统索引	第 13、14 篇
线段树与树状数组	支持区间查询与更新	竞赛、高频面试	第 19 篇

这张表现在看不懂没关系，它更像一张”藏宝图”：你先记住”有这么多宝藏”，等我们一篇一篇挖出来时，再回来对照，会有一种”地图终于对上了”的快乐。

6.8 遇到问题怎么选树：三步决策法

看完成员介绍，你可能会想：那以后我遇到一个实际问题，到底该选哪种树？这里先给你一个”三步决策法”，现在用起来可能还有点生疏，但有了这张图，等你学完整套系列再回来看，会特别有感触。

第一步，先问：这个问题真的需要树吗？如果数据是纯顺序的，用数组或链表；如果只需要精确查找单个键，可以考虑哈希表。只有当你需要”层次关系”或者”有序范围”时，才轮到树出场。这一步能帮你挡掉一半”为了用树而用树”的冲动。

第二步，再问：我需要什么样的操作？只要插入、删除、查找，并且要求稳定快速，优先考虑平衡二叉搜索树（AVL 或红黑树）；只要”最大最小”，考虑堆；只要字符串前缀，考虑 Trie；只要区间统计，考虑线段树或树状数组；如果数据大到要落盘，考虑 B 树家族。

第三步，最后问：我的数据有多大、多乱？几百条数据，任何结构都无所谓，选最简单的；几万条有序插入的数据，记得用平衡树；几亿条存在磁盘上的数据，几乎只有 B+ 树能扛住。数据量，往往是最后拍板的那只手。

这三步现在听不懂没关系，它们更像是给未来的你留的索引。等你学完第 20 篇，再回头看这段，你会发现自己已经能自然地做出这些判断了。

看到这里，你可能会有点眼花：这么多树，学得过来吗？别担心，这正是我们设计二十篇路线图的原因。树的家族虽然大，但它们的共同骨架只有一套——节点、边、父子关系。你只要把这套骨架打牢，剩下的都是往骨架上挂不同的”纪律”和”用途”。下一章，我们就来看这二十篇是怎么安排的。

第 7 章 本系列路线图：接下来 20 篇我们怎么走

决定写这个系列的时候，我给自己定了一个原则：不堆砌术语，不跳过推导，每一篇都让零基础读者能读懂。二十篇听起来很多，但如果你把它分成四个阶段，每一阶段的目标都很清晰。

7.1 第一阶段：基础篇（第 1-6 篇）——把树”扶起来”

这一阶段的目标是：让你彻底搞懂树是什么、怎么表示、怎么走。

第 1 篇（本篇）：从数组、链表到树。理解为什么需要层次结构，建立树的直觉。

第 2 篇：树的基本术语。系统学习节点、边、根、叶子、深度、高度、子树、满二叉树、完全二叉树等概念，把它们变成你的日常词汇。

第 3 篇：二叉树。认识树家族里最流行、最基础的成员：定义、左孩子右孩子、满/完全/完美二叉树，以及节点数与高度的关系。

第 4 篇：树的存储方式。一棵树在内存里到底怎么放？链式、数组与父子表示三种方案，比较读写代价与适用场景。

第 5 篇：深度优先遍历。用递归和栈彻底走通前序、中序、后序，把”走一遍树”变成条件反射。

第 6 篇：广度优先遍历。用队列逐层扫描整棵树，学会层序，并把四种遍历放在一起对比应用。

读完这一阶段，你已经能看懂、写出简单的树代码，并且理解”怎么表示、怎么走”。这一阶段也是后面所有内容的地基，建议一篇都不跳。

7.2 第二阶段：搜索树与平衡篇（第 7-12 篇）——让查找又快又稳

地基打牢之后，我们开始解决树最重要的用途：快速查找。这一阶段从二叉搜索树出发，一路走到自平衡树，理解”树为什么会退化、工程师怎么修正”。

第 7 篇：二叉搜索树。亲手实现查找、插入、删除，理解它为什么快，也理解它为什么可能退化。

第 8 篇：BST 为什么会退化。看升序插入如何把一棵树拉成一条链，搞懂”平衡”到底在解决什么问题。

第 9 篇：AVL 树——旋转与插入。第一个自平衡二叉搜索树：平衡因子、四种旋转、插入修复全流程。

第 10 篇：AVL 树的删除与对比。删除的多次旋转、复杂度分析，以及 AVL 与红黑树的取舍。

第 11 篇：红黑树——五条性质背后的直觉。理解工程里最常用的平衡树为什么”规则宽松”反而更好用。

第 12 篇：红黑树的插入与删除。修复全流程、代码实现与应用场景。

这一阶段是”平衡”的主战场：第 7、8 篇需要第 3 篇的二叉树基础；第 9、10 篇建议先读完第 7、8 篇；第 11、12 篇最好放在 AVL 之后读。

7.3 第三阶段：磁盘、概率与工程结构篇（第 13-15 篇）——走向真实世界

从这一阶段开始，我们不再满足于”认识”树，而是要看树在真实系统里怎么工作。这里每一篇都会解释”为什么真实系统这么选”：每种结构都有自己的场景和代价，学会权衡，比记住结论重要得多。

第 13 篇：从内存到磁盘——为什么需要 B 树。了解磁盘读取和内存读取的巨大差异，以及”矮胖”树是怎么来的。

第 14 篇：B 树操作与 B+ 树。看数据库索引为什么选 B+ 树而不是红黑树，理解”叶子节点串成链表”的巧妙设计。

第 15 篇：跳表。认识概率平衡的层级结构，理解它为什么常被用作有序集合与缓存索引的底层实现。

这一阶段的前置关系：第 13、14 篇建议先学完第 7 篇二叉搜索树；第 15 篇相对独立，读完第 3、4 篇即可。

7.4 第四阶段：进阶应用与总结篇（第 16-20 篇）——让树为你工作

最后一个阶段，我们把学到的树用在算法题和真实项目上。你会发现，前面打下的每一个概念，在这里都会派上用场。

第 16 篇：堆与优先队列。学会用数组实现一棵”看不见的树”，解决”永远先处理最紧急的事”。

第 17 篇：Trie 前缀树。用树处理字符串前缀问题，实现一个简易的搜索联想器。

第 18 篇：并查集。用树表达”元素属于哪个集合”，学会路径压缩和按秩合并这两个经典优化。它看起来不像树，骨子里却是树。

第 19 篇：线段树与树状数组。解决”区间查询、区间更新”这类高频竞赛和面试问题，理解两种区间神器的取舍。

第 20 篇：哈夫曼树、选型指南与系列总结。亲手推一遍最短编码，再站在全局回看：什么时候该用哪种树。

第 16-19 篇主要需要第 3、4 篇的基础；第 20 篇是总结篇，建议至少读完前 18 篇再回头对照。

7.5 给初学者的阅读建议

路线图画完了，我还想唠叨几句实在话。

第一，不要跳着读。至少按顺序读完前 6 篇，因为树的概念是层层叠叠的，第 2 篇的术语会出现在第 3 篇的代码里，第 3 篇的二叉树会出现在第 5、6 篇的遍历和第 7 篇的查找里。跳一篇，后面可能就会有一段读不懂。

第二，练习题一定要动手。只看不练，树的”手感”是长不出来的。尤其是第 7 篇的二叉搜索树，强烈建议你亲手在纸上插入一串数字，画出每一步的树形，再对照答案。纸和笔是学数据结构最好的工具，比任何视频都管用。

第三，遇到看不懂的地方，先放下。大多数”卡住”不是因为你笨，而是因为缺了一个前面的概念。睡一觉，第二天再看一遍，往往会自己解开。这也是我故意把每篇控制在一个主题内的原因：宁可慢，不可乱。

第四，带着问题读。每一篇开头我都会抛出一个问题，比如”为什么数组插入很慢""为什么数据库不用红黑树”。你可以在读之前先自己想一分钟答案，再往下看。这个”先猜后验证”的过程，比被动接收信息有效得多。

如果你已经有基础，想直接查漏补缺，可以按上面的前置关系跳到对应篇目。但我仍然建议你花十分钟把前几篇扫一遍，因为我用的术语和命名可能与你看过的教材略有差异，先对齐再深入，效率反而更高。

7.6 学习工具建议：让树”看得见”

最后，分享几个我亲测有效的学习工具，它们能让抽象的树变得看得见、摸得着。

第一，纸和笔是最好的数据结构工具。每次学一种新树，都亲手画几棵：随机写一串数字，插入成一棵二叉搜索树；随便画一棵多叉树，标出根、叶子、深度。画错没关系，画错的过程正是理解的过程。面试前用纸笔画树，也远比盯着屏幕有效率。

第二，善用在线可视化网站。网上有很多数据结构可视化工具，比如把一串数字喂进去，它能一步步演示二叉搜索树怎么插入、怎么旋转。看动画十遍，不如自己点十次按钮；自己点十次按钮，又不如亲手在纸上画一遍。三样搭配，效果最好。

第三，善用调试器。等你学会写树的代码，调试器里的”监视”面板会把节点的引用关系展开成一棵小树。你可以在每一步操作后暂停，亲眼看看”插入一个新节点之后，树变成了什么样”。这种”亲手操作 + 立刻看到结果”的正反馈，是保持学习动力的秘诀。

第四，给自己建一个”树的词卡”。每学一个新术语，就写一张卡片：术语、一句话解释、一个生活例子、一棵手绘小树。等系列学到一半，你会拥有一叠只属于你自己的”树词典”，复习时成就感拉满。

工具就这些，接下来就看你的了。

小结：今天你带走了什么

让我们把这一篇的内容收进一个背包，看看你都带走了什么。

第一，你重新认识了两个老朋友：数组取东西快、但插入删除要搬移；链表插入删除快、但查找必须从头走。它们都是线性结构，只能表达”前后关系”，既表达不了层次，也快不起来。

第二，你在生活里发现了树：文件系统、公司架构、族谱、网页 DOM、思维导图、比赛淘汰赛，全是树。树的骨架是：一个根，若干分支，层层向下，末端是叶子。

第三，你认识了树的基本零件：节点、边、根、父节点、子节点、兄弟、祖先、后代、叶子、内部节点、子树、深度、高度。它们全都来自”家谱”和”文件夹”的直觉，一点也不神秘。

第四，你理解了树的三大价值：表达层次，让”包含关系”一目了然；加速查找，二叉搜索树能把一亿次比较变成约三十次；组织数据，让程序世界和现实世界对齐。

第五，你预览了树家族的几位成员：二叉树、多叉树、堆、Trie、B 树，还听说了哈夫曼树、线段树、并查集、红黑树。你知道了后面二十篇的路线图，也知道了每篇之间的前置关系。

如果现在有人问你”树到底是什么”，你可以这样回答：树是一种把数据组织成”层次”的结构，它有一个根，向下不断分支，每个节点都清楚地知道自己的父节点和子节点；因为有了分支，我们既能表达”谁包含谁”，又能高效地寻找”某个东西在哪里”。

这句话，就是整个树系列的种子。后面的每一篇文章，都是这粒种子长出来的枝干。

常见疑问：零基础读者最关心的四个问题

写到这里，我猜你可能还有几个小问题堵在心里。我们把它们一次性说清楚。

第一个问题：树和图到底有什么区别？我什么时候该用树，什么时候该用图？简单说，树是”每个人只有一个爸爸”的分层结构，图是”关系可以互相交叉、可以成环”的网状结构。判断标准就一条：如果关系严格单向、分层、无环，用树；如果关系会交叉、会回环（比如地铁换乘、好友关系、地图导航），用图。我们以后会专门讲图，但今天记住这个判断标准，你就不会用错。

第二个问题：树一定要从上往下画吗？不一定。这只是计算机科学里的主流约定：根在上，叶子在下，方便从左到右阅读。有些教材会把根画在左边，让树”往右长”；家谱里也经常把长辈画在上面。画法只是表达方式，树的本质是”谁是谁的父节点”，与画法无关。你读别人画的树时，先找根，再看方向，就不会被画法带偏。

第三个问题：我是不是要先把所有术语背下来，才能继续学？完全不用。这一系列文章的写法是”用到了才讲”：第 3 篇的代码里用到”节点”，我们就复习节点；第 7 篇的二叉搜索树用到”左孩子""右孩子”，我们就强调左孩子右孩子。术语是工具，不是门槛。你只需要在读完本篇后，看到”根、父节点、子节点、叶子”这些词不犯怵，就已经超额完成任务了。

第四个问题：树和递归是什么关系？为什么大家都说”学树必须学递归”？因为树有一个天生的递归性质：一棵树由根和若干棵子树组成，而每棵子树自己又是一棵树。所以”处理一棵树”这件事，天然可以写成”先处理根，再递归地处理每一棵子树”。后面的遍历、查找、插入，全部长这个模样。你现在只需要记住”树 = 根 + 一堆更小的树”这句话，递归的直觉就埋下种子了。

好了，问题答完，该动动手了。下面是给今天这篇配的练习题，请先独立完成，再对答案。

练习题：动动手，把直觉变成肌肉记忆

如果你全部做对了，恭喜你，第一棵树的种子已经种下；如果做错了，也别灰心，把错题对应的章节再读一遍，这比做对十道题更有价值。

写在最后：给这粒种子浇点水

在结束之前，我想再陪你多待一小会儿。今天这篇的篇幅不短，如果你真的读到了这里，说明你是一个愿意花时间把基础打牢的人，这本身就值得恭喜。

学数据结构，最忌讳的就是”赶进度”。树的二十篇，你可以一个月读完，也可以半年读完，速度不重要，重要的是每一篇读完，你都能用自己的话把”它是什么、为什么存在、解决什么问题”讲清楚。能讲清楚，才是真的懂了；不能讲清楚，就回头再读一遍，这不丢人，这是每个程序员都走过的路。

下一篇文章，我们会进入树的世界的第一片正式领地：术语。那里的每一个词，都是今天这些直觉的”官方名字”。你带着今天的画面去读，会发现一切都顺理成章。

我在这里等你。我们下一篇见。

下一篇预告：树的基本术语

这一篇，我们用生活经验”看见”了树，但还欠着一笔账：正式的术语。比如”深度”和”高度”到底怎么算？“满二叉树”和”完全二叉树”差在哪？“有序树”和”无序树”又是什么意思？树在代码里到底长什么样？

下一篇《树系列第 2 篇：树的基本术语》，我们会把这些词一个一个抠清楚，每一个术语都配上图和例子；我们还会亲手把一棵树翻译成代码里的节点定义，为后面实现二叉搜索树铺好路。

到那时候，你再看任何一棵树，都能像看家谱一样，一眼认出谁是谁。我们下一篇见！