完全二叉树的权值

试题 历届真题 完全二叉树的权值【第十届】【省赛】【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

上一篇:Vue购物车案例


下一篇:2021-09-28