服务优化 要点提示

数据结构第五次作业（树）第四题：已知机场是由分叉点和登机口组成的三叉树，根据客流量调整机场登机口顺序。

1. 输入

数据输入分两部分：前一部分描述机场的树结构，给出了分叉结点的子结点信息；后一部分给出了每个登机口的客流量。

此题的数据输入共有 3 处难点:

1. 第一部分的行数未知
2. 第一部分每一行的数据个数未知
3. 第二部分的行数未显式给出

解决方法:

对于第一部分来说，每行的第一个数据表示一个父结点的编号，后面是子结点。所以首先输入第一个编号，当遇到 -1 表示第一部分结束。

while (1) {
    int id;
    scanf("%d", &id);
    if (id == -1)
        break;
    // code here ...
}

而后，读入这一行的后续部分，即可借鉴与上面的循环类似的思路，再嵌套一层循环，读入子结点编号，判断遇到 -1 则结束。

// 输入第一部分完整代码框架
while (1) {
    int id;
    scanf("%d", &id);   // 输入每行第一个数据 (父结点编号)
    if (id == -1)
        break;
    int count = 0;  // 统计子结点数量
    while (1) {
        int child;
        scanf("%d", &child);
        if (child == -1)    // 该行输入结束
            break;
        // TODO: 将编号为 child 的节点保存为 id 的子结点
    }
}

对于第二部分，由题意，行数就是登机口结点的个数，这里也有两种处理办法：一是当成行数未知，用 while (scanf("%d %d", &a, &b) != EOF) 的循环读入，一边循环一边计数得到登机口数量；二是在读入第一部分时，对输入的子结点编号进行判断，统计编号小于 100 的个数。

2. 树的存储

如果采用传统的链式存储方式，在建树时需要递归遍历已有的部分树来找到当前的父结点或子结点，造成不必要的代码难度（递归遍历树）与时间复杂度（找一次 $O(n)$, 建树总体 $O(n^2)$ ）。但是在此题中，由于树的结点是有唯一编号的，因此我们可以将编号作为索引来加速对树结点的查找。于是很自然地我们可以想到：

用数组来管理树的结点，数组的下标就是这个结点的编号。这样在建树的过程中我们就可以通过数组下标的方式根据编号直接找到树的结点，单次查找时间复杂度 $O(1)$。

另外，虽然此题的树是三叉树，但是三个子结点之间除了有序以外，左中右三个位置本身并无其他特殊性。因此可以用数组来代替三个单独的变量来管理一个结点的子结点。这样我们不但可以用循环来遍历子结点，采用数组也很方便地扩展为四叉树甚至更多叉树（例如：字典树是 26 叉树）

struct Node {
    struct Node *left, *middle, *right; // not so good
};
struct Node {
    struct Node *child[3]; // better than above
    int numChildren; // 用一个变量记录子结点数量，即 child 数组非空部分的长度
};

3. 广度优先遍历

题目中提到要对树进行从上到下（树根在最上，所以是从近到远），从左到右的遍历。简单分析可知这种遍历顺序是层序遍历，也就是广度优先遍历。

广度优先遍历需要借助队列，如果将树换成（未来将要学习的）图，这种方法就是广度优先搜索 (BFS)。

在这里给出一个基本的代码结构：

将起点加入队列;
while (队列非空) {
    取出队列首部 (记为 now) 并将其弹出队列;
    对 now 进行访问操作（输出、计数等）;
    for (next : now 的邻接元素) {
        if (next 从未被加入队列过)
            将 next 加入队列;
    }
}

其中判断 (next 从未被加入队列过) 在现阶段可以暂不考虑，因为树的一个结点只能从其父结点到达，因此一定不会重复加入队列，但在图中则需要考虑这一点。感兴趣的同学可自行学习广度优先搜索算法。