“树”的高度的计算——CSP-J1真题详解

如同树有高度一样，数据结构中的“树”也有高度，只不过这个高度指的是第几“层”。就像武功可以修炼到第几层一样，树也可以长到第几层。

需要指明的是，树的根节点属于第几层是没有严格的定义的，一般被认为是处于第0层或第1层（国内主流视为第1层）。

以树的根节点为第1层为例，由树根长出来的分支就是第2层，分支再长出来的是第3层，以此类推。只不过，一般来讲数据结构中的“数”一般都被设计成倒着长的树。

明白了树的高度是什么，就可以做个真题练练手。

【题目】根节点的高度为1，一棵拥有2023个节点的三叉树高度至少为()

A. 6

B. 7

C. 8

D. 9

【题目来源】

2023 CCF非专业级别软件能力认证第一轮 (CSP-J1) 入门级C++语言试题 第5题

【解析】

本题先是明确告诉你“根节点的高度为1”，也就是说将树的根节点视为第1层。如果没有这句话，题目就是不严谨的。

三叉树就是一个树枝最多可以长出三个树杈的树，就像计划生育一户最多可生三个娃一样。已知节点数（2023个），求树的最小高度，也就是树至少要长多少层，或者可以看作人要繁衍多少辈。显然，生的越多，所需的层数就越少。所以，这个问题就相当于问：一户人家，每辈生三个娃，生出2023个娃需要多少辈？

这就是一个画图找规律的题：

很容易看出，每一层的节点数都是前一层的3倍。

第一层：1

第二层：3=1×3

第三层：9=3×3

第四层：27=9×3

第五层：81=27×3

第六层：243=81×3

第七层：729=243×3

第八层：2187=729×3

前七层的节点为1093（1+3+9+27+81+243+729=1093），无论怎样努力也生不出2023个娃；第八层的节点为3280（1093+2187=3280），大于2023。所以要生出2023个娃，至少要八代，即一棵拥有2023个节点的三叉树高度至少为8，本题选C。

实质上，这些节点数构成的正是高中要学的等比数列（后一项与前一项的比值相等）。求n层的节点就是求等比数列前n项的和，公式为：

s = a1*(1-q^n)/(1-q)

公式中的a1为首项，q就是后一项与前一项的比值，被称为公比。了解了这个公式，不管是几叉树都可以套公式算出n层的总节点数。本题为三叉树，公比为3，代入得：

s = 1*(1-3^n)/(1-3) = (3^n-1)/2

但是，背熟公式未必是快速解题的最佳方式，比如本题，当n取7、8等相对较大的值时，因为同时有乘方、减法、除法，算出s的值并不那么方便。

相反，按照前面那样一层一层推导，每次都乘一个很小3，计算量小，反而是更快的。在求总节点数时，也不必从第一层一直加到最后一层，可以采用估算的方式，很快就能锁定答案。方法就是在算每一层的节点数时，心里都要有一杆秤：暗暗与目标数2023进行对比。显然计算到第六层时，只有一个数上百，加起来根本不可能上千，别说2000多了，所以根本不用算就能直接排除。算到第七层，简单估算下，六、七两层加起来还不到一千，加上前面的虾兵蟹将也根本不可能破2000，所以肯定也不行。算到第八层，好嘛，您老人家一层已经超过2023了，所以答案是什么还用问吗？

因为求树高度的题目很少见，所以咱们只要掌握这种找规律的方法就可以从容应对了。

但是，如果你是个追求极致的人，还想让速度更快怎么办呢？

吴军曾提出过：真正的高手都是“杀鸡要用牛刀”的人！

这时候你还得用公式，但是咱们说过公式存在计算困难的问题，怎么解决？

无他，唯手熟尔！

方法就是把计算结果提前背下，就像背九九乘法表一样。

提高速度最有效的办法就是减少步骤。记公式是为了减少推导步骤，记结果是为了减少计算步骤。

速度拼到最后拼的是记忆。

以二叉树和三叉树举例，每层节点数和节点总数如下：

n	二叉树		三叉树
	单层节点	总节点	单层节点	总节点
	2^(n-1)	2^n-1	3^(n-1)	(3^n-1)/2
1	1	1	1	1
2	2	3	3	4
3	4	7	9	13
4	8	15	27	40
5	16	31	81	121
6	32	63	243	364
7	64	127	729	1093
8	128	255	2187	3280
9	256	511	6561	9841
10	512	1023	19683	29524

当然要记住这个表很困难，性价比也比较低。但如果改成记下面这个表，再结合公式辅助，完全可以做到秒解。

n	2^n	3^n
1	2	3
2	4	9
3	8	27
4	16	81
5	32	243
6	64	729
7	128	2187
8	256	6561
9	512	19683
10	1024	59049

记这个表就比较有意义了，尤其是2^n在二进制运算中很常用，所以记住它性价比就很高。虽然记3^n性价比没2^n高，但总比记π的小数点后n位更实用吧！