SCAU 18924 二叉树的宽度
文章目录
- 题目描述
- Description
- 输入格式
- 输出格式
- 输入样例
- 输出样例
- 思路
- 代码
本菜鸡第一次写blogT T，开始好好学习。
输入输出使用了C++的iostream。
题目描述
Description
二叉树的宽度指的是具有节点数目最多的那一层的节点个数。
1
/ \
2 3
/
4
答案为2, 第二层节点数最多，为2个节点。
输入格式
共n行。
第一行一个整数n，表示有n个结点，编号为1至n。（1<=n<=50）
第二行至第n行，每行有两个整数x和y，表示在二叉树中x为y的父节点。x第一次出现时y为左孩子
输出格式
输出二叉树的宽度。
输入样例
5
1 2
1 3
2 4
2 5
输出样例
2
思路
( 2021/06/02：oj上似乎新增了一个案例，是像下图这样的父节点还没出现，它的孩子先出了，于是就先用另外一个结构体临时将数据保存起来，用sort函数根据父节点的数字编号排个序，其他照旧就可以了）
通过一个数组level记录每一个结点所在的层数，用结点对应数字作为下标进行存储。
结点的层数=父节点的层数+1，通过父结点的数字可以找到level数组中记录的父结点的层数。
用一个数组A存储每一层的结点个数。
在记录每一个结点的层数level时，level层的结点个数自增一。
用Max记录最大的层节点数。
并比较当前level的个数是否最大，更新Max。
代码
#include <iostream>
#include <algorithm>
using namespace std;
#define For(i,a,b) for(int i=a;i<b;i++)
//存储结点对应的层数
int level[100];
//临时存放数据的结构体数组
/*----*/
typedef struct dataTemp
{
int parent;
int child;
//父结点小的排在前面
//内嵌运算符重定义，这样子直接sort就可以了，不需要另外定义一个bool函数
bool operator <(const dataTemp &d)const{
return parent<d.parent;}
}T;
T temp[100];
/*----*/
//A[i]用来存储第i层的结点个数
int A[10005]= {0};
int main()
{
int n;//结点的总个数
cin>>n;
//特殊情况 结点个数为1时二叉树的宽度为1
if(n==1)
cout<<1<<endl;
else
{
//有改动的地方
/*----*/
For(i,0,n-1)
{
//先放进临时结构体数组里面
cin>>temp[i].parent>>temp[i].child;
}
//让结构体数组中保存的父节点与子节点的关系，
//根据父节点的数字编号，从小到大排序
//相当于是把数据先整理一下吧
sort(temp,temp+n-1);
level[temp[1].parent]=1;
int Max=0;
For(i,0,n-1)
{
int p,c;
p=temp[i].parent;
c=temp[i].child;
//记录子节点的层数，为父节点的层数+1
level[c]=level[p]+1;
//该层的结点个数自增1
A[level[c]]++;
//比较该层的结点个数是否最大，更新Max
if(A[level[c]]>Max)
Max=A[level[c]];
}
//输出最大的层结点个数
cout<<Max<<endl;
}
return 0;
}