迭代中序遍历 B 树

Question

我的最终目标是做一个findKthElement函数，我能想到的唯一方法是执行迭代中序遍历，这样我就可以保留一个计数器，如果它是递归的，这显然是行不通的。我已尽力实现类似于 BST 的实现，但它不起作用，只是无限地打印相同的东西。这是我的尝试：

public void findKth() {
        Stack<BTreeNode> s = new Stack<>();
        BTreeNode current = this.root;
        while(current != null || !s.isEmpty()) {
            int i;
            for(i = 0; i < current.numNodes; i++) {
                if(!current.isLeaf) {
                    s.push(current);
                    current = current.children[i];
                }
            }
            current = s.pop();
            for(int j = 0; j < current.numNodes; j++) {
                System.out.println(current.keys[j].getName());
            }
        }
    }

Answer 1

keep a counter, which obviously doesn't work if its recursive

在递归解决方案中保留一个计数器没有问题。您只需要确保它是一个可变引用。例如：

public class Counter {
    private int count;
    public boolean complete() { return count == 0; }
    public void decrement() { count--; }
}

Optional<Node> findKthChild(Node node, Counter counter) {
    if (counter.isLeaf()) {
        if (counter.complete())
            return Optional.of(node);
        counter.decrement();
    } else {
        for (Node child: getChildren()) {
            Optional<Node> kthChild = findKthChild(child, counter);
            if (kthChild.isPresent())
                return kthChild;
        }
    }
    return Optional.empty();
}

如果您熟悉流，内部 for 循环可能是：

return getChildren().stream()
    .map(ch -> findKthChild(ch, counter))
    .filter(Optional::isPresent)
    .findFirst().orElse(Optional.empty());

Answer 2

这是家庭作业的味道。人们应该尝试通过用笔和纸手动跟踪所需的步骤来解决它。

我并不是说下面的代码是正确的或者很好。

表示中序遍历，深度优先，需要返回第i^th个子分支继续下一个子节点

为此，我使用新的 record class 作为堆栈元素，class 仅包含 BTreeNode node 和 int index.

public String findKth(int k) {
    record NodePos(BTreeNode node, int index) {};
    Stack<NodePos> stack = new Stack<>();
    stack.push(new NodePos(this.root, -1);
    while (!stack.isEmpty()) {
        NodePos pos = stack.pop();
        pos = new NodePos(pos.node, pos.index + 1);
        if (pos.index >= pos.node.numNodes) { // Past end of child nodes.
            continue;
        }
        // Sub-branch:
        if (!pos.node.isLeaf) {
            stack.push(new NodePos(pos.node.children[pos.index], -1);
            continue;
        }
        // Key:
        if (pos.index + 1 >= pos.node.numNodes) { // Past end of child keys.
            continue;
        }
        System.console().printf("%d. %s%n", k, pos.node.keys[pos.index]);
        if (k <= 0) {
            return pos.node.keys[pos.index];
        }
        --k;
        stack.push(pos);
    }
}

一个节点(node.keys)中有numNodes个子分支(node.children)和numNodes - 1个键。

当你在第i个子分支时，可以先继续子树，当不够时（递减k仍大于0），再继续i-1 个键。

如您所见，当不手动执行代码时，很难阅读它。为此，自己解决这些问题是非常宝贵的建议。

顺便说一句，递归解决方案更简单。

好的，一个可行的解决方案

我上面的回答是想思考的，肯定不对，由于 OP 没有表现出认真考虑过该算法，给定操作代码。但是明显是有功夫的。

因此是一个可读的递归解决方案。仍然以一种不能作为自己的功课还给别人。

static class BTreeNode {
    int numNodes;
    boolean isLeaf;
    BTreeNode[] children;
    int[] keys;

    BTreeNode(int... keys) {
        numNodes = keys.length + 1;
        this.keys = keys.clone();
        isLeaf = true;
    }

    public void addChildren(BTreeNode... children) {
        assert children.length == numNodes;
        this.children = children.clone();
        isLeaf = false;
    }
}

public static OptionalInt findKth(BTreeNode node, AtomicInteger k) {
    if (node == null || k.get() < 0) {
        return OptionalInt.empty();
    }
    for (int i = 0; i < node.numNodes; ++i) {
        if (!node.isLeaf) {
            OptionalInt result = findKth(node.children[i], k);
            if (result.isPresent()) {
                return result;
            }
        }
        if (i + 1 < node.numNodes) {
            int j = k.getAndDecrement();
            System.out.printf("%d. %s%n", j, node.keys[i]);
            if (j <= 0) {
                return OptionalInt.of(node.keys[i]);
            }
        }
    }
    return OptionalInt.empty();
}

public static void main(String[] args) {
    //
    //       (4       8        12)
    // (1 2 3) (5 6 7) (9 10 11) (13 14 15)
    BTreeNode n1to3 = new BTreeNode(1, 2, 3);
    BTreeNode n5to7 = new BTreeNode(5, 6, 7);
    BTreeNode n9to11 = new BTreeNode(9, 10, 11);
    BTreeNode n13to15 = new BTreeNode(13, 14, 15);
    BTreeNode root = new BTreeNode(4, 8, 12);
    root.addChildren(n1to3, n5to7, n9to11, n13to15);

    OptionalInt key5 = findKth(root, new AtomicInteger(5));
    System.out.println("The result is " + key5.orElse(-1));
}

按顺序遍历 B 树，递减请求的 k 直到达到 0。按顺序遍历 numNodes 个子树分支和 numNodes - 1 个键需要一个 for+if.

AtomicInteger 用于有一个计数器，它是 findKth 的结果，否则需要一个输入参数 k，以及 return 上 k 的一个新值。这是可以做到的。

优化：如果知道整个子树中的元素数量，就可以跳过访问子树。对于将是 numNodes 的叶节点。

迭代中序遍历 B 树

Iterative Inorder Traversal B-Tree

java

b-tree

inorder