当前位置:网站首页>BUAA喜鹊筑巢
BUAA喜鹊筑巢
2022-07-06 03:23:00 【star-399】
【问题描述】
喜鹊通常会选择一棵树最高处分枝最多(即分枝最多的结点中高度最高的结点)的地方筑巢(结构最稳定)。给定一棵三叉树,计算出喜鹊筑窝的地点(可能有多个,多个时应按树前序遍历的顺序给出相应的结点信息,包括结点号以及按照前序遍历第几个访问到该结点)。例如下图是一颗三叉树:
该树中结点最多有三个分枝,拥有三个分枝的最高的结点为23号和15号结点,按照前序遍历顺序将会第19个访问到23号结点,第31个访问到15号结点。
要求:按照前序遍历访问三叉树的分枝时应先访问左分枝,再访问中间分枝,最后访问右分枝;根结点为第1个访问到结点,且树中最多有100个结点。
【输入形式】
先从控制台输入一个整数表示树结点关系的条目数,接着在下一行开始,从根开始依次输入树结点之间的关系。其中结点编号从数字1开始,如1表示树根结点,其它结点的编号大于1,不会重复,但编号没有规律。树中结点间关系用下面方式描述:
R S1 S2 S3
其中R为分叉结点,S1,S2,S3分别为树叉R的左、中、右子结点,由于是三叉树,S1,S2,S3中至多可以2项为空,该项为空时用0表示。各项间以一个空格分隔,最后有一个回车。如:
1 5 6 0
表明编号1的树根有两个子叉,编号分别为5和6。
注意:结点关系的输入顺序是依次先从根结点输入根与子结点的关系,再输入分叉结点与子结点的关系,输入某个结点关系时,其父结点一定已经存在,但不一定按照层次输入。
【输出形式】
按照前序遍历顺序输出分枝最多的结点中高度最高的结点信息,每个结点信息占一行,包括结点编号和按照前序遍历第几个访问到该结点,以一个空格分隔数据。
【样例输入】
18
1 2 3 4
4 5 0 0
3 6 7 8
2 9 10 0
7 21 22 0
21 23 24 0
23 25 26 27
9 28 29 0
28 30 31 37
30 32 0 0
31 33 36 0
33 34 35 0
5 11 12 13
11 14 0 0
12 15 0 0
13 16 0 0
15 17 18 19
19 20 0 0
【样例输出】
23 19
15 31
【样例说明】
输入了18条树结点关系,按照这些关系建立的三叉树如上图所示。该树中结点最多有三个分枝,拥有三个分枝的最高的结点为23号和15号结点,按照前序遍历顺序将会第19个访问到23号结点,第31个访问到15号结点。根结点为第1个访问到的结点。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXSIZE 102
struct triple_tree
{
int num;
struct triple_tree *child[3];
};
typedef struct queue
{
int num, when, level, point;
} queue;
typedef struct triple_tree tree;
queue result[MAXSIZE];
tree nodes[MAXSIZE];
int n, i, cup[3], head, j;
int count;
void tree_vt(tree *root, int level)
{
result[count].level = level;
result[count].num = root->num;
result[count].when = count + 1;
result[count].point = 0;
for (i = 0; i < 3; i++)
{
if (root->child[i] != NULL)
{
result[count].point += 1;
}
}
count++;
return;
}
void fvisit(tree *root, int level)
{
int i;
tree_vt(root, level);
for (i = 0; i < 3; i++)
{
if (root->child[i] != NULL)
{
fvisit(root->child[i], level + 1);
}
}
return;
}
int cmp(queue *a, queue *b)
{
if (a->point > b->point)
return -1;
else if (a->point == b->point && a->level > b->level)
return -1;
else if (a->point == b->point && a->level == b->level && a->when < b->when)
return -1;
return 1;
}
int main()
{
scanf("%d", &n);
while (n--)
{
scanf("%d%d%d%d", &head, &cup[0], &cup[1], &cup[2]);
for (i = 0; i < 3; i++)
{
if (cup[i] != 0)
nodes[head - 1].child[i] = &nodes[cup[i] - 1];
else
nodes[head - 1].child[i] = NULL;
}
}
for (i = 0; i < MAXSIZE; i++)
nodes[i].num = i + 1;
fvisit(&nodes[0], 1);
qsort(&result[0], count + 1, sizeof(queue), (const void *)cmp);
i = 0;
n = result[0].level;
while (result[i].level == n)
{
printf("%d %d\n", result[i].num, result[i].when);
i++;
}
return 0;
}
BUAAer?
边栏推荐
猜你喜欢
NR modulation 1
SWC介绍
3.1 rtthread 串口设备(V1)详解
真机无法访问虚拟机的靶场,真机无法ping通虚拟机
Web security SQL injection vulnerability (1)
1.16 - 校验码
Résumé des méthodes de reconnaissance des caractères ocr
BUUCTF刷题笔记——[极客大挑战 2019]EasySQL 1
Image super-resolution using deep convolutional networks(SRCNN)解读与实现
【SLAM】ORB-SLAM3解析——跟踪Track()(3)
随机推荐
手写数据库客户端
八道超经典指针面试题(三千字详解)
Precautions for single chip microcomputer anti reverse connection circuit
【SLAM】ORB-SLAM3解析——跟踪Track()(3)
继承day01
Quartz misfire missed and compensated execution
How to write compile scripts compatible with arm and x86 (Makefile, cmakelists.txt, shell script)
MADDPG的pythorch实现——(1)OpenAI MADDPG环境配置
Differences and application scenarios between resulttype and resultmap
Image super-resolution using deep convolutional networks(SRCNN)解读与实现
Princeton University, Peking University & UIUC | offline reinforcement learning with realizability and single strategy concentration
Yyds dry inventory what is test driven development
【Rust 笔记】18-宏
svg拖动点裁剪图片js特效
遥感图像超分辨重建综述
Arabellacpc 2019 (supplementary question)
[Li Kou] the second set of the 280 Li Kou weekly match
Redo file corruption repair
mysqldump数据备份
Résumé des méthodes de reconnaissance des caractères ocr