试题 F: 完全二叉树的权值
时间限制: 1.0s 内存限制: 256.0MB 本题总分：15 分
【问题描述】
给定一棵包含 N 个节点的完全二叉树，树上每个节点都有一个权值，按从上到下、从左到右的顺序依次是 A1, A2, · · · AN，如下图所示：
现在小明要把相同深度的节点的权值加在一起，他想知道哪个深度的节点权值之和最大？如果有多个深度的权值和同为最大，请你输出其中最小的深度。
注：根的深度是 1。
【输入格式】
第一行包含一个整数 N。
第二行包含 N 个整数 A1, A2, · · · AN 。
【输出格式】
输出一个整数代表答案。
【样例输入】
7
1 6 5 4 3 2 1
【样例输出】
2
【评测用例规模与约定】
对于所有评测用例，1 ≤ N ≤ 100000，−100000 ≤ Ai ≤ 100000。
算法分析：
1.数据结构：使用双重指针代替二维数组（题目为明确给出数据范围，使用 “ 边长数组 ” 动态分配空间）
2.
代码实现（C++版本）
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <malloc.h>
#include <string.h>
using namespace std;
int n;
int main()
{
cin >> n;
int count=0, deep=0;//变量均要进行初始化
while (count < n)
{
deep++;
count += pow(2.0, (deep - 1));
}//计算出节点个数为n 的完全二叉树的深度
int** tree=(int**)malloc((deep + 1) * sizeof(int *));
for (int i = 0; i < deep+1; i++)
{
tree[i] = (int*)malloc((deep + 1) * sizeof(int*));
memset(tree[i], 0, (deep + 1) * sizeof(int));
}//对完全二叉树逐层分配空间，并初始化
count = 0;
int temp_sum=0, temp_max=0,res=0;
for (int temp_deep = 0; temp_deep < deep; temp_deep++)
{
for (int i = 0; i < pow(2.0, temp_deep); i++)
{
cin >> tree[temp_deep][i];
count++;
if (count >= n) break;//完全二叉树的最后一层可以不填满
}
}//对二叉树进行初始化，将值全部放入二叉树中
int deep_max = 0, sum_max = 0;
for (int temp_deep = 1; temp_deep <= deep; temp_deep++)
{
int sum = 0;
for (int i = 1; i <= pow(2.0, (temp_deep-1)); i++) sum += tree[temp_deep][i];
if (sum > sum_max)
{
deep_max = temp_deep;
deep_max = temp_deep;
}
}//逐层比较二叉树权值，并输出权值最高的那层
cout << res << endl;
return 0;
}
/*
源代码（C语言版本）
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include <iostream>//头文件结束
using namespace std;
int n;
int main()
{
cin>> n;
int count = 0, deep = 0;
while (count < n)
{
deep++;
count += pow(2.0, (deep - 1));
}//计算节点总数为n的完全二叉树的深度
int** tree;
tree = (int**)malloc((deep + 1) * sizeof(int*));
for (int i = 0; i < deep + 1; i++)
{
tree[i] = (int*)malloc((deep + 1) * sizeof(int));
memset(tree[i], 0, (deep + 1) * sizeof(int));
}//双指针+malloc存储完全二叉树，节点个数未知
// 将输入的值让完全二叉树的规则输入数组
count = 0;
for (int temp_deep = 1; temp_deep <= deep; temp_deep++)
{
for (int i = 1; i <= pow(2.0, temp_deep - 1); i++)
{
scanf("%d", &tree[temp_deep][i]);
count++;
if (count >= n) break; // 当所有元素写入之后推出输入循环
}
}
// 比较同一深度的节点权值之和
int max_deep = 0, max_sum = 0;
for (int temp_deep = 1; temp_deep <= deep; temp_deep++)
{
int sum = 0;
for (int i = 1; i <= pow(2.0, temp_deep - 1); i++)
{
sum += tree[temp_deep][i];
}
if (sum > max_sum)
{
max_sum = sum;
max_deep = temp_deep;
}
}
printf("深度为 %d 的节点权值之和最大\n", max_deep);
printf("\n");
system("pause");
}
Pow函数详解：
头文件：#include <math.h>
pow() 函数用来求 x 的 y 次幂（次方），x、y及函数值都是double型 ，其原型为：
double pow(double x, double y);
pow()用来计算以x 为底的 y 次方值，然后将结果返回。设返回值为 ret，则 ret = x y 。
可能导致错误的情况：
如果底数 x 为负数并且指数 y 不是整数，将会导致 domain error 错误。
如果底数 x 和指数 y 都是 0，可能会导致 domain error 错误，也可能没有；这跟库的实现有关。
如果底数 x 是 0，指数 y 是负数，可能会导致 domain error 或 pole error 错误，也可能没有；这跟库的实现有关。
如果返回值 ret 太大或者太小，将会导致 range error 错误。
错误代码：
如果发生 domain error 错误，那么全局变量 errno 将被设置为 EDOM；
如果发生 pole error 或 range error 错误，那么全局变量 errno 将被设置为 ERANGE。
Math.pow(底数,几次方)
如：double a=2.0;
double b=3.0;
double c=Math.pow(a,b);
就是2的三次方是多少；
c最终为8.0；
*/