[数据结构与算法]完全二叉树的权值

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