无序树上的级别顺序插入

Question

我正在尝试使用广度优先搜索将节点添加到无序树

树：无序 节点：每个节点将3个数据点分组在一起，这些数据点是用户名 子节点：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 (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
 * https://www.studytonight.com/post/insertionadding-a-new-node-in-a-binary-tree-data-structure
 * @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;
}

Answer 1

我所要做的就是添加一个变量： 第一个非完整节点

因为它以呼吸优先的方式进行搜索，所以它会找到要添加到的正确节点。