蓝桥杯备战日志(Python)8-完全二叉树的权值(二叉树的性质)

哈妹 lv.1

发布时间：2023-02-11 12:24:55 263

原题

给定一棵包含 N 个节点的完全二叉树，树上每个节点都有一个权值，按从上到下、从左到右的顺序依次是，如下图所示：

现在小明要把相同深度的节点的权值加在一起，他想知道哪个深度的节点权值之和最大？如果有多个深度的权值和同为最大，请你输出其中最小的深度。

注：根的深度是 1。

蓝桥杯备战日志(Python)8-完全二叉树的权值(二叉树的性质)_完全二叉树_03

分析

完全二叉树

在完全二叉树中，对于树的任意一个结点，若其有右结点，则一定有左结点；反之不一定。

蓝桥杯备战日志(Python)8-完全二叉树的权值(二叉树的性质)_权值_04

图· 完全二叉树（来源：百度百科）

性质

树的第i层的结点编号：以2^i-1开始，2ⁱ-1结束；
N个结点的完全二叉树的深度（高度）为int(log₂N) + 1

注：

以上性质画个图很容易推导出来，不必死记；其它性质可由基本性质综合推导，理解即可。

本题的解题思路用到了以上两个性质，具体实现见下述源码。

源码

import math

N = int(input())
An = [int(i) for i in input().split()]

h = int( math.log(N,2) )+1  # 该二叉树的高度(深度)
num_max = Sn[1]
h_res = 1
for j in range(2,h+1):
    i_start = 2**(j-1)-1  # 减1是因为An的索引从0开始的
    i_end = 2**j
    # 这里需要注意i_end可以超出结点的总个数，即N
    sum_weight = sum(An[i_start:i_end])
    if sum_weight > num_max:
        num_max = sum_weight
        h_res = j

if sum(An[i_end:]) > num_max:
    h_res = h
print(h_res)

测试数据：

①输出：2

7
1 6 5 4 3 2 1

②输出：5

31
0 -87 62 100 -77 -90 -11 20 -75 49 -25 24 -48 15 -30 29 15 -81 0 -34 30 -41 67 72 17 56 18 19 10 -55 68

上一篇：蓝桥杯备战日志(Python)7-求和(前缀和)

文章来源： https://blog.51cto.com/gpnuCITlabCar/6036357

特别声明：以上内容（图片及文字）均为互联网收集或者用户上传发布，本站仅提供信息存储服务！如有侵权或有涉及法律问题请联系我们。