javascript - 如何一次创建一项树形数据结构？

Question

这是该数据结构/算法的工作方式(每行为 1 步):

 1. []
 2. [1]
 3. [1, 2]
 4. [1, 2, 3]
 5. [[1, 2, 3], [4]]
 6. [[1, 2, 3], [4, 5]]
 7. [[1, 2, 3], [4, 5, 6]]
 8. [[1, 2, 3], [4, 5, 6], [7]]
 9. [[1, 2, 3], [4, 5, 6], [7, 8]]
10. [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
11. [[[1, 2, 3], [4, 5, 6], [7, 8, 9]], [[10]]]
12. [[[1, 2, 3], [4, 5, 6], [7, 8, 9]], [[10, 11]]]
13. [[[1, 2, 3], [4, 5, 6], [7, 8, 9]], [[10, 11, 12]]]
14. [[[1, 2, 3], [4, 5, 6], [7, 8, 9]], [[10, 11, 12], [13]]]
15. [[[1, 2, 3], [4, 5, 6], [7, 8, 9]], [[10, 11, 12], [13, 14]]]
16. [[[1, 2, 3], [4, 5, 6], [7, 8, 9]], [[10, 11, 12], [13, 14, 15]]]...

• 您会注意到，在每个级别，数字都位于树中的同一级别。
• 在事情发生变化之前，每个级别的每个数组只能有 3 个项目。
• 您会注意到从第 4 步到第 5 步的过渡，它必须将数组再向下嵌套一层。
• 从第 10 步到第 11 步的过渡也进一步嵌套。
• 当每个级别获得 3 个项目时，该模式将继续嵌套。
• 如第 11 步所示，当您添加下一个项目时，它会添加到树的适当深度。
• 所有数字(实际上是任意“项目”)在树中都处于相同的深度级别。

棘手的部分是，当到达特定运行的“结束”时，如何遍历数组并将新数组插入到适当的位置？简洁地实现这一点的通用算法是什么？理想情况下，不是一种函数式算法，而是一种常规的程序/命令式算法。我的尝试是here 。本质上，这是将一个项目推送到“树数组”中，使每个项目/对象/数字在树的叶子处保持相同的深度级别。

当涉及到如何在嵌套级别更改时上下遍历树以添加新项目时，我很挣扎。

注意:我使用数字来演示它们的添加顺序。但它们不应该在最终算法中使用，它应该采用通用对象。

Answer 1

您可以为此使用递归。

首先递归到树中，始终选择最后一个条目，直到到达底部，这可以通过那里不再有子数组的事实来识别。

然后回溯阶段将用于构建一个新的子树，该子树最终将被插入到空闲位置。起初这个子树只是值本身。如果底层已经有空间，则在那里插入“子树”(实际上不是树)。

但是如果没有空间，让递归调用返回一个新值:它将是包装在数组中的值，所以像 10 变成 [10]。在调用函数中，我们上升了一级。如果那里有空间，则插入该值(在示例中为 [10])。如果那里也没有空间，则再次包装该值并将其返回给调用者。在示例中，我们将返回 [[10]]。

因此，您不断从递归树中向上回溯，并使值“更深”。在某些时候它可以被插入，从那时起该函数将只返回 undefined以便向调用者表明工作已经完成，他们应该返回 undefined还有。

在边界情况下，递归将回溯到原始调用者而没有插入值。在这种情况下，返回值将是仍然需要到达某个地方的包装值。因此，我们使整个树更深，给它一个新的根(这是添加的级别)，其中原始根成为第一个子节点，而包装的值成为第二个子节点。

这是 JavaScript 中的实现:

class Tree {
    constructor() {
        this.root = [];
    }
    add(value) {
        const recur = (node) => {
            if (Array.isArray(node[0])) { // Not yet at bottom level
                value = recur(node[node.length-1]); // Recursive call...
                if (value === undefined) return; // done: get out of recursion
            }
            if (node.length === 3) return [value]; // wrap the value to be inserted
            node.push(value); // There is room here: insert the (possibly wrapped) value
            // By returning undefined we indicate the value has been inserted
        };
        
        value = recur(this.root);
        // If tree is full, increase the depth of the tree
        if (value !== undefined) this.root = [this.root, value];
    }
}

// Demo
let tree = new Tree;
for (let i = 1; i < 16; i++) {
    tree.add(i);
    console.log(JSON.stringify(tree.root));
}

迭代版本

相同的逻辑，但没有递归。所以现在我们有一个堆栈( path ):

class Tree {
    constructor() {
        this.root = [];
    }
    add(value) {
        let node = this.root;
        let path = []; // ...from root to bottom
        while (Array.isArray(node[0])) { // Not yet at bottom level
            path.push(node); // Keep track where we come from
            node = node[node.length-1]; // Descend in the right arm of the tree
        }
        // We arrived at the bottom. Now let's find a free spot
        while (node && node.length === 3) { // While there is no room...
            value = [value]; // Wrap the value to be inserted as a tree of its own
            node = path.pop(); // Get ancestor node
        }
        // We are now ready to insert the value/subtree
        if (node) { // We found an available spot
            node.push(value);
        } else { // No spot found: tree is full. Add level at the top.
            this.root = [this.root, value];
        }
    }
}
// Demo
let tree = new Tree;
for (let i = 1; i < 16; i++) {
    tree.add(i);
    console.log(JSON.stringify(tree.root));
}