当树节点具有子树大小时，如何按索引返回树节点

Question

假设我有这段演示数据：

{
size: 100,
type: 'container',
list: [
{
size: 30,
type: 'container',
list: [
{
size: 10,
type: 'leaf',
list: [1,2,3,4,5,6,7,8,9,10]
},
{
size: 15,
type: 'leaf',
list: [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]
},
{
size: 25,
type: 'leaf',
list: [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25]
}
]
},
{
size: 50,
type: 'container',
list: [
{
size: 20,
type: 'leaf',
list: [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20]
},
{
size: 25,
type: 'leaf',
list: [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25]
},
{
size: 25,
type: 'leaf',
list: [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25]
}
,
{
size: 30,
type: 'leaf',
list: [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30]
}
]
},
{
size: 20,
type: 'container',
list: [
{
size: 5,
type: 'leaf',
list: [1,2,3,4,5]
},
{
size: 15,
type: 'leaf',
list: [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]
}
]
}
]
}

注意，我只是填写了所谓的"；叶子；使用整数显示其数组位置的节点。但它们可以填充任何JavaScript对象(数组、对象、字符串、数字等(。叶节点最多可以有32个项，但我认为这对这个问题并不重要。容器节点也只能有32个直接子节点

你怎么说getLeafContaining(tree, index)，它会向你返回在全局index上有项目的叶，以及相对索引。我说"；全球指数"；因为这是叶节点的索引，如果要将所有叶节点视为连续的。

到目前为止，我所做的是：

const getLeafContaining = (tree, index) => {
if (index > tree.size - 1) {
return { node: null, index: -1 }
}
let nodes = [tree]
let startSize = 0
a:
while (true) {
b:
for (let i = 0, n = nodes.length; i < n; i++) {
let node = nodes[i]
let endSize = startSize + node.size
if (startSize <= index && index <= endSize) {
if (node.type == 'container') {
nodes = node.list
break b
} else {
let relativeIndex = index - startSize
return { node, index: relativeIndex }
}
} else {
startSize = endSize
}
}
}
}
const tree = {
size: 100,
type: 'container',
list: [
{
size: 30,
type: 'container',
list: [
{
size: 10,
type: 'leaf',
list: [1,2,3,4,5,6,7,8,9,10]
},
{
size: 15,
type: 'leaf',
list: [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]
},
{
size: 25,
type: 'leaf',
list: [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25]
}
]
},
{
size: 50,
type: 'container',
list: [
{
size: 20,
type: 'leaf',
list: [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20]
},
{
size: 25,
type: 'leaf',
list: [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25]
},
{
size: 25,
type: 'leaf',
list: [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25]
}
,
{
size: 30,
type: 'leaf',
list: [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30]
}
]
},
{
size: 20,
type: 'container',
list: [
{
size: 5,
type: 'leaf',
list: [1,2,3,4,5]
},
{
size: 15,
type: 'leaf',
list: [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]
}
]
}
]
}
console.log(getLeafContaining(tree, 22))

这似乎是正确的，但我说不出来。如何有力地实现这一点？

Answer 1

不，这是不正确的，index <= endSize应该是index < endSize。在最坏的情况下，这将导致空节点上的无限循环。

此外，递归解决方案会比迭代版本简单得多：

const getLeafContaining = (tree, index) => {
if (index < tree.size) {
if (node.type == 'leaf') {
return { node, index };
} else if (node.type == 'container') {
let before = 0
for (const node of nodes) {
const after = before + node.size;
if (index < after) {
return getLeafContaining(node, index - before);
}
before = after;
}
}
}
return { node: null, index: -1 }
}

累积before和的替代方案是递减index:

for (const node of nodes) {
if (index < node.size) {
return getLeafContaining(node, index);
}
index -= node.size;
}