结题报告--P5551洛谷--Chino的树学
题目:点此
题目描述
Chino树是一棵具有某种性质的满二叉树,具体来说,对于这棵树的每一个非叶子节点,它的左子节点(A)(A)(A)的右子节点(C)(C)(C)与它的右子节点(B)(B)(B)的左子节点(D)(D)(D)的值相同,且CCC与DDD下方的子树也完全相同。现在,Chino想知道,要如何从根节点走到其中任意叶节点使路上经过的节点的权值之和最大。
思路
先分析一下Chino树(满二叉树)的性质(节点编号)。
k层的满二叉树的最后一个结点的编号是2k-1,第一个叶子结点的编号是2k-1,由此可知,判断节点是否为叶子:if(i>=pow(2,k-1)//i为结点编号 判断此编号是否有对应节点:if(i>=0&&i<=pow(2,k)-1)//i为编号
定义一个变量n_1存储2k-1,再定义一个变量x=n_1*2-1(就是2k-1)。
本题难点之一就是把以深搜序列输入的树变成在数组里存储的树(数组存储是广搜序列),这个问题的解决方法是:在递归建树的函数里加一个参数now_number,表示现在是数组下标几了,因为数组下标是可以计算的:左子树下标:now_number*2,右子树下标:now_number*2+1。再加一个max_node_number,表示最大的结点编号,判断是否有左子树或右子树。
接下来就是判断最大值了。使用先根遍历遍历二叉树,由于这棵树是用数组存储的,所以这篇博客里的in_oder函数的参数可以变为now_number,再加一个now_weight,表示现在的结点权值和。
这个函数里执行:先更新now_weight,把此节点权值加进去。然后判断此节点是否为叶子,若是则判断是否为最大值,若是则更新最大值,结束,不是叶子则按照先根遍历的方法继续遍历。
最后主函数就是这些函数的结合。
(犯的错误和收获全部丢失,无法叙述)
代码:
#include <iostream>
#include <cstdio>
using namespace std;
int tree[];
int read()
{
int s=,w=;
char ch=getchar();
while(ch<''||ch>'')
{
if(ch=='-')
w=-;
ch=getchar();
}
while(ch>=''&&ch<='')
s=s*+ch-'',ch=getchar();
return s*w;
} void maketree(int now_number,int max_node_number){
int now_node;
now_node=read();
tree[now_number]=now_node;
if(now_number*>max_node_number){
return ;
}
maketree(now_number*,max_node_number);
maketree(now_number*+,max_node_number);
}
int pow(int r){
if(r==){
return ;
}
int data=;
if(r%==){
data=;
}
int index=pow(r/);
return index*index*data;
}
int maxx,n_1;
void pre_oder(int now_weight,int now_number){
now_weight+=tree[now_number];
if(now_number>=n_1){
if(now_weight>maxx){
maxx=now_weight;
}
return ;
}
pre_oder(now_weight,now_number*);
pre_oder(now_weight,now_number*+);
}
int main(){
int n;
n=read();
n_1=pow(n-);
int x=n_1*-;
maketree(,x);
pre_oder(,);
cout << maxx;
return ;
}
代码
最新文章
- C#开发微信门户及应用(4)--关注用户列表及详细信息管理
- mysql常用函数
- REGEXP 正则的实现两个字符串组的匹配。(regexp)
- 修改PHP上传文件大小限制的方法
- html5 三角形
- 深入理解JS异步编程四(HTML5 Web Worker)
- PLSQL登录弹出空白框如何解决
- CoffeeRobotTeam项目组报告
- PHP组合模式、策略模式
- 【转】Enable ARC in a Cocos2D Project: The Step-by-Step-How-To-Guide Woof-Woof!
- MFC 单文档中动态添加菜单项和响应菜单事件
- 转 Could not create the view: An unexpected exception was thrown.问题解决
- 带着SMART原则重新出发
- 【原创】一文掌握 Linux 性能分析之 I/O 篇
- 宝塔linux面版安装网站环境 自动化
- 登录views
- python3编写网络爬虫19-app爬取
- MySQL学习笔记Windows篇<;一>; Welcome to MySQL
- Flask 中的蓝图(BluePrint)
- input事件手机端可能会影响手写