“树”的高度的计算——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位更实用吧!
相关文章:
“树”的高度的计算——CSP-J1真题详解
如同树有高度一样,数据结构中的“树”也有高度,只不过这个高度指的是第几“层”。就像武功可以修炼到第几层一样,树也可以长到第几层。 需要指明的是,树的根节点属于第几层是没有严格的定义的,一般被认为是处于第0层或…...
Docker介绍、docker安装以及实现docker的远程管理
1.Docker介绍 1.Docker介绍 Docker 是⼀个开源的应用容器引擎,可以实现虚拟化,完全采用“沙盒”机制,容器之间不会存在任何接口。 Docker 通过 Linux Container(容器)技术将任意类型的应用进行包装,变成一…...
【UE5】基于摄像机距离逐渐剔除角色
效果 步骤 1. 新建一个工程,在内容浏览器中添加第三人称游戏内容包 2. 找到第三人称角色的材质实例“MI_Quinn_01”并打开 找到材质实例的父项材质“M_Mannequin” 打开材质“M_Mannequin” 在材质图表中添加如下节点 此时运行效果如文章开头所示。 参考视频&#…...
LabVIEW优化内存使用
在LabVIEW中,优化内存使用的关键在于理解LabVIEW的内存管理机制并采用一些最佳实践。以下是一些可能帮助减少内存占用的方法: 1. 减少数据副本的生成 避免不必要的数据复制:每当你在程序中传递数组或子数组时,LabVIEW可能会创建副…...
多进程和多线程基础概念LINUX
进程和程序的区别 程序是静态的,它是保存在磁盘上的指令的有序集合,没有任何执行的概念进程是一个动态的概念,它是程序执行的过程,包括了动态创建、调度和销毁的整个过程 并行:在 cpu 多核的支持下,实现物…...
React Native的Android端fetch的网络请求FormData请求错误:TypeError:Network request failed
// formdataconst formData new FormData();formData.append("code", appUserCode);formData.append("wallet", appName);// const formDataStr code appUserCode &wallet appName;// 参数形式//const _body code${appUserCode}&wallet${app…...
python之matplotlib (1 介绍及基本用法)
介绍 matplotlib是Python中的一个绘图库,它提供了一个类似于 MATLAB 的绘图系统。使用matplotlib你可以生成图表、直方图、功率谱、条形图、错误图、散点图等。matplotlib广泛用于数据可视化领域,是 Python 中最著名的绘图库之一。 同样matplotlib的安…...
ROS2常用指令
ROS2(Robot Operating System 2)是一个用于机器人软件开发的灵活框架,它提供了一套丰富的工具和库来支持机器人的开发、模拟、部署和测试。ROS2的常用指令可以大致分为几个类别,包括功能包管理、节点管理、话题管理、服务管理、动…...
SQL注入(原理、分类、union、POST注入)
目录 【学习目标、重难点知识】 【学习目标】 【重难点知识】 SQL注入简介 SQL注入原理 SQL注入类型 MySQL与SQL注入的相关知识 information_schema 数据库的结构 数据库查询语句 limit的用法 需要记住的几个函数 注释符号 SQL注入探测方法 SQL注入漏洞攻击流程…...
【勒索病毒应急响应流程】
概述 不同应急事件响应方式不同,建议大家阅读以下案例,解决自己当前的困扰,当然也可以根据自己的经验对文章进行补充和修正,欢迎在评论区留言。 案例1 事件概述 某安服团队接到某政府部门的远程应急响应求助,要求对被勒索服务器进行排查分析并溯源。 排查溯源 1、应…...
C ++初阶:C++入门级知识点
目录 🌞0.前言 🚈1.C输入输出 🚈2.缺省参数 🚝2.1全缺省参数 🚝2.2半缺省参数 🚈3.函数重载 🚝3.1参数类型不同 🚝 3.2参数个数不同 🚝3.3参数类型顺序不同 …...
php中如何高效地实现一个函数以判断给定日期是否位于多个预定义的时间范围内,同时确保代码的可读性、可维护性和性能优化
背景信息: 我有一个包含多个时间范围的数组,每个时间范围由起始日期和结束日期组成(目前以字符串形式给出),例如: $ranges [[start > 2023-01-01, end > 2023-03-31],[start > 2023-06-01, end …...
存在重复元素 II(LeetCode)
题目 给你一个整数数组 nums 和一个整数 k ,判断数组中是否存在两个 不同的索引 i 和 j ,满足 nums[i] nums[j] 且 abs(i - j) < k 。如果存在,返回 true ;否则,返回 false 。 解题 """ 时间复杂度…...
认知杂谈21
今天分享 有人说的一段争议性的话 I I 自在之“坏”:真实自我的绽放 在社交场合中,听到“他不是个好人”这句话可能会让人惊讶,但其实被贴上“坏人”标签的人往往敢于跳出规则框架,展现真实自我。他们不做表面和谐的牺牲品&am…...
2024前端面试题-工程化篇
1.webpack(模块打包工具)五大核心 Entry入口,Output定义输出路径和命名规则,Loader模块转换器,Plugin扩展插件,Mode模式(Webpack使用相应模式的配置) 2.谈一谈你对Loader和Plugin的…...
【附源码】Python :PYQT界面点击按钮随机变色
系列文章目录 Python 界面学习:PYQT界面点击按钮随机变色 文章目录 系列文章目录一、项目需求二、源代码三、代码分析3.1 导入模块:3.2 定义App类:3.3 构造函数:3.4 初始化用户界面:3.5 设置窗口属性:3.6 …...
[Qt][QSS][下]详细讲解
目录 1.样式属性0.前言1.盒模型(Box Model) 2.常用控件样式属性1.按钮2.复选框3.单选框4.输入框5.列表6.菜单栏7.注意 1.样式属性 0.前言 QSS中的样式属性⾮常多,不需要都记住,核⼼原则是⽤到了就去查 ⼤部分的属性和CSS是⾮常相似的 QSS中有些属性&am…...
RAII在实现webserver这个项目中是怎么体现的?起到了什么作用
在WebServer项目中,RAII(Resource Acquisition Is Initialization,即资源获取即初始化)是一种重要的资源管理策略,它主要通过智能指针、锁、文件句柄等对象的生命周期来管理资源的分配和释放。RAII在WebServer项目中的…...
QT下显示自己派生的QWidget界面(提升为)
在实际开发过程中,我们可能有这样的需求,自己绘制一个仪表盘界面,然后将其贴到主界面上方。 这个时候就会用到“提升为”这个功能,该功能目的是将QWidget提升为自己派生的QWdiget子类,具体操作为,在主界面…...
jvm监控工具一览
下面是对 BTrace、JAD、JMAP、JSTAT、JSTACK、JINFO 以及 MARK 工具的比较表: 工具/属性功能适用场景使用难度是否侵入式是否需要重启 JVMBTrace动态跟踪和监控 Java 应用程序性能分析、故障排查、日志收集、安全监控中等无侵入式否JAD反编译 Java 字节码文件&…...
Java 语言特性(面试系列2)
一、SQL 基础 1. 复杂查询 (1)连接查询(JOIN) 内连接(INNER JOIN):返回两表匹配的记录。 SELECT e.name, d.dept_name FROM employees e INNER JOIN departments d ON e.dept_id d.dept_id; 左…...
【论文阅读28】-CNN-BiLSTM-Attention-(2024)
本文把滑坡位移序列拆开、筛优质因子,再用 CNN-BiLSTM-Attention 来动态预测每个子序列,最后重构出总位移,预测效果超越传统模型。 文章目录 1 引言2 方法2.1 位移时间序列加性模型2.2 变分模态分解 (VMD) 具体步骤2.3.1 样本熵(S…...
初学 pytest 记录
安装 pip install pytest用例可以是函数也可以是类中的方法 def test_func():print()class TestAdd: # def __init__(self): 在 pytest 中不可以使用__init__方法 # self.cc 12345 pytest.mark.api def test_str(self):res add(1, 2)assert res 12def test_int(self):r…...
JVM虚拟机:内存结构、垃圾回收、性能优化
1、JVM虚拟机的简介 Java 虚拟机(Java Virtual Machine 简称:JVM)是运行所有 Java 程序的抽象计算机,是 Java 语言的运行环境,实现了 Java 程序的跨平台特性。JVM 屏蔽了与具体操作系统平台相关的信息,使得 Java 程序只需生成在 JVM 上运行的目标代码(字节码),就可以…...
R语言速释制剂QBD解决方案之三
本文是《Quality by Design for ANDAs: An Example for Immediate-Release Dosage Forms》第一个处方的R语言解决方案。 第一个处方研究评估原料药粒径分布、MCC/Lactose比例、崩解剂用量对制剂CQAs的影响。 第二处方研究用于理解颗粒外加硬脂酸镁和滑石粉对片剂质量和可生产…...
mac 安装homebrew (nvm 及git)
mac 安装nvm 及git 万恶之源 mac 安装这些东西离不开Xcode。及homebrew 一、先说安装git步骤 通用: 方法一:使用 Homebrew 安装 Git(推荐) 步骤如下:打开终端(Terminal.app) 1.安装 Homebrew…...
【JavaSE】多线程基础学习笔记
多线程基础 -线程相关概念 程序(Program) 是为完成特定任务、用某种语言编写的一组指令的集合简单的说:就是我们写的代码 进程 进程是指运行中的程序,比如我们使用QQ,就启动了一个进程,操作系统就会为该进程分配内存…...
Go语言多线程问题
打印零与奇偶数(leetcode 1116) 方法1:使用互斥锁和条件变量 package mainimport ("fmt""sync" )type ZeroEvenOdd struct {n intzeroMutex sync.MutexevenMutex sync.MutexoddMutex sync.Mutexcurrent int…...
脑机新手指南(七):OpenBCI_GUI:从环境搭建到数据可视化(上)
一、OpenBCI_GUI 项目概述 (一)项目背景与目标 OpenBCI 是一个开源的脑电信号采集硬件平台,其配套的 OpenBCI_GUI 则是专为该硬件设计的图形化界面工具。对于研究人员、开发者和学生而言,首次接触 OpenBCI 设备时,往…...
TSN交换机正在重构工业网络,PROFINET和EtherCAT会被取代吗?
在工业自动化持续演进的今天,通信网络的角色正变得愈发关键。 2025年6月6日,为期三天的华南国际工业博览会在深圳国际会展中心(宝安)圆满落幕。作为国内工业通信领域的技术型企业,光路科技(Fiberroad&…...
