基于深度优先+从左到右规则填充N叉树的实现疑问

我要实现一个N叉树的插入函数，填充优先级规则如下：

• 尽可能在最大深度处插入节点
• 同一深度内按从左到右的顺序插入

举个例子：深度为3、包含12个节点、每个节点最多3个子节点的N叉树（对应描述的示例图）。

目前我已经实现了最大深度填充的部分，但不知道怎么处理「从左到右」的约束。以下是我写的尝试代码：

int Tree::insertcell(int data, int depth, int* done, int maxchild, TreeNode* node) {
    for(int i = 0; i < maxchild; i++){
        cout << "children: " << i << endl;
        if (node->children[i] == nullptr && depth > 0){
            node->children[i] = new TreeNode(data, maxchild); //insert new node with data
            if(i == maxchild - 1){
                (*done) = depth + 1;
            }
            this->size += 1;
            return 1;
        }
        else if(node->children[i] != nullptr && depth > 0){
            if ((*done) > 0){
                this->insertcell(data, depth - 1, done, maxchild, node);
                continue;
            }else{
                this->insertcell(data, depth - 1, done, maxchild, node->children[i]); // access
            }
            this->size += 1;
            return 1;
        }
        else if(node->children[i] == nullptr && depth == 0){
            node->children[i] = new TreeNode(data, maxchild);
            this->size += 1;
            if(i == maxchild - 1){
                (*done) += 1;
            }
            return 1;
        }
        
    }
    return 0;
}

问题分析 #

当前代码的核心问题是递归逻辑没有严格遵循「左到右遍历子节点」的顺序，且递归调用的目标节点存在错误——当done>0时递归调用了当前节点而非子节点，导致插入顺序混乱，无法满足左到右的约束。

修复思路 #

要满足「最大深度优先+左到右」的插入规则，本质是先对当前节点的所有子节点按左到右顺序做深度优先遍历，优先填充最深层的左空位。具体调整点：

1. 递归时必须严格按左到右顺序遍历子节点，先处理左子节点的深层插入，再往右推进
2. 只有当当前节点的所有子节点都已经填满到当前深度时，才在当前节点的子节点位置插入（若未达最大深度）
3. 修正done变量的逻辑，用来标记当前深度是否已填满，避免重复插入

修正后的代码 #

int Tree::insertcell(int data, int depth, int* done, int maxchild, TreeNode* node) {
    // 先尝试在当前节点的子节点的深层插入（满足最大深度优先）
    if (depth > 0) {
        for (int i = 0; i < maxchild; ++i) {
            if (node->children[i] != nullptr) {
                int result = this->insertcell(data, depth - 1, done, maxchild, node->children[i]);
                if (result == 1) {
                    this->size += 1;
                    return 1;
                }
            } else {
                // 当前子节点为空，且还有深度可走，说明深层无空位，直接在此插入
                node->children[i] = new TreeNode(data, maxchild);
                this->size += 1;
                // 若为最后一个子节点，标记当前深度已填满
                if (i == maxchild - 1) {
                    *done = depth;
                }
                return 1;
            }
        }
    } else {
        // 已达最大深度，直接在当前节点的子节点按左到右顺序插入
        for (int i = 0; i < maxchild; ++i) {
            if (node->children[i] == nullptr) {
                node->children[i] = new TreeNode(data, maxchild);
                this->size += 1;
                if (i == maxchild - 1) {
                    *done = 1;
                }
                return 1;
            }
        }
    }
    // 当前节点无空位可插入
    return 0;
}

逻辑说明 #

• 当depth>0时，先遍历每个子节点：若子节点存在，递归去其深层插入（优先填最深层）；若子节点为空，说明深层无空位，直接在此插入
• 当depth=0时，直接在当前节点的子节点按左到右顺序找第一个空位插入
• done变量标记当前深度是否已填满，避免后续重复在同一深度插入

内容的提问来源于stack exchange，提问作者hakken