如何在每个数组只能包含1、2、4、8、16或32项的情况下增量构建数组树？ [英] How to incrementally build an array tree where each array can only have 1, 2, 4, 8, 16, or 32 items?

问题描述

在较高级别上，我要做的是构建一个树形数组和结构，与tree array structure in this answer中的完全相同，但有一个额外的限制：每个数组的长度只能是1、2、4、8、16或32个项目/数组。

从外部看，它的行为类似于一个数组(具有所有常规的数组方法)，但它是由树构造的。增加了树中的每个节点只能有1、2、4、8、16或32个节点(2的幂)的约束。这些节点可以是内部(容器&Q；)节点、基础节点或叶节点。为了获得这些数字1、2、4、8、16和32，对于项，您需要在添加项之后的尾部位置添加一个空占位符，而对于容器(数组)，只需添加额外的数组即可达到该级别。

现在我将演示数据结构在其开发的不同关键点是什么样子。

下面是前32项的布局：

[]
[1]
[1,2]
[1,2,3,-]
[1,2,3,4]
[1,2,3,4,5,-,-,-]
[1,2,3,4,5,6,-,-]
[1,2,3,4,5,6,7,-]
[1,2,3,4,5,6,7,8]
[1,2,3,4,5,6,7,8,9,- ,- ,- ,- ,- ,- ,- ]
[1,2,3,4,5,6,7,8,9,10,- ,- ,- ,- ,- ,- ]
[1,2,3,4,5,6,7,8,9,10,11,- ,- ,- ,- ,- ]
[1,2,3,4,5,6,7,8,9,10,11,12,- ,- ,- ,- ]
[1,2,3,4,5,6,7,8,9,10,11,12,13,- ,- ,- ]
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,- ,- ]
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,- ]
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,- ,- ,- ,- ,- ,- ,- ,- ,- ,- ,- ,- ,- ,- ,- ]
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,- ,- ,- ,- ,- ,- ,- ,- ,- ,- ,- ,- ,- ,- ]
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,- ,- ,- ,- ,- ,- ,- ,- ,- ,- ,- ,- ,- ]
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,- ,- ,- ,- ,- ,- ,- ,- ,- ,- ,- ,- ]
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,- ,- ,- ,- ,- ,- ,- ,- ,- ,- ,- ]
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,- ,- ,- ,- ,- ,- ,- ,- ,- ,- ]
...
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,...,32]

一旦达到32，它就会筑巢，与this question/answer完全一样。然后它开始像这样构建：

[[1,2,...,32],[1]]
[[1,2,...,32],[1,2]]
[[1,2,...,32],[1,2,3,-]]
[[1,2,...,32],[1,2,3,4]]
[[1,2,...,32],[1,2,3,4,5,-,-,-]]
...
[[1,2,...,32],[1,2,3,4,5,...,32]]

然后此嵌套级别的第三个数组创建一个额外的空数组：

[[1,2,...,32],[1,2,..,32],[1],[]]
[[1,2,...,32],[1,2,..,32],[1,2],[]]
[[1,2,...,32],[1,2,..,32],[1,2,3,-],[]]
[[1,2,...,32],[1,2,..,32],[1,2,3,4],[]]
[[1,2,...,32],[1,2,..,32],[1,2,3,4,5,-,-,-],[]]
...
[[1,2,...,32],[1,2,..,32],[1,2,3,4,5,...,32],[]]

末尾额外的[]数组的原因是，顶级数组有4个子数组。我猜也可能是null(-)，两个都行，比较容易的都行，所以也可能是这个。

[[1,2,...,32],[1,2,..,32],[1,2,3,4,5,...,32],-]

所以现在我们填充第二层数组，每个数组都有32项：

[[1,2,...,32],[1,2,..,32],...,[1,2,...,32]]

接下来会发生什么，它会再次筑巢！

[[[1,2,...,32],[1,2,..,32],...,[1,2,...,32]],[[1]]]
[[[1,2,...,32],[1,2,..,32],...,[1,2,...,32]],[[1,2]]]
[[[1,2,...,32],[1,2,..,32],...,[1,2,...,32]],[[1,2,3,-]]]
[[[1,2,...,32],[1,2,..,32],...,[1,2,...,32]],[[1,2,3,4]]]
[[[1,2,...,32],[1,2,..,32],...,[1,2,...,32]],[[1,2,3,4,5,-,-,-]]]
[[[1,2,...,32],[1,2,..,32],...,[1,2,...,32]],[[1,2,3,4,5,...,32]]]
[[[1,2,...,32],[1,2,..,32],...,[1,2,...,32]],[[1,2,...,32]],[[1]],[[]]]
[[[1,2,...,32],[1,2,..,32],...,[1,2,...,32]],[[1,2,...,32]],[[1,2]],[[]]]
[[[1,2,...,32],[1,2,..,32],...,[1,2,...,32]],[[1,2,...,32]],[[1,2,3,-]],[[]]]
...

这意味着数组树中的每个对象(每个项目，可以是任何项，甚至数组！)都位于树中的同一级别(深度相同)，与linked simplified MVP question/answer完全相同。

我有tried to do it但我很快就迷路了。我很想看看这是如何以迭代的方式完成的(例如，代替递归)，但是如果您也想添加它，递归也会是一个很好的尝试。(在这个要点的底部也可以找到一些有用的方法。)

注意：我在数组中使用的数字不是实际值。实际值将是任何JavaScript对象(数组、对象、数字、字符串、日期等)。我只是用数字来简洁地显示位置以及它们之间的关系。😊

它应该使用链接问题中的单个方法：tree.add(object)、tree.push(object)或push(tree, object)等。

还请注意，为了简单起见，我在JavaScript中请求这样做。我知道JavaScript数组是动态调整大小的，但假装它们不是。我将在一种定制编程语言中使用它，该语言像C一样具有固定大小的数组，所以我想知道当您必须重新创建数组时它是如何工作的，因为它们需要增大大小。

我modified the linked answer here非常接近我的想象，但仍未达到。

推荐答案

按照您的建议，我也选择了内部级别的null选项：

我猜也可能是null(-)，两个都行，比较容易的都行，所以也可能是这个。

您还写道：

每一项，可以是任何项甚至数组！

对于您的上一个问题，我使用了数组检查来检测树中的项目是否为树叶，但由于在这里不起作用，我在Tree类中添加了一个跟踪树高度的属性。

由于数组将用null值填充，因此JavaScript的length属性不会给出在哪里插入下一项的线索。为了避免代码必须重复迭代这样的数组才能找到第一个null的索引，我决定跟踪指向最后插入项的路径上的数组的数据大小(因此不计算null填充)。这样，我既有树的高度(此路径的长度)，也有可用于存储新项目的下一个null所在位置的信息。

这种基于路径的解决方案还有一个优点，如果您真的想存储null项，可以实际存储。虽然无法从填充中区分出来，但一旦在填充之后添加另一个非空值，您就会注意到不同之处。以前添加的null项将保持原样。

实现如下：

数据-lang="js"数据-隐藏="假"数据-控制台="真"数据-巴贝尔="假">

class Tree {
    constructor(maxPower=5) {
        this.root = null;
        this.maxSize = 2**maxPower; // default: 32
        // Path of rightmost data-branch from bottom to top:
        //   It will have {node, size} objects
        this.rightPath = []; 
    }
    add(value) {
        for (let level of this.rightPath) {
            let {node, size} = level;
            if (size < this.maxSize) {
                // Double array size when there is no more room:
                if (size === node.length) node.push(...Array(size).fill(null));
                node[size] = value; // This is the empty spot to use
                level.size++; // Update size on the path
                return;
            }
            // If we get here, there was no available spot at this level
            // Wrap the value so when it gets inserted at a higher level,
            //    the core value will still end up at the bottom level.
            value = [value];
            // Update path accordingly (for use in future `add` calls)
            level.node = value;
            level.size = 1;
        }
        // If we get here, there was no available spot in the tree: 
        //    add a level at the top
        this.root = this.root ? [this.root, value] : [value];
        // Update path accordingly
        this.rightPath.push({ node: this.root, size: this.root.length });
    }
}

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

这篇关于如何在每个数组只能包含1、2、4、8、16或32项的情况下增量构建数组树？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！