刷题刷出新高度,偷偷领先!偷偷领先!偷偷领先! 关注我们,悄悄成为最优秀的自己!

简答题

满二叉树:一棵二叉树,如果每一层的节点数都达到最大值,则这个二叉树就是满二叉树。即如果一棵二叉树的层数为K,且结点总数是(2^k)-1,那么它就是满二叉树。

完全二叉树:一棵深度为K的二叉树,除第K层外,其他各层(1至k-1层)的节点数都达到最大值,目第K层的所有节点都连续集中在左边,那么它就是完全二叉树。

节点:包含一个数据元素及若干指向子树分支的信息。

权值:对节点赋予的有意义的数量值。

深度:也被称为树的高度,树中所有节点的层次最大值称为树的深度,例如下图中的二叉树深度都为4。

编程实现:

给出一棵包含n个节点的完全二叉树,节点按照从上到下、从左到右的顺序依次排序,每个节点上都有一个权值,如下图现在需要将同一深度节点的权值加在一起,然后比较每个深度的权值之和,输出权值之和最大的深度值。如果有多个深度的权值之和相同,则输出其中最小的深度(如:深度2权值之和为5,深度3权值之和也为5,则输出2)。

注:根的深度为1

第一行输入完全二叉树节点的总数量n(5<n<101),第二行输入n个正整数作为每个节点的权值。输出权值之和最大的深度值(如果有多个深度的权值之和相同则输出其中最小的深度值)。

例如:上图的二叉树,第一行输入为6,第二行输入为1 5 6 1 2 3。深度1的权值之和为1,深度2的权值之和为11,深度3的权值之和为6。其中深度2的权值之和最大,则输出2。

输入描述

第一行输入一个正整数n(5<n<101)作为节点的总数量

第二行输入n个正整数,且n个正整数之间以一个空格隔开

输出描述

输出权值之和最大的深度值


样例输入1

6
1 5 6 1 2 3

样例输出1

2

样例输入2

8
1 5 6 1 2 3 4 100

样例输出2

4


使用微信搜索喵呜刷题,轻松应对考试!

答案:

首先,根据题目要求,需要构建一个完全二叉树,并根据节点数量计算出树的深度。然后,从根节点开始,逐层遍历二叉树,计算每层节点的权值之和,并找到权值之和最大的深度。

解析:

【喵呜刷题小喵解析】:
首先,我们需要了解满二叉树和完全二叉树的概念。满二叉树是每一层节点数都达到最大值的二叉树,而完全二叉树是深度为K的二叉树,除第K层外,其他各层节点数都达到最大值,且第K层的所有节点都连续集中在左边。

对于这个问题,我们需要构建一个完全二叉树,并根据节点数量计算出树的深度。然后,从根节点开始,逐层遍历二叉树,计算每层节点的权值之和,并找到权值之和最大的深度。

具体实现步骤如下:

1. 根据输入的节点数量n,计算出完全二叉树的深度。对于完全二叉树,深度的计算公式为$k = \lfloor \log_{2}n \rfloor + 1$,其中$\lfloor x \rfloor$表示不大于x的最大整数。

2. 构建完全二叉树。由于完全二叉树的节点按照从上到下、从左到右的顺序依次排序,因此可以根据节点数量n和深度k,构建出完全二叉树。

3. 从根节点开始,逐层遍历二叉树,计算每层节点的权值之和。对于每一层,从根节点开始,向右遍历该层的所有节点,计算权值之和。

4. 找到权值之和最大的深度。遍历完所有层后,比较每层权值之和,找到权值之和最大的深度。如果有多个深度的权值之和相同,则输出其中最小的深度。

需要注意的是,由于完全二叉树的节点按照从上到下、从左到右的顺序依次排序,因此在构建完全二叉树时,可以根据节点数量n和深度k,计算出每个节点的位置,从而构建出完全二叉树。同时,在遍历二叉树时,由于完全二叉树的特性,可以通过节点的位置计算出其父节点和左右子节点的位置,从而快速遍历二叉树。
创作类型:
原创

本文链接:满二叉树:一棵二叉树,如果每一层的节点数都达到最大值,则这个二叉树就是满二叉树。即如果一棵二叉树的层

版权声明:本站点所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明文章出处。

让学习像火箭一样快速,微信扫码,获取考试解析、体验刷题服务,开启你的学习加速器!

分享考题
share