如何在每个数组只能包含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?

查看:17
本文介绍了如何在每个数组只能包含1、2、4、8、16或32项的情况下增量构建数组树?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

在较高级别上,我要做的是构建一个树形数组和结构,与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屋!

查看全文
相关文章
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆