"二叉树的性质与推导及常见习题整理 "

简介: 这篇内容介绍了二叉树的一些性质及其推导。

一、性质推导

1. 若一个二叉树有n个节点,则该二叉树共有(n-1)条边。

推导:如图,可以理解为二叉树除了根节点外,每一个节点头上都有一条边指向它。因此,边的总数就是n-1




2. 若规定 根结点的层数为 1 ,则一棵 非空二叉树的第 i 层上最多有 2^(i-1)   (i>0) 个结点。

推导:当第i层满的时候,就是该层节点数最多的时候。如下图的完全二叉树,第一层最多1个节点,第二层最多2个节点,第三层最多4个节点,第四层最多8个节点……可以归纳出规律:第i层最多2^(i-1)个节点。





3. 若规定只有根结点的二叉树的深度为1,则深度为K的二叉树的最大结点数是 2^k -1


(k>=0)

推导:深度为K的二叉树最大节点的情况是该树为一棵满二叉树。将每一层节点数求和,即该树的总结点数。求和的过程是等比数列的求和过程,根据等比数列求和的公式(其中n是项数):




代入a1(首项)为2^0即1,q为2,n为k,可得最大节点数为: 2^k-1

4. 具有 n 个结点的完全二叉树的深度 k为log(n+1)上取整 。

推导:由性质3倒推可得:





向上取整即若一个数是3点几,则答案向上取4。


假设共有16个节点,n=16.则:2^k = 17,而2^4为16,2^5为32,因此k实际为4点几,但若k取4,则不够,还多了一个节点。因此k应当向上取5.


注意:这里的 k 还有另一种表示方式,即log(n)+1。此时 k 为log(n)+1向下取整。向下取整即3点几向下取3.



5. 对任何一棵二叉树 , 如果其 叶结点个数为 n0, 度为 2 的非叶结点个数为 n2, 则有 n0 = n2 + 1 (度为0的节点个数比度为2的节点个数多一个。)

推导:该结论的推导运用到了二叉树边与节点个数的关系。


假设度为0的节点有n0个,度为1的节点有n1个,度为2的节点有n2个,总结点数为N。首先可得:N = n0 + n1 + n2 ……①(节点个数关系)


同时,由性质1可得,该二叉树有N-1条边。度为0的节点发射出0条边,度为1的节点发射出1条边,度为2的节点发射出2条边。由此可得:


N-1 = 0*n0 + 1*n1 + 2*n2 ……②(边条数关系)


由①和②可得结论:n0 = n2 + 1


6. 对于具有 n 个结点的完全二叉树 ,如果按照 从上至下从左至右的顺序对所有节点从 0 开始编号 ,则对于 序号为  i 的结点有 :

       若i>0 ,则其 双亲结点序号为: (i-1)/2 ;若 i=0 , i 为根结点编号 ,无双亲结点。

       若2i+1<n,则其左孩子序号为: 2i+1; 否则无左孩子。

       若2i+2<n ,则其右孩子序号: 2i+2; 否则无右孩子。

推导:如下图规律所示。





若 i = 4,则其双亲序号为 (i-1)/2 即 (4-1)/2 为1;


左孩子2*i+1为9 < 总结点个数10,因此左孩子存在且序号为9;


右孩子2*i+2为10,不小于10,因此右孩子不存在。


若i = 5,则其双亲序号为(i-1)/2 即 2;


左孩子2*i+1为11大于10,因此左孩子不存在。由于该性质是针对完全二叉树的,因此其右孩子一定也不存在。


注意:若从1开始编号,则序号为i的节点的双亲节点序号为 i/2,左孩子节点为 2*i ,右孩子节点为 2*i + 1.


该结论可以不死记硬背,遇到的时候简单画图即可快速推导。







二、常见的二叉树性质习题


  1. 某二叉树共有 399 个结点,其中有 199 个度为 2 的结点,则该二叉树中的叶子结点数为()。


A、不存在这样的二叉树


B、200


C、198


D、199


答案选B。


由性质5可知,n0 = n2+1.n0 = 199+1 = 200


  1. 在具有 2n 个结点的完全二叉树中,叶子结点个数为()。


A n


B n+1


C n-1


D n/2


答案选A。该题运用到了性质5.

首先分析题干,如何求叶子节点的个数?和节点个数相关的公式有二:

n0 = n2 + 1,N = n0 + n1 + n2

已知总个数N为2n,那么只要知道n1即可求出n0.


这里有一个重要的结论:


在完全二叉树中,如果节点总个数为奇数,则没有度为1的节点;如果节点总个数为偶数,只有一个度为1的节点。



节点个数是偶数,只有一个度为1的节点

2n为偶数,因此有一个度为1的节点。

2n = n0 + 1 + n2 = n0 + 1 + n0 - 1

2n = 2n0

n0 = n,故选A



3.一个具有767个节点的完全二叉树,其叶子节点个数为()。

A 383


B 384


C 385


D 386


答案选B。


本题同上。此时共有奇数个节点,因此没有度为1的节点,即n1 = 0.


由 N = n0 + n1 + n2得: 767 = n0 + 0 + n0 - 1


n0 = 768/2 = 384


  1. 一棵完全二叉树的节点数为531个,那么这棵树的高度为()。


A 11


B 10


C 8


D 12


答案选B。


已知节点求高度,运用性质4,h = log(n+1)向上取证。h = log(531+1),向上取整为10,故选B。


  1. 在一颗度为3的树中,度为3的结点有2个,度为2的结点有1个,度为1的结点有2个,则叶子结点有( )个。


A.4


B.5


C.6


D.7


本题选C。

运用了边与节点个数的关系。

令n3 = 2;n2 = 1;n1 = 2;设总结点的个数为N

则由节点个数的关系得 N = n3 + n2 + n1 + n0,由边条数的关系得 N-1 = 3*n3 + 2*n2 + 1*n1 + 0*n0

联立可得:N = 2 + 1 + 2 + n0,N-1 = 3*2 + 2*1 + 1*2 + 0

n0 = 6


  1. 一颗拥有1000个结点的树度为4,则它的最小深度是( )。


A.5


B.6


C.7


D.8


答案选B


当这棵树每一层都是满的时,它的深度最小。也就是说,这棵树应当是一棵满四叉树。


假设高度为h,则由求二叉树节点个数的公式类比可知:根据等比数列求和公式得,这个数的节点个数为(4^h - 1) / 3


当h = 5,最大节点数为341,当h = 6, 最大节点数为1365,所以,最小深度应该向上取整为6。


7.在一颗完全二叉树中,某一个结点没有其左孩子,则该结点一定( )。


A.是根结点


B.是叶结点


C.是分支结点


D.在倒数第二层


答案选B.


完全二叉树中,如果一个节点没有左孩子,则一定没有右孩子,它必定为一个叶子节点。


最后一层一定为叶子节点,但是倒数第二层也可能存在叶子节点。




相关文章
|
关系型数据库 MySQL Shell
三、Docker常用命令
把 Docker 玩转,就像一个建筑师,需要掌握两套核心工具:一套用来管理你的“图纸”(镜像),另一套用来管理你用图纸盖好的“房子”(容器)。
914 3
|
数据采集 存储 算法
终于有人把数据挖掘讲明白了
在大数据时代,许多企业面临一个难题:数据存储量庞大,却难以从中挖掘真正价值。本文深入探讨了数据挖掘的核心概念与实践方法,解析了其与普通数据分析的区别,并通过真实案例展示了如何通过数据挖掘发现隐藏的业务规律。文章还详细介绍了数据挖掘的六个步骤及三大关键点,强调了业务理解与数据质量的重要性,帮助企业在实际应用中少走弯路,真正实现数据驱动决策。
终于有人把数据挖掘讲明白了
|
人工智能 文字识别 API
医疗票据OCR技术演进:从模板匹配到智能理解的突破
医疗票据OCR正从传统模板匹配迈向智能理解新阶段。快瞳科技融合OCR与医疗知识图谱,实现高精度、自适应识别,显著提升效率与准确性,推动医疗数字化智能化升级。
803 3
|
机器学习/深度学习 算法 数据挖掘
【机器学习】解释什么是K-means聚类?
【5月更文挑战第11天】【机器学习】解释什么是K-means聚类?
|
存储 消息中间件 开发框架
如何开发一套ERP系统(附架构图+流程图+代码参考)
ERP系统是企业资源计划的核心工具,有效解决信息孤岛、数据重复等问题,提升管理效率与运营成本控制能力。本文详解ERP系统的核心模块及订单管理模块的开发流程,涵盖功能设计、技术选型与代码示例,助力企业高效搭建信息系统。
|
存储 机器学习/深度学习 算法
C 408—《数据结构》图、查找、排序专题考点(含解析)
408考研——《数据结构》图,查找和排序专题考点选择题汇总(含解析)。
1855 29
|
资源调度 JavaScript 前端开发
Pinia 如何在 Vue 3 项目中进行安装和配置?
Pinia 如何在 Vue 3 项目中进行安装和配置?
1497 4
|
存储 人工智能 自然语言处理
《深度揭秘LDA:开启人工智能降维与分类优化的大门》
线性判别分析(LDA)是一种强大的监督学习降维方法,旨在通过最大化类间距离、最小化类内距离,将高维数据投影到低维空间,从而提升分类性能。LDA通过计算类内和类间散布矩阵,找到最优的投影方向,有效增强类别可分性,并过滤噪声与冗余信息。它在计算机视觉、自然语言处理及生物医学等领域有着广泛应用,显著提高了图像识别、文本分类和基因数据分析等任务的准确性和效率。
783 3
|
前端开发 Java 测试技术
综合案例【商品管理系统-Java基础版】(附完整源码)
综合案例【商品管理系统-Java基础版】(附完整源码)
939 9
|
前端开发 Java
【案例+源码】详解MVC框架模式及其应用
【案例+源码】详解MVC框架模式及其应用
1502 0