完全二叉树的权值
2021/10/1 23:12:29
本文主要是介绍完全二叉树的权值,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
试题 历届真题 完全二叉树的权值【第十届】【省赛】【A组】
问题描述
给定一棵包含 N 个节点的完全二叉树,树上每个节点都有一个权值,按从
上到下、从左到右的顺序依次是 A1, A2, · · · AN,如下图所示:
现在小明要把相同深度的节点的权值加在一起,他想知道哪个深度的节点
权值之和最大?如果有多个深度的权值和同为最大,请你输出其中最小的深度。
注:根的深度是 1。输入格式
第一行包含一个整数 N。
第二行包含 N 个整数 A1,
A2, · · · AN 。输出格式
输出一个整数代表答案。
样例输入
7
1 6 5 4 3 2 1样例输出
2
思路:用一个数组来存这棵树,1为根节点所在,然后左孩子就是i*2,右孩子就是i * 2+1 ;树存完后,层序遍历一遍就ok了,
这里的层序遍历的时候,我们有两层循环,外层是q队列不为空,内层是将当前层的结点全部pop(),这样就可以计算整层的权值和了
#include <iostream> #include <queue> using namespace std; const int N = 1e5+5; //每个点有下标,和值,我这里用一个结构体表示, typedef struct{ int no, value; }Node; //队列 queue<Node> q; //tree存树的数组,total[i]表示第i层的权值和,为什么是18? //因为2^18已经大于了本题的最大范围了 int tree[N], n, total[18]; int main() { //表示计算第no层的权值 int no = 1; cin >> n; for ( int i = 1; i <= n; ++i ) { cin >> tree[i]; } //把头结点入队 Node t = {1, tree[1]}; q.push(t); //层序遍历 while ( !q.empty() ) { //size表示当前队列中的元素个数,即当前层的结点有多少个 int size = q.size(), sum = 0; while ( size-- ) { Node temp = q.front(); q.pop(); //累加当前层权值 sum += temp.value; //有左孩子 if ( temp.no * 2 <= n ) { Node te = {temp.no*2, tree[temp.no*2]}; q.push(te); } //有右孩子 if ( temp.no * 2 + 1 <= n ) { Node te = {temp.no*2+1, tree[temp.no*2+1]}; q.push(te); } } total[no++] = sum; } int maxn = total[1], maxno = 1; for ( int i = 1; i < no; ++i ) { if ( maxn < total[i] ) { maxn = total[i]; maxno = i; } } cout << maxno << endl; return 0; }
看图吧:
end
这篇关于完全二叉树的权值的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-02springboot项目无法注册到nacos-icode9专业技术文章分享
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)