1. 从“数叶子”到“算家底”为什么我们需要计算树的结点在数据结构的世界里树Tree是一种再常见不过的结构。无论是文件系统的目录、公司组织的架构图还是编程语言中的抽象语法树其背后都是树形逻辑在支撑。很多初学者在学树时会把大量精力放在遍历前序、中序、后序或者平衡旋转AVL、红黑树这些“动态”操作上这当然很重要。但有一类非常基础却极其关键的问题常常被当成“数学题”而轻视了——那就是给定一些条件计算一棵树到底有多少个结点其中又有多少个是叶子结点。你可能会问知道这个有什么用难道我们不是直接遍历一遍数一下就行了吗在实际的软件工程和算法问题中情况往往没这么简单。场景一资源预估与性能分析。假设你正在设计一个内存数据库的索引决定使用B树。老板问你“我们的用户表预计有10亿条记录用3阶B树来存这棵树大概有多高会占用多少内存” 如果你不会根据树的度阶数和总结点数来推算树的高度和结点总数你就无法给出一个量化的评估只能拍脑袋说“大概、可能、也许”这在严谨的系统设计中是不可接受的。场景二静态代码分析与优化。你在为一个编译器开发优化模块需要分析抽象语法树AST。某些优化策略比如常量折叠的效率与树中叶结点的比例有关。你不需要真正解析整个庞大的源码文件生成AST再去遍历统计而是可以根据语法规则推导出这棵语法树的大致形态从而预判优化器的开销。场景三笔试面试与算法竞赛。这可能是最直接的动力了。“若一棵度为4的树中有20个度为4的结点10个度为3的结点1个度为2的结点10个度为1的结点则叶结点数是多少” 这类题目在《王道数据结构》等考研资料中屡见不鲜它考察的正是你对树的基本性质的深刻理解而非死记硬背。所以计算树的总结点数和叶结点数绝不是一道脱离实际的数学练习题。它是将树的抽象定义与具体问题连接起来的桥梁是进行复杂度分析、空间估算和结构推导的基石。掌握了它你才能从“知道树是什么”进化到“能用树的思维解决问题”。2. 核心公式的推导从“数枝条”到“数结点”要计算结点我们需要一个最核心的武器。这个武器不是凭空出现的而是从树的一个最基本性质推导出来的在一棵树中除了根结点每个结点都有且仅有一个父结点而每个父结点到其孩子结点之间都有一条边分支。我们可以从这个性质出发得到两个视角的等式视角一按结点度数算总分支数。树的度Degree of Tree是树内各结点度的最大值。而某个结点的度Degree of Node就是指这个结点拥有的孩子数或者说子树数。每个度为k的结点就会贡献k条向下的分支边。假设树中度为0, 1, 2, ..., m 的结点个数分别为n0, n1, n2, ..., nm其中m是树中最大的度。 那么整棵树的总分支数也就是总边数B就等于B n1 * 1 n2 * 2 ... nm * m视角二按结点关系算总分支数。从边的定义来看一条边连接一个父结点和一个子结点。除了根结点没有父结点其他每个结点都有且仅有一条指向它的边来自其父结点。假设树的总结点数为N那么根结点有1个其他结点有N-1个每个对应一条入边。因此总边数B又等于B N - 1现在我们把两个视角联系起来就得到了关键等式N - 1 n1 * 1 n2 * 2 ... nm * m(公式1)同时总结点数N显然也是所有度数的结点数之和N n0 n1 n2 ... nm(公式2)我们的目标通常是求叶结点数n0。将公式2代入公式1(n0 n1 n2 ... nm) - 1 n1 * 1 n2 * 2 ... nm * m移项整理后一个美妙的公式出现了n0 1 n2 * 1 n3 * 2 ... nm * (m-1)更简洁地可以写成n0 1 Σ_{i2}^{m} [ni * (i-1)]这个公式就是我们的核心武器。它揭示了叶结点数与所有非叶结点且度大于1之间的关系。度数为1的结点n1在这个公式中神奇地消失了因为它贡献一条边同时也消耗一个“子结点”名额一进一出对叶结点数量没有净影响。注意这个公式适用于任何普通的树Rooted Tree不一定是二叉树。它是普适的。一个生活化的类比想象一个家族谱系一棵树。每个人结点都有0个或多个孩子度。现在我们要数没有孩子的人叶结点。我们可以换个思路从老祖宗根结点开始他本身算1个“基础名额”。然后每当有一个人生了2个孩子他就比“只生1个”的情况多带来了1个“额外名额”因为2个孩子需要2个位置但父亲本人已经占了一个位置净增1个位置。生3个孩子就净增2个名额以此类推。所有这些“额外名额”加上老祖宗自己的“基础名额”最终就构成了整个家族的所有“终端位置”叶结点的总数。这个“额外名额”就是公式中的(i-1)。3. 二叉树情形下的特化与深化二叉树是树结构中最常用的一类它规定每个结点最多有两个孩子左孩子和右孩子。在二叉树中结点的度只能为0、1或2。让我们把上面的通用公式应用到二叉树上。设二叉树中度为2的结点数为n2度为1的结点数为n1度为0的结点数叶结点为n0总结点数为N。代入通用公式n0 1 Σ_{i2}^{m} [ni * (i-1)]因为最大度m2所以n0 1 n2 * (2-1) 1 n2同时总结点数N n0 n1 n2。结合这两个式子我们可以得到二叉树性质中非常著名的一条在任意一棵二叉树中叶结点数总比度为2的结点数多一个n0 n2 1。这个结论非常强大它不受树是否平衡、是否完全的影响。只要它是二叉树这个等式就恒成立。实战例题1基础计算题目已知一棵二叉树有10个度为2的结点5个度为1的结点请问该二叉树总共有多少个结点多少个叶结点 解答叶结点数n0 n2 1 10 1 11。总结点数N n0 n1 n2 11 5 10 26。 验证边数B n1 2*n2 5 20 25等于N-125正确。进阶思考为什么n1不影响n0从公式n0 1 n2看n1确实没有出现。我们可以从“构建过程”理解想象我们从只有一个根结点叶结点开始每次增加一个度为2的结点实际上需要“占用”一个已有的叶结点位置并“生成”两个新的叶结点。净效果是叶结点数增加1-1 2 1。而增加一个度为1的结点是“占用”一个叶结点位置“生成”一个新的叶结点。净效果是叶结点数不变-1 1 0。所以只有度为2的结点会净增叶结点且每个净增一个。4. 应对复杂树形通用公式的解题框架当题目给出的树不是二叉树或者条件更复杂时我们就必须回到最根本的通用公式和两个基本等式。下面通过几个典型场景建立一套解题框架。场景A已知各类度结点数求总结点或叶结点直接套用这是最直接的题型。通常题目会给出n1, n2, n3, ...的值要求n0或N。 解题步骤确认最大度 m从题目条件中找出出现的最高度数。列出已知量明确给出数值的ni。套用核心公式n0 1 Σ_{i2}^{m} [ni * (i-1)]。计算总结点N n0 Σ_{i1}^{m} ni。例题2开篇问题变形一棵度为4的树中有20个度为4的结点10个度为3的结点1个度为2的结点10个度为1的结点求叶结点数和总结点数。 解答最大度m4。已知n420,n310,n21,n110。n0未知。套公式n0 1 n2*(2-1) n3*(3-1) n4*(4-1) 1 1*1 10*2 20*3 1 1 20 60 82总结点数N n0 n1 n2 n3 n4 82 10 1 10 20 123。场景B已知总结点数与叶结点数反推度分布这类问题通常隐含了树是“满树”或“完全树”的假设或者需要你列出方程。例题3设一棵树有100个结点其中叶结点有80个。已知该树中只有度为0、1、3的结点问度为3的结点有多少个 解答设度为1的结点数为x度为3的结点数为y。根据总结点数80 x y 100x y 20(方程1)根据边数关系N-1 各度结点数乘度数之和100 - 1 x*1 y*399 x 3y(方程2)解方程组方程2减方程1得(x3y) - (xy) 99 - 202y 79y 39.5。结点数必须是整数y39.5不合理。因此不存在这样的一棵树。这个结果本身就是一个重要答案它告诉你题目给出的条件100结点80叶只有度0、1、3在树的基本性质约束下是不可能的。这在验证数据结构设计合理性时很有用。场景C与树高、路径长度结合的综合题这类题目常出现在平衡树如AVL树、B树的分析中。例题4对于一棵高度为5的满二叉树所有分支结点度均为2且所有叶结点在同一层请问有多少个结点多少个叶结点 分析满二叉树是特殊的二叉树也是特殊的树。我们可以用二叉树性质也可以用通用方法。 方法1二叉树性质满二叉树中只有度为0和度为2的结点。且n0 n2 1。对于高度为h的满二叉树叶结点全在第h层数量为2^(h-1)。本题h5所以n0 2^(5-1) 16。则n2 n0 - 1 15。总结点数N n0 n2 31。 方法2通用公式在满二叉树中n10。我们已知高度h5总结点数N 2^h - 1 31。设n2为x则n0 N - x。代入n0 1 n2得(31 - x) 1 x解得x15n016。实操心得对于完全二叉树、满二叉树这类规整的树通常有更直接的公式如高度为h的满二叉树结点总数为2^h - 1。但用基本性质去推导和验证能加深你对这些公式来源的理解避免死记硬背。5. 从理论到实践在算法与工程中的应用理解了原理我们来看看它在代码和实际问题中如何体现。你不会真的写一个函数去“计算”已知的n2来求n0因为如果树已经建好了遍历一遍统计一下n0是 O(N) 的更直接。这个公式的真正威力在于分析和推导。应用1评估完全二叉树的数组存储完全二叉树常用数组存储。如果已知一个完全二叉树有N个结点我们可以快速知道叶结点数大约为ceil(N/2)对于最后一个结点其父结点索引为floor(N/2)所以索引大于floor(N/2)的结点都是叶子。这个结论可以用公式验证在完全二叉树中n1要么是0要么是1。根据n0 n2 1和N n0 n1 n2可以推导出n0 floor((N1)/2)。当N很大时约等于N/2。这让你在内存分配和索引计算时心里有数。应用2B树/B树容量与性能估算这是最体现价值的应用之一。以一道面试题为例“一颗M阶的B树最多能存储多少个关键字” 我们不直接背答案而是用树的结点思想来分析。B树规定根结点至少2个子树除非为叶。非根非叶结点至少有ceil(M/2)棵子树。每个结点最多有M棵子树。所有叶结点在同一层。问题转化为一棵满足B树约束的、高度为h的树最多有多少个结点每个结点最多有M-1个关键字。根结点最多1个。第1层根的孩子最多M个结点。第2层最多M * M个结点。...第h层叶结点层最多M^(h-1)个结点。则总结点数最多为1 M M^2 ... M^(h-1) (M^h - 1)/(M - 1)。 每个结点最多M-1个关键字所以最多关键字数约为(M-1) * (M^h - 1)/(M - 1) M^h - 1。 这个h就是树高。反过来如果告诉你树高h和阶数M你就能估算出这棵B树最多能存多少数据。这对于数据库存储引擎的参数调优至关重要。应用3哈夫曼树最优二叉树的构建验证哈夫曼树用于数据压缩。给定n个权值构建的哈夫曼树一定有(2n-1)个结点其中叶结点为n个原始权值结点内部结点为(n-1)个。这正好符合二叉树性质n0 n2 1吗注意哈夫曼树没有度为1的结点n10。那么n0 n, n2 n-1满足n (n-1) 1。如果你在实现哈夫曼编码时最后得到的结点数不对就可以用这个性质快速检查构建过程是否出错。6. 常见陷阱与深度思考题掌握了基本公式一些看似复杂的题目也能拆解。但有几个陷阱需要特别注意。陷阱一混淆“树的度”与“结点的度”树的度是整棵树中所有结点度的最大值。它是一个全局属性一个数值。结点的度是某个特定结点拥有的子树孩子个数。它是一个局部属性。 在公式n0 1 Σ_{i2}^{m} [ni * (i-1)]中这个m指的是树的度即所有结点中度数最大的那个值。即使只有一个结点的度是10其他结点度都是1m也等于10公式中n3, n4, ..., n10这些项虽然可能为0但逻辑上要清楚。陷阱二忽视“树”与“二叉树”定义的前提所有推导基于一个前提我们讨论的是树而不是图。树是无环连通图。有一个等价定义树是有且仅有一个根结点且除了根结点外每个结点有且仅有一个父结点的结构。这个“有且仅有一个父结点”的性质才是总边数 总结点数 - 1的根源。如果是一个有环的图或者森林多棵树这个等式就不成立了。深度思考题一棵树有N个结点则它有多少条边答案N-1。这是树的定义性质也是所有推导的起点。对于一棵二叉树已知其前序遍历序列和中序遍历序列能否直接求出叶结点数可以。通过两个序列可以唯一确定这棵二叉树的结构。重建树后遍历即可得到。但有没有不重建树的方法理论上通过分析序列中结点的相对位置可以判断哪些结点在重建后是叶子即在中序序列中其左右都没有子树结点但实现起来比重建树更复杂。在工程上重建树是更清晰通用的做法。如果一棵树有N个结点其中度为1的结点有X个那么叶结点最少有多少个这个问题需要一点极值思维。要叶结点最少就要让非叶结点尽可能多地“分担”子结点。但树的度没有上限本题未指定最大度。我们可以构造一种极端情况让一个根结点有(N-X-1)个孩子这些孩子都是叶结点剩下的(X-1)个度为1的结点作为这些孩子链上的中间结点如果X1。但这样根结点的度会非常大。如果限制最大度问题就变成了一个优化问题。通常在无限制下可以构造出叶结点数仅为X当所有度为1的结点连成一条链链的末端是一个叶结点的情况吗让我们验证设链上有k个度为1的结点则链的末端是一个叶结点链的起始是根结点如果根结点度也为1则它也在链上。总结点数N k 1k个度1结点1个叶结点。但题目给了N和X要求最少叶结点。我们可以尝试让结构更“紧凑”即让度1的结点作为其他度更高结点的孩子从而减少叶结点。实际上可以构造出只有1个叶结点的情况吗考虑一个星形结构一个根结点它有(N-1)个孩子。这些孩子都是叶结点。此时度为1的结点数X0根结点度为N-1其他结点度为0。如果要求X0我们就必须引入一些度为1的结点这必然会增加叶结点或改变其他结点的度。这是一个有趣的组合数学问题其答案与N和X的具体关系有关通常需要分情况讨论。最后记住这些公式和性质不是为了应付考试而是为你植入一种“树形思维”。下次当你看到任何树形结构无论是前端的DOM树、后端的决策树还是系统里的目录树你都能下意识地去分析它的规模、平衡性和资源消耗这才是数据结构知识内化的标志。从理解每一个结点的度和每条边的意义开始你就能把握住整棵树的脉络。
)
