技术交流 | 工业界 | N叉树有约束排序，功能与性能讨论

问题背景

在某通信网络中，存在三种网络站点角色，一种是通信主站（简称M），一种是通信中继站（简称P），一种是通信子站（简称S）。该通信网络的网络拓扑是树形网络结构，其中通信主站M是根节点，通信子站S是叶子节点，通信中继站P则是除根节点/叶子节点之外的站点。

每一个通信节点可以包含两种资源res_a和res_b。其中，res_a资源占用的时间长度固定为R1，而res_b根据资源类型不同，资源占用的时间可能为R1或R2（其中R1≤R2）。同一个节点上res_a和res_b不能同时占用，且res_a用完之后，res_b才能使用。对于每个节点资源属性展示如下：

typedef struct node_resource {
    uint32_t res_a;   // 固定=R1
    uint32_t res_b;   // R1/R2 (R1≤R2)
} node_res;

通信主站M能够掌握全局拓扑信息，包括每个节点所使用的资源信息。

功能要求

根据以下规则约束，主站节点M根据拓扑情况对整个网络的节点排序，并输出排序结果。

规则1：在一个时间段内，不同节点的res_a和res_b可以共存。即不同节点的res_b可以共用res_a的时间段。

规则2：排序顺序不能子树的节点在前，父节点在后。

规则3：不违反其他规则，排序按照层级顺序，先输出根节点，再输出中间节点，最后输出叶子节点。

性能要求

1. 支持≥3000个节点的网络拓扑管理；
2. 空间内存使用量≤20KByte；
3. 运行时间≤20ms（200MHz主频）。

示例

网络拓扑示例：

                 1 
              /  |  \
            2    3    4
          /      |     \
        5        6      7
        .
        8
        |
        9

各个节点资源占用示例：

R1 = 1;
R2 = 2;
node_res node_1 = {R1, R1}; // res_a, res_b
node_res node_2 = {R1, R1}; // res_a, res_b
node_res node_3 = {R1, R1}; // res_a, res_b
node_res node_4 = {R1, R1}; // res_a, res_b
node_res node_5 = {R1, R2}; // res_a, res_b
node_res node_6 = {R1, R1}; // res_a, res_b
node_res node_7 = {R1, R1}; // res_a, res_b
node_res node_8 = {R1, R1}; // res_a, res_b
node_res node_9 = {R1, R1}; // res_a, res_b
注：资源上，node_5资源的特殊性，包括不一样的res_b为R2。

输出结果：

1,2,5,3,4,8,6,7,9