引子老王画族谱画出了一棵倒立的树还记得那位经营仓库、痴迷于用聪明方法做事的老王吗这一路我们陪着老王认识了四位摆货家什——连号储物柜数组、寻宝纸条链表、一摞盘子栈、一条长龙队列。老王越用越顺手可他渐渐发现这四位有一个共同的局限它们都是线性的——货物排成一条线一个挨一个要么往前、要么往后是一条直肠子。可这天老王要给自己的仓库画一张部门管理结构图麻烦来了。总经理底下管着两个副总每个副总底下又各管着两个主管每个主管底下再各带几个组长……老王拿着连号储物柜和寻宝纸条比划了半天怎么都画不出来不对啊老王挠头“这关系它不是一条线啊它是一个分两个、两个分四个像树枝一样层层分叉开来的我那些’排成一条线’的家什根本装不下这种’分叉’的关系”他随手在纸上一画——一个顶点在上枝杈向下层层散开。画完一看老王自己都笑了“嘿这不就是一棵’倒过来长’的树嘛根在上头枝叶往下散。”老王不知道他这随手一画正好画出了计算机世界里一类全新的、威力巨大的非线性家什——它彻底挣脱了一条线的束缚用分叉的智慧装下了这个世界里千千万万的层级关系。它就是——树Tree。而其中最经典、最重要的一种正是我们这一篇的主角——二叉树Binary Tree。第一章从一条线到一棵树——非线性的飞跃在认识二叉树之前我们得先搞懂一件大事树这种结构到底新在哪里前面四位家什数组、链表、栈、队列有一个共同的名字叫线性结构数据排成一条线每个元素最多只有一个前面和一个后面。就像排队你前面只有一个人后面也只有一个人。规规矩矩一条道走到底。而树是非线性结构的代表。它最大的突破在于一个元素可以同时连着好几个下级就像一位经理手下可以同时管着好几个员工一根树枝可以同时分出好几条岔枝。关系从一条线变成了一张网、一棵树。线性结构一条线 树形结构层层分叉 [A]→[B]→[C]→[D] (A) 一个接一个 ╱ ╲ 一条道走到底 (B) (C) ╱ ╲ ╱ ╲ (D)(E) (F)(G) 一个分两个层层散开核心飞跃从线性到树形是数据结构的一次质的飞跃。现实世界里那些线装不下的东西——公司的组织架构、家族的族谱、电脑里的文件夹、网页的层层目录——通通可以用树来完美表达。因为这个世界本就充满了层级与分叉。而二叉树则是树家族里最简单、最经典、最重要的一员。它的规矩只多了一条——二叉树每个节点最多只能有两个孩子。一个左孩子一个右孩子不能再多了。为什么偏偏是二叉因为一分为二是最简洁、最优雅的分叉方式——非左即右非此即彼简单到极致却又威力无穷后面你就明白它的厉害了。第二章认识这棵树的零件——一套形象的家族称谓一棵二叉树是由一个个节点Node组成的。还记得链表的节点吗只不过链表节点的纸条指向一个下家而二叉树的节点最多揣着两张纸条——一张指向左孩子一张指向右孩子。老王发现给这棵树的各个零件起名字用的全是家族称谓亲切又好记(A) ← 根节点祖宗最顶上的老大 ╱ ╲ (B) (C) ← A的孩子B和C互为兄弟 ╱ ╲ ╲ (D) (E) (F) ╱ (G) ← 叶子节点没有孩子的最末梢根节点Root最顶上的那个老祖宗整棵树的起点A。一棵树只有一个根父节点 / 子节点A 是 B、C 的父亲B、C 是 A 的孩子——和现实里的父子关系一模一样兄弟节点同一个父亲的孩子们互称兄弟B 和 C 是兄弟叶子节点Leaf那些没有孩子的末梢节点像 D、E、G位于树的最外围像树叶一样深度 / 高度这棵树有几层。层数越多树就越高。巧妙的命名你发现没有整套术语——根、父、子、兄弟、叶——全是一棵树 一个家族的形象比喻计算机科学家在给这些抽象概念命名时悄悄借用了我们最熟悉的自然万物和人伦关系。这让冰冷的结构瞬间有了温度也好记多了。第三章怎么逛完一棵树——四种遍历的智慧数组、链表那种一条线的结构逛起来很简单——从头到尾走一遍就行。可二叉树是分叉的逛起来就有讲究了到了一个分叉口你是先看左边先看右边还是先看自己不同的顺序就有了不同的游览路线这在计算机里叫遍历Traversal。老王带我们走几条最经典的路线我们用这棵小树举例(1) ╱ ╲ (2) (3) ╱ ╲ (4) (5)3.1 前序遍历先看自己再看左右根→左→右规则每到一个节点先记录自己再去逛左子树最后逛右子树。路线1 → 2 → 4 → 5 → 3像什么像一个急性子的领导——每到一处先把自己的名字签上再去看下属。3.2 中序遍历先看左再看自己最后看右左→根→右规则先逛完左子树再记录自己最后逛右子树。路线4 → 2 → 5 → 1 → 3它有个神奇的特性后面讲二叉搜索树时揭晓——能让数据自动按从小到大的顺序排好3.3 后序遍历先看左右最后才看自己左→右→根规则先逛完左右子树最后才记录自己。路线4 → 5 → 2 → 3 → 1像什么像一个沉稳的领导——先让下属都汇报完自己最后才表态、做总结。3.4 层序遍历一层一层地逛从上到下从左到右规则像看楼层一样第一层逛完逛第二层第二层逛完逛第三层……路线1 → 2 → 3 → 4 → 5⚠️彩蛋还记得上一篇队列里埋的那个钩子吗这个一层一层逛的层序遍历也叫广度优先搜索 BFS它的幕后功臣正是队列每逛到一个节点就把它的孩子们入队排好再依次出队处理——先进先出恰好保证了一层一层、从左到右的完美秩序。你看前面学的家什在这里重出江湖串起来了遍历的智慧同一棵树仅仅因为先看谁、后看谁的顺序不同就走出了四条完全不同的路线。这告诉我们面对同一个复杂的事物切入的顺序’不同看到的’风景’也截然不同。而每一种顺序都自有它最妙的用武之地。第四章二叉树的封神之作——二叉搜索树BST讲到这里你可能会问二叉树分叉是挺好可它到底快在哪凭什么说它威力无穷答案藏在二叉树一个封神的变种里——二叉搜索树Binary Search Tree简称 BST。它在普通二叉树的基础上加了一条石破天惊的规矩对于任何一个节点它的左边子树里所有的值都比它小它的右边子树里所有的值都比它大。一句话——左小右大井然有序。(8) ╱ ╲ (3) (10) ╱ ╲ ╲ (1) (6) (14) 看节点8左边的3、1、6 全都 8右边的10、14 全都 8 看节点3左边的1 3右边的6 3 …… 每个节点都满足这条左小右大的规矩有什么魔力它让查找这件事快得飞起故事老王想在这棵树里找数字6。看他怎么找第①步从根节点 8 开始。6 8 → 往左走右边一大半直接砍掉不看了 第②步来到 3。6 3 → 往右走左边又砍掉了 第③步来到 6。找到了只用了3步而且你发现没有——每比较一次就砍掉了一大半的数据这个每次砍掉一半的感觉是不是无比熟悉没错这正是我们在算法篇里见识过的、那位取货员小赵的二分查找绝技二叉搜索树相当于把二分查找的智慧物化成了一棵树的形状。所以它的查找速度也达到了二分查找那个令人惊叹的水平——O(logn)还记得 O(logn) 有多恐怖吗100 万个数据最多找约20 次10 亿个数据最多找约30 次这就是二叉树的封神之作。它用左小右大的优雅秩序把查找速度提升到了 O(logn) 的境界——既不像数组那样增删要全体挪位又不像链表那样查找要顺藤摸瓜它在查找和增删之间找到了一个绝妙的平衡一个小提醒树也会长歪不过二叉搜索树有个软肋——如果数据插入的顺序不巧它可能会长歪退化成一条瘸腿的斜线正常的树矮胖快 长歪的树瘦高慢 (8) (1) ╱ ╲ ╲ (3) (10) (2) ╲ (3) ← 退化成链表了一旦长成这副瘦高个的模样它就退化成了链表查找又变回了慢吞吞的 O(n)。为了不让树长歪聪明的科学家又发明了能自动保持平衡、自我调整的升级版树——比如大名鼎鼎的红黑树“AVL树”。它们就像有了健身教练无论怎么插入数据都能始终保持矮胖均衡的好身材把 O(logn) 的高效稳稳锁死。这些是后话但你要知道二叉树家族枝繁叶茂还有很多高手。第五章二叉树的用武之地——它撑起了半个计算机世界别以为树只是个理论玩具它的应用深入到了计算机世界的骨髓里️文件系统你电脑里的文件夹——一个文件夹里装着子文件夹子文件夹里再装文件夹……这就是一棵活生生的树数据库的索引数据库为什么能在亿万条记录里瞬间查到你要的数据背后正是一种树B树在飞速地左小右大地查找网页的结构DOM树你看的每一个网页浏览器都把它解析成一棵树——body下面挂着divdiv下面挂着p……层层嵌套决策与AI游戏 AI 的决策树、机器学习里的随机森林本质都是树数据压缩你发的每一个压缩包如哈夫曼编码背后也有一棵树在帮你节省空间。恍然大悟原来树无处不在只要现实世界里存在层级、包含、分类、上下级的关系——它背后几乎都站着一棵树。因为这个世界的秩序本就是分叉的、层级的。树正是对这种秩序最忠实、最优雅的描摹。尾声一棵分叉树的智慧亦是人生的智慧老王的分叉智慧树从一张画不出的组织架构图讲到根、叶、遍历再到左小右大的封神之作终于把二叉树这位威力巨大的非线性家什说了个透。但当我们合上书会发现这棵倒立生长的树竟也舒展着几分耐人寻味的人生哲理。第一挣脱一条线的思维世界会豁然开朗。老王最初的困境是想用一条线去装分叉的关系怎么都装不下。直到他画出那棵树难题才迎刃而解。这何尝不是一种思维的解放我们太习惯线性地思考——非黑即白、非此即彼、一条道走到黑。可现实世界分明是分叉的、多元的、有层次的。当你愿意挣脱一条线的执念承认一个问题可以有好多个分支、一件事可以有好多种可能——你眼前的世界会豁然开朗。第二左小右大的秩序是高效的前提。二叉搜索树为什么能快到 O(logn)因为它有一条左小右大的铁律让一切井然有序于是每一步都能砍掉一半、直奔目标。这启示我们高效的前提是秩序。一个杂乱无章、毫无规则的系统就像那棵长歪的树注定是低效的、缓慢的。无论是整理房间、安排工作还是规划人生——先建立起一套清晰的秩序你才能在需要时迅速地找到方向、直击要害。第三别让自己长歪要懂得自我平衡。那棵会长歪、退化成瘸腿斜线的树给了我们最深的警醒——再好的结构若失去了平衡也会沦为低效。而那些红黑树之所以高明正在于它们懂得自我调整、动态平衡。人生不也如此吗工作与生活、付出与休息、进取与沉淀……一旦长期失衡、单方面疯长整个人就会像那棵瘦高的歪树一样迟早出问题。真正的智慧不是一味地往一个方向猛冲而是像那棵会自我调整的树——在动态中始终守护着自己的平衡。下次当你在电脑里一层层打开文件夹、在数据库里瞬间查到一条记录、或是看着一张组织架构图时请记得——在那看不见的背后正有一棵棵倒立生长的智慧树用它分叉与秩序的古老智慧为这个层级分明的世界又快又稳地梳理着千头万绪。二叉树就是这门关于分叉与层级、秩序与平衡的、优雅而深刻的智慧。它让数据结构第一次挣脱了一条线的束缚舒展成一棵枝繁叶茂的大树像一句朴素的箴言提醒着我们——挣脱一条线的执念你才看得见世界的辽阔守住左小右大的秩序你才能在繁杂中直击要害而懂得自我平衡、不让自己长歪的人才能像一棵真正的树那样——向下扎根向上生长枝繁叶茂从容而蓬勃。这就是藏在一棵分叉树背后的二叉树的全部浪漫。