时间戳

首页 > 解决方案 > 如何增量构建一个数组树，其中每个数组只能有 1、2、4、8、16 或 32 个项目？

javascript - 如何增量构建一个数组树，其中每个数组只能有 1、2、4、8、16 或 32 个项目？

问题描述

在高层次上，我想做的是建立一个“树数组”结构，就像这个答案中的树数组结构一样，还有一个额外的约束：每个数组只能是 1、2、4、8，长度为 16 或 32 个项目/数组。

从外部看，它就像一个数组（具有所有常规数组方法），但它是由一棵树构成的。添加了约束，即树中的每个节点只能有 1、2、4、8、16 或 32 个节点（2 的幂）。节点可以是内部（“容器”）节点、基节点或叶节点。为了实现这些数字 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，它就会嵌套，就像这个 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,-]],[[]]]
...

这意味着数组树中的每个“对象”（每个项目，可以是任何东西，甚至是数组！）在树中处于同一级别（在同一深度），就像链接的简化 MVP 问题/答案一样.

我试过这样做，但我很快就迷路了。我很想看看这是如何以迭代方式完成的（即，而不是递归），但如果你也想添加递归，递归也是一个不错的选择。（也可以在该要点的底部找到一些有用的方法。）

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

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

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

我在这里修改了链接的答案以非常接近我的想象，但还没有。

标签： javascriptarraysalgorithmtree

解决方案

我也null选择了内部级别，就像你建议的那样：

我想它也可能是null( -)，任何一个都可以，无论哪个更容易，所以它也可能是这个。

你还写道：

每个项目，可以是任何东西，甚至是数组！

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

由于数组将被填充null值，JavaScript 的length属性不会提供关于在何处插入下一项的线索。为避免代码必须反复迭代此类数组以查找 first 的索引null，我决定跟踪位于最后插入项的路径上的数组的数据大小（因此不计算填充）。null这样我就有了树的高度（作为这条路径的长度），以及下一个null可用于存储新项目的信息。

这种基于路径的解决方案还有一个优点，即如果您真的想要，您可以实际存储项目。null虽然无法与填充区分开来，但在此之后添加另一个非空值时，您会注意到差异。先前添加的null项目将保持不变。

这是实现：

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));
}

推荐阅读