如何判断一棵B-Tree是否为二叉树（每个节点至多有两个子节点）-java教程-PHP中文网

如何判断一棵B-Tree是否为二叉树（每个节点至多有两个子节点）

本文详解如何用递归方法准确判断b-tree是否满足二叉结构约束：即每个非空节点的子节点数不超过2，并正确处理叶节点终止条件，避免因忽略叶子情况导致恒返回false的常见错误。

本文详解如何用递归方法准确判断b-tree是否满足二叉结构约束：即每个非空节点的子节点数不超过2，并正确处理叶节点终止条件，避免因忽略叶子情况导致恒返回false的常见错误。

在B-Tree中，“是否为二叉树”并非指其符合标准B-Tree定义（如阶数、关键字数量等），而是特指结构上的二叉性：即每个节点的子节点数量 ≤ 2。注意，这与经典二叉搜索树（BST）不同——我们不关心键值顺序，只校验子节点数组长度是否始终为0、1或2（且不能超过2）。

原实现存在关键逻辑缺陷：它强制要求每个节点必须恰好有2个子节点（node.children.length != 2 → return false），导致所有叶节点（children.length == 0）和单子节点（length == 1）均被判定为“非法”，从而整棵树必然返回 false。而实际上，叶节点是合法的终点，应返回 true；仅当子节点数 > 2（如3、4…）时才违反二叉约束。

以下是修正后的递归实现：

public boolean isBinary() {
    return isBinary(root);
}

private boolean isBinary(BNode node) {
    // 叶节点：无子节点 → 符合二叉约束
    if (node.children.length == 0) {
        return true;
    }
    // 违反约束：子节点数超过2
    if (node.children.length > 2) {
        return false;
    }
    // 子节点数为1或2：递归检查每个非空子树
    // 注意：children数组可能含null元素（取决于实现），但此处按题设“仅长度有意义”
    for (BNode child : node.children) {
        if (child != null && !isBinary(child)) {
            return false;
        }
    }
    return true;
}

⚠️ 重要注意事项：

若 BNode.children 是固定长度数组（如长度为m+1的B-Tree典型实现），需结合实际结构判断有效子节点数（例如通过node.numChildren字段），而非直接依赖children.length；
若叶节点由特殊类型（如LeafNode）表示且无children字段，应在递归前做类型检查或统一接口设计；
本解法默认children为对象数组，允许null占位；若实现中子节点严格连续存储，建议额外维护子节点计数器以提升鲁棒性。