BUAA喜鹊筑巢

【问题描述】

喜鹊通常会选择一棵树最高处分枝最多（即分枝最多的结点中高度最高的结点）的地方筑巢（结构最稳定）。给定一棵三叉树，计算出喜鹊筑窝的地点（可能有多个，多个时应按树前序遍历的顺序给出相应的结点信息，包括结点号以及按照前序遍历第几个访问到该结点）。例如下图是一颗三叉树：

该树中结点最多有三个分枝，拥有三个分枝的最高的结点为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？