如何在每个数组只能包含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)
等。
我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屋!