如何构建排列树优化任务排序利润计算？C++代码补全求助

核心问题分析 #

你需要构建的是排列树（每层子节点数随层级递增递减1），核心难点在于跟踪已使用的任务索引，确保每个节点分配唯一的未使用任务，同时正确处理多叉节点的创建、遍历与内存释放。

代码修改与补全 #

完整可运行代码 #

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

int n = 4;

struct node {
    int task_index = -1; // 根节点用-1标识，无对应任务
    double value = 0.0;
    struct node** next = nullptr;
};

// 构建排列树：通过used数组跟踪已分配的任务索引
void build_tree(node* current_node, int current_level, vector<bool>& used) {
    // 叶子节点：当前层级等于任务总数，无需创建子节点
    if (current_level == n) {
        return;
    }

    int child_count = n - current_level;
    current_node->next = new node*[child_count];
    int child_idx = 0;

    // 遍历所有未使用的任务，分配给当前节点的子节点
    for (int i = 0; i < n; ++i) {
        if (!used[i]) {
            current_node->next[child_idx] = new node;
            current_node->next[child_idx]->task_index = i;
            
            // 标记任务为已使用，递归构建下一层树
            used[i] = true;
            build_tree(current_node->next[child_idx], current_level + 1, used);
            used[i] = false; // 回溯，恢复任务可用状态
            
            child_idx++;
        }
    }
}

// 按层级缩进打印树结构
void print_tree(node* current_node, int current_level = 0) {
    if (!current_node) return;

    // 打印当前节点的任务索引，层级越深缩进越多
    for (int i = 0; i < current_level; ++i) {
        cout << "  ";
    }
    cout << "任务索引: " << current_node->task_index << endl;

    // 递归打印所有子节点
    if (current_node->next && current_level < n) {
        int child_count = n - current_level;
        for (int i = 0; i < child_count; ++i) {
            print_tree(current_node->next[i], current_level + 1);
        }
    }
}

// 递归删除树节点，避免内存泄漏
void delete_tree(node* current_node, int current_level = 0) {
    if (!current_node) return;

    // 先递归删除所有子节点，再释放当前节点的子节点数组
    if (current_node->next && current_level < n) {
        int child_count = n - current_level;
        for (int i = 0; i < child_count; ++i) {
            delete_tree(current_node->next[i], current_level + 1);
            delete current_node->next[i];
        }
        delete[] current_node->next;
    }
}

int main() {
    node* root = new node;
    vector<bool> used(n, false); // 初始化所有任务为未使用状态

    build_tree(root, 0, used);
    print_tree(root);
    delete_tree(root);
    delete root;

    return 0;
}

关键修改说明 #

• 任务索引跟踪：用vector<bool> used数组记录已分配的任务，递归时通过回溯恢复状态，确保每个子节点分配唯一的未使用任务索引。
• 节点索引赋值：根节点task_index设为-1，第一层子节点分配0~n-1的未使用索引，后续层级依次分配剩余未使用的索引，完全匹配排列树的逻辑。
• 递归逻辑修正：调整终止条件为current_level == n（叶子节点），此时不再创建子节点；子节点数量由n - current_level计算，确保每层子节点数递减1。
• 内存管理：delete_tree先递归删除所有子节点，再释放当前节点的子节点数组，彻底避免内存泄漏。

运行效果（n=4时） #

输出的树结构层级清晰，每层子节点对应未被选中的任务索引：

任务索引: -1
  任务索引: 0
    任务索引: 1
      任务索引: 2
      任务索引: 3
    任务索引: 2
      任务索引: 1
      任务索引: 3
    任务索引: 3
      任务索引: 1
      任务索引: 2
  任务索引: 1
    任务索引: 0
      任务索引: 2
      任务索引: 3
    任务索引: 2
      任务索引: 0
      任务索引: 3
    任务索引: 3
      任务索引: 0
      任务索引: 2
  ...（剩余子树结构类似）

利润计算集成 #

你可以在创建子节点后，直接集成任务价值计算逻辑，例如：

// 在创建子节点后计算当前任务的价值
current_node->next[child_idx]->value = calculate_profit(current_level + 1, i);

其中calculate_profit(int position, int task_idx)是你已掌握的、与任务位置相关的价值计算函数。

内容的提问来源于stack exchange，提问作者Y.S.