algorithm - 如何以迭代方式按顺序遍历 BTree 而无需递归？

Question

我需要 B-Tree LNR 遍历(按顺序)。我找到了B树遍历的算法here 。我如何以迭代的方式实现它而无需递归？ 我找到了this question但没有答案，问题中的代码非常不清楚并且似乎不正确。至少，这不是LNR，也不适合我。 我还发现了很多简单二叉树遍历的例子，但我确实需要 B 树。

我使用 Rust，但我很高兴看到任何语言或伪代码的答案。

Answer 1

正如评论中已经提到的:如果您不想使用递归(这将是一种可行的方法)，那么您必须使用堆栈来模仿它。

该堆栈上的条目将是一对，其中包含:

• 对节点的引用，以及
• 该节点内的当前索引 (0...m-1)，其中 m 是该节点处的分支数

作为示例，我将使用以下 B 树:

...并使用它的 JSON 表示形式:

{
    "keys": [29],
    "children": [{
        "keys": [15, 21],
        "children": [{
            "keys": [11, 12]
        }, {
            "keys": [18, 20]
        }, {
            "keys": [23, 25, 27]
        }]
    }, {
        "keys": [35, 42],
        "children": [{
            "keys": [31, 33]
        }, {
            "keys": [36, 39]
        }, {
            "keys": [45, 47, 50, 55]
        }]
    }]
}

下面是 JavaScript 中 iterate 函数的实现，它按 LNR 顺序返回键上的迭代器:

function * iterate(node) {
    let stack = []; // stack of [node, child-index] pairs
    
    stack.push([node, 0]);
    while (stack.length > 0) {
        let [node, i] = stack.pop();
        if (!("children" in node)) { // bottom level has no "children" member
            for (let key of node.keys) {
                yield key;
            }
        } else if (i < node.children.length) {
            if (i > 0) {
                yield node.keys[i-1];
            }
            stack.push([node, i+1]);
            stack.push([node.children[i], 0]);
        }
    }
}

// The example B-tree:
const btree = {"keys": [29],"children": [{"keys": [15, 21],"children": [{"keys": [11, 12]}, {"keys": [18, 20]}, {"keys": [23, 25, 27]}]}, {"keys": [35, 42],"children": [{"keys": [31, 33]}, {"keys": [36, 39]}, {"keys": [45, 47, 50, 55]}]}]};

// Consume the iterator and output
console.log(...iterate(btree));