首页 > 代码库 > 数据结构作业——brothers
数据结构作业——brothers
brothers
Description
给你一棵节点编号从 1 到 n 的,根节点为 1 的二叉树。然后有 q 个询问,每个询问给出一个整数表示树的节点,要求这个节点的兄弟节点数目和堂兄弟节点
的数目。如下给出定义:兄弟节点:父节点相同的互为兄弟节点;堂兄弟节点:双亲在同一层的节点互为堂兄弟节点(要求双亲编号不同)。
Input
输入第一行为一个正整数 n 表示树的节点数目。从第 2 行到第 n+1 行,每行两个整数 l,r,分别表示编号为 i(i 从 1 到 n)的节点的左右儿子,0 表示没有儿子节点。接下来一行有一个整数 q,表示询问数目。紧接着 q 行,每行一个整数,表示要询问的节点。
30%的数据:n<=20,q<=10;
60%的数据:n<=1000,q<=n;
100%的数据:n<=100000,q<=n;
Output
输出 q 行,每行两个数,第一个数表示兄弟节点数目,第二个数表示堂兄弟节点数目。
Sample Input
8
2 3
4 0
5 7
0 8
6 0
0 0
0 0
0 0
3
4
5
6
Sample Output
0 2
1 1
0 1
思路
根据给出的每个节点的左右儿子建树,然后宽搜,给每一层编号,存储每一层各有什么节点,这样就可以很容易判断其兄弟节点以及堂兄弟节点的个数了
#include<iostream>#include<cstdio>#include<cstring>#include<vector>#include<queue>using namespace std;const int maxn = 100005;struct Tree{ int lson,rson; Tree():lson(0),rson(0){}}tree[maxn];vector<int>itv[maxn];int fa[maxn],hei[maxn];void bfs(int st){ int cnt = 1; queue<int>que,tque; que.push(st); while (!que.empty()) { while (!que.empty()) { int tmp = que.front(); que.pop(); hei[tmp] = cnt; itv[cnt].push_back(tmp); if (tree[tmp].lson) tque.push(tree[tmp].lson); if (tree[tmp].rson) tque.push(tree[tmp].rson); } if (tque.empty()) return; cnt++; while (!tque.empty()) { que.push(tque.front()); tque.pop(); } }}int main(){ //freopen("input.txt","r",stdin); //freopen("output.txt","w",stdout); int n,q,lson,rson,i; scanf("%d",&n); for (i = 1;i <= n;i++) { scanf("%d%d",&lson,&rson); tree[i].lson = lson,tree[i].rson = rson; fa[lson] = i,fa[rson] = i; } bfs(1); scanf("%d",&q); while (q--) { int x = 0; scanf("%d",&n); if (tree[fa[n]].lson && tree[fa[n]].rson) x = 1; n = itv[hei[n]].size(); printf("%d %d\n",x,n - x - 1); } return 0;}
数据结构作业——brothers
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。