宁波建网站模板,网上帮人卖东西的平台,网络公司网站建设,企业邮箱地址怎么注册如同树有高度一样#xff0c;数据结构中的“树”也有高度#xff0c;只不过这个高度指的是第几“层”。就像武功可以修炼到第几层一样#xff0c;树也可以长到第几层。
需要指明的是#xff0c;树的根节点属于第几层是没有严格的定义的#xff0c;一般被认为是处于第0层或…如同树有高度一样数据结构中的“树”也有高度只不过这个高度指的是第几“层”。就像武功可以修炼到第几层一样树也可以长到第几层。
需要指明的是树的根节点属于第几层是没有严格的定义的一般被认为是处于第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
第二层31×3
第三层93×3
第四层279×3
第五层8127×3
第六层24381×3
第七层729243×3
第八层2187729×3
前七层的节点为109313927812437291093无论怎样努力也生不出2023个娃第八层的节点为3280109321873280大于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位更实用吧
