无序树的层序插入问题：现有代码无法按层级插入节点

问题描述 #

我尝试用BFS向无序树添加节点，树的规则是：每个节点最多存储3个用户名，最多拥有3个子节点。但当前代码没有层级感知能力，会盲目把节点插入到最右侧节点，无法实现预期的层级插入逻辑——比如想把节点插入到第2层的指定节点下，实际却插到了最右侧节点。

原问题代码 #

const fs = require('fs');
trees = [];
init_tree("core", "founder_user")
// level 0
add_user(trees[0], "user")
add_user(trees[0], "user")
// level 1
add_user(trees[0], "user")
add_user(trees[0], "user")
add_user(trees[0], "user")
add_user(trees[0], "user")
add_user(trees[0], "user")
add_user(trees[0], "user")
add_user(trees[0], "user")
add_user(trees[0], "user")
add_user(trees[0], "user")
// level 2
// level 2 under node 1... ideally
add_user(trees[0], "user")
add_user(trees[0], "user")
add_user(trees[0], "user")
add_user(trees[0], "user")
add_user(trees[0], "user")
add_user(trees[0], "user")
add_user(trees[0], "user")
add_user(trees[0], "user")
add_user(trees[0], "user")
// level 2 under middle node ideally (yet it's under right most
add_user(trees[0], "user")
add_user(trees[0], "user")
add_user(trees[0], "user")
add_user(trees[0], "user")
add_user(trees[0], "user")
add_user(trees[0], "user")
add_user(trees[0], "user")
add_user(trees[0], "user")
add_user(trees[0], "user")
fs.writeFileSync('./data/test.json', JSON.stringify(trees[0], null, 2));


/**
 * Initialize tree
 */
function init_tree(title, user_addr) {
    node = {
        title: title,
        users: [
            user_addr
        ],
        "children": [
        ]
    }
    trees[trees.length] = node;
}
/**
 * Add node
 * @param {*} node 
 * Node to add from
 */
function add_node(node) {
    node.children.push({
        title: "X",
        users: [],
        children: []
    })
}
/**
 * Uses a recursive queue
 * @param {*} root_node 
 * @param {*} user_addr 
 * @returns 
 */
function add_user(root_node, user_addr) {
    queue = []
    queue.push(root_node)

    isAdded = false
    parent_node = root_node

    while(!isAdded) {
        // BASE CASE 0: queue is empty, add and push a new node.
        if (queue.length == 0) {
            add_node(parent_node);
            queue.push(parent_node.children[parent_node.children.length-1]);
        }
        node = queue.pop()
        // BASE CASE 1: current node is not at capacity
        // SOLUTION: add user!
        if (node.users.length < 3) {
            node.users[node.users.length] = user_addr
            isAdded = true;
        // Recursive cases: push children nodes
        } else {  
            
            for (node_child of node.children) {
                queue.push(node_child)
            }
            if (parent_node.children.length == 3) {
                parent_node = node
            }
        } 
    }
    return 1;
}

问题根源分析 #

1. 队列操作错误：用pop()从队列取元素，实际把BFS变成了DFS，导致优先处理最右侧的深层节点
2. 父节点追踪逻辑混乱：parent_node的更新条件不合理，无法正确定位当前层级可扩展子节点的父节点
3. 层级遍历逻辑缺失：没有遵循「先填满当前层所有节点的用户，再扩展子节点进入下一层」的规则

修正后的完整代码 #

const fs = require('fs');
trees = [];
init_tree("core", "founder_user")
// level 0
add_user(trees[0], "user")
add_user(trees[0], "user")
// level 1
add_user(trees[0], "user")
add_user(trees[0], "user")
add_user(trees[0], "user")
add_user(trees[0], "user")
add_user(trees[0], "user")
add_user(trees[0], "user")
add_user(trees[0], "user")
add_user(trees[0], "user")
add_user(trees[0], "user")
// level 2
// level 2 under node 1... ideally
add_user(trees[0], "user")
add_user(trees[0], "user")
add_user(trees[0], "user")
add_user(trees[0], "user")
add_user(trees[0], "user")
add_user(trees[0], "user")
add_user(trees[0], "user")
add_user(trees[0], "user")
add_user(trees[0], "user")
// level 2 under middle node ideally (now works correctly)
add_user(trees[0], "user")
add_user(trees[0], "user")
add_user(trees[0], "user")
add_user(trees[0], "user")
add_user(trees[0], "user")
add_user(trees[0], "user")
add_user(trees[0], "user")
add_user(trees[0], "user")
add_user(trees[0], "user")
fs.writeFileSync('./data/test.json', JSON.stringify(trees[0], null, 2));


/**
 * Initialize tree
 */
function init_tree(title, user_addr) {
    node = {
        title: title,
        users: [user_addr],
        children: []
    }
    trees.push(node);
}
/**
 * Add node
 * @param {*} parentNode 
 */
function add_node(parentNode) {
    parentNode.children.push({
        title: "X",
        users: [],
        children: []
    })
}
/**
 * BFS-based user insertion with level awareness
 * @param {*} rootNode 
 * @param {*} userAddr 
 * @returns 
 */
function add_user(rootNode, userAddr) {
    let currentLevelNodes = [rootNode];

    while (true) {
        // 第一步：遍历当前层级所有节点，尝试添加用户
        for (const node of currentLevelNodes) {
            if (node.users.length < 3) {
                node.users.push(userAddr);
                return 1;
            }
        }

        // 当前层级所有节点都满了，准备扩展子节点
        let nextLevelNodes = [];
        let createdNewNode = false;

        // 遍历当前层级的每个节点，检查是否能创建新子节点
        for (const parent of currentLevelNodes) {
            if (parent.children.length < 3) {
                // 创建新子节点并添加用户
                add_node(parent);
                const newChild = parent.children[parent.children.length - 1];
                newChild.users.push(userAddr);
                createdNewNode = true;
                break;
            } else {
                // 该父节点子节点已满，把子节点加入下一层队列
                nextLevelNodes.push(...parent.children);
            }
        }

        if (createdNewNode) {
            break;
        }

        // 当前层级所有父节点都满3个子节点，进入下一层级
        currentLevelNodes = nextLevelNodes;
    }
}

修正说明 #

1. 严格层级遍历：先遍历当前层所有节点，优先填满每个节点的用户位，只有当前层所有节点都满了，才会扩展子节点
2. 正确的子节点扩展逻辑：当需要扩展时，按顺序为当前层的父节点创建子节点（最多3个），保证插入到指定层级的对应节点下
3. 逻辑简化：去掉混乱的parent_node追踪，用层级节点列表直接管理遍历顺序

运行修正后的代码，生成的树结构会符合预期：第2层的用户会依次插入到第1层各个节点的子节点下，而非全部堆到最右侧节点。

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