解题思路

1. 数据结构设计 用一个结构体（或类）存储单个节点的全部信息：

   • feature_index 分裂特征下标
   • threshold 分裂阈值
   • left 左子节点行号
   • right 右子节点行号
   • label 分类结果（仅在叶子节点有效）

2. 读取模型

   • 读取 $m$ 个节点并存入数组或列表，编号即其行号

3. 推理过程

   • 对每个样本，从根节点 (0) 开始
   • 如果当前节点是叶节点（feature_index == -1），输出该节点分类结果
   • 否则，比较样本在 feature_index 特征上的值与 threshold，选择走向左或右子节点
   • 重复直到到达叶节点

4. 时间复杂度 对每个样本，最多遍历树的高度 $h$，因此时间复杂度为 $O(n \cdot h)$，节点总数为 $m$，一般 $h \ll m$ 空间复杂度为 $O(m)$。

C++

#include <iostream>
#include <vector>
using namespace std;

// 定义节点结构体
struct Node {
    int feature_index; // 分裂特征下标
    float threshold;   // 分裂阈值
    int left;          // 左子节点行号
    int right;         // 右子节点行号
    int label;         // 分类结果
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int f, m, n;
    cin >> f >> m >> n;

    vector<Node> tree(m);
    // 读取决策树节点信息
    for (int i = 0; i < m; i++) {
        cin >> tree[i].feature_index >> tree[i].threshold
            >> tree[i].left >> tree[i].right >> tree[i].label;
    }

    // 对每个样本进行推理
    for (int i = 0; i < n; i++) {
        vector<float> features(f);
        for (int j = 0; j < f; j++) {
            cin >> features[j];
        }
        int current = 0; // 从根节点开始
        while (true) {
            if (tree[current].feature_index == -1) {
                // 到达叶子节点，输出分类结果
                cout << tree[current].label << "\n";
                break;
            }
            // 根据阈值选择左右子节点
            if (features[tree[current].feature_index] <= tree[current].threshold) {
                current = tree[current].left;
            } else {
                current = tree[current].right;
            }
        }
    }
    return 0;
}

Python

# 定义节点类
class Node:
    def __init__(self, feature_index, threshold, left, right, label):
        self.feature_index = feature_index  # 分裂特征下标
        self.threshold = threshold          # 分裂阈值
        self.left = left                    # 左子节点行号
        self.right = right                  # 右子节点行号
        self.label = label                  # 分类结果

# 读取输入
f, m, n = map(int, input().split())

tree = []
for _ in range(m):
    fi, thr, l, r, lbl = input().split()
    # 转换数据类型，分裂阈值是 float
    tree.append(Node(int(fi), float(thr), int(l), int(r), int(lbl)))

# 推理过程
for _ in range(n):
    features = list(map(float, input().split()))
    current = 0  # 从根节点开始
    while True:
        node = tree[current]
        if node.feature_index == -1:
            # 到叶子节点
            print(node.label)
            break
        if features[node.feature_index] <= node.threshold:
            current = node.left
        else:
            current = node.right

Java

import java.util.*;

public class Main {
    // 定义节点类
    static class Node {
        int feature_index; // 分裂特征下标
        double threshold;  // 分裂阈值
        int left;          // 左子节点行号
        int right;         // 右子节点行号
        int label;         // 分类结果
        Node(int fi, double thr, int l, int r, int lbl) {
            feature_index = fi;
            threshold = thr;
            left = l;
            right = r;
            label = lbl;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int f = sc.nextInt();
        int m = sc.nextInt();
        int n = sc.nextInt();
        Node[] tree = new Node[m];
        // 读取决策树节点
        for (int i = 0; i < m; i++) {
            int fi = sc.nextInt();
            double thr = sc.nextDouble();
            int l = sc.nextInt();
            int r = sc.nextInt();
            int lbl = sc.nextInt();
            tree[i] = new Node(fi, thr, l, r, lbl);
        }
        // 处理每个样本
        for (int i = 0; i < n; i++) {
            double[] features = new double[f];
            for (int j = 0; j < f; j++) {
                features[j] = sc.nextDouble();
            }
            int current = 0;
            while (true) {
                Node node = tree[current];
                if (node.feature_index == -1) {
                    System.out.println(node.label);
                    break;
                }
                if (features[node.feature_index] <= node.threshold) {
                    current = node.left;
                } else {
                    current = node.right;
                }
            }
        }
        sc.close();
    }
}

题目内容

在无线通信系统中为了资源调配更加合理和及时，需要对未来一段时间网络的负载做出预判以确定资源调配的优先级。决策树是一种常用的模型，可以根据采集到的状态数据，结合时间段、天气等因素来推测合理的资源调配优先级。现在将一个训练好的分类决策树模型$Tree$ 安装在系统中，请实现决策树的推算算法，根据输入特征返回资源调配优先级。

输入描述

输入包含多行数据：

• 首行是属性参数；
• 后续$(m)$行是决策树模型的结构数据；
• 再后续$(n)$行是待推理的样本。

$1$. 属性参数（首行）

包含 $3$个$int$类数据，分别表示：

• 特征数量 $(f)$，
• 树模型的节点数 $(m)$，
• 待推理样本的行数$(n)$。

$2$. 决策树模型 $(T)$ $((T)$ 是 $(m)$ 行$5$ 列的矩阵$)$

• 一行数据表示决策树的一个节点，首行表示根节点(即$(T)$矩阵中的第$0$ 行)，共有$(m)$个节点。
• $5$个列分别表示：
  1. 分裂特征的下标
  2. 分裂特征的阈值
  3. 当前节点左子节点的行号（即 $(T)$矩阵中第几行）
  4. 当前节点右子树的行号
  5. 分类结果（即资源调配优先级）

数据类型分别为：$int, float, int, int, int$；下标和行号均从$0$开始。

• 模型结构中有意义的数据均$(\geq 0)$，无意义数据统一用$(-1)$表示。 例如：叶子节点无分裂特征，因此该字段填入$(-1)$。
• 决策规则：若样本特征的取值$(\leq)$ 分裂特征的阈值，则进入左子树，否则进入右子树。

$3.$ 待推理样本($(n)$ 行 $(f)$ 列)

• 一行数据表示一个待推理的样本；
• 每行包含$(f)$个特征，数据类型为 $float$。

输出描述

返回分类结果。 注：一行一个分类结果，数据类型为 $int$。

样例1

输入

2 5 2
0 2.5 1 2 -1
-1 -1 -1 -1 1
1 5.0 3 4 -1
-1 -1 -1 -1 2
-1 -1 -1 -1 3
1.2 3.4
5.6 6.0

输出

1
3

说明

• 第 $1$ 行：特征数量为$2$，模型节点数为$5$，待推理样本为 $2$ 条。
• 第$2$ 到 $6$ 行：决策树模型，共 $5$ 个节点。首行（第$2$行输入数据）为根节点。
• 第 $7$ 到$8$ 行：$2$ 个待推理样本，每个样本包含$2$ 个特征。

输出：两条样本的推理结果分别为 分类 1、分类 3。

样例2

输入

3 9 2
0 6.1 1 2 -1
2 7.0 3 4 -1
1 6.5 5 6 -1
-1 -1 -1 -1 1
1 10.3 7 8 -1
-1 -1 -1 -1 5
-1 -1 -1 -1 6
-1 -1 -1 -1 3
-1 -1 -1 -1 4
3.2 9.2 6.2
6.3 3.2 12.0

输出

1
5

说明

第 $1$ 行：特征数量为$3$，模型节点数为 $9$，待推理样本为 $2$条。

第$2$ 到$10$ 行：决策树模型，共$9$ 个节点。首行（第 $2$ 行输入数据）为根节点。

第$11$ 到$12$行：$2$ 个待推理样本，每个样本包含 $3$ 个特征。

输出：两条样本的推理结果分别为 分类 1、分类 5。