如何一次创建一个树数据结构? [英] How do you create this tree data structure one item at a time?

问题描述

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

Here is the way this data structure / algorithm should work (each line is 1 step):

 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所示，当您添加下一项时，它会被添加到树的适当深度.
• 所有数字(实际上是任意"items")都在树中处于相同的深度级别.

棘手的部分是，当您到达终点"时，在特定运行中，如何遍历数组并将新数组插入适当的位置?简洁地实现这一目标的通用算法是什么?理想情况下，不是功能性算法，而是常规的程序/命令性算法.我的尝试是此处.从本质上讲，这是将项目推入树数组"中，使每个项目/对象/编号在树的叶子处保持在相同的深度级别.

The tricky part is, when you reach the "end" of a particular run, how do you traverse the arrays and insert the new arrays in the appropriate spots? What is the general algorithm to implement this concisely? Ideally not a functional algorithm but a regular procedural/imperative one. My attempt is here. Essentially this is pushing an item in a "tree array", keeping every item/object/number at the same depth level at the leaves of the tree.

在嵌套级别更改时，如何在树上上下移动以添加新项目时，我感到很挣扎.

I am struggling when it comes to how to traverse up and down the tree to add a new item when the nesting level changes.

注意:我使用数字来说明添加它们的顺序.但是，不应在最终算法中使用它们，而应使用通用对象.

推荐答案

您可以为此使用递归.

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

First recurse into the tree, always choosing the last entry, until you reach the bottom, which can be recognised by the fact that there are no more subarrays there.

然后，回溯阶段将用于构建新的子树，该子树最终将被插入到空闲位置.首先，此子树只是值本身.如果在底层已经有空间，则插入子树".(实际上不是一棵树).

Then the backtracking phase will be used to build a new subtree which will eventually be inserted at a free spot. At first this subtree is just the value itself. If there is already room at the bottom level, insert the "subtree" (which is not really a tree) there.

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

But if there is no room, let the recursive call return a new value: it will be the value wrapped in an array, so like 10 becomes [10]. In the calling function we are one level up. If there is room over there, then insert that value (in the example that would be [10]). If there is no room there either, then wrap the value again and return it to the caller. In the example we would return [[10]].

因此，您继续从递归树中向上回溯，并使值"deeper"更深.在某个时候可以将其插入，此后函数将仅返回 undefined ，以便向调用方指示作业已完成，并且他们应仅返回 undefined .

And so you keep backtracking upwards out of the recursion tree, and making the value "deeper". At some point it can be inserted, and from then onwards the function will just return undefined so to indicate to the caller that the job has already been done, and they should just return undefined also.

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

In a boundary case, the recursion will backtrack to the original caller without having inserted the value. In that case the return value will be the wrapped value that still needs to go somewhere. So then we make the whole tree deeper, giving it a new root (this is the added level), where the original root becomes the first child, and the wrapped value becomes the second child.

这是JavaScript的实现:

Here is an implementation in 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 ):

The same logic, but without recursion. So now we have a stack (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));
}

这篇关于如何一次创建一个树数据结构?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！