Java计算红黑树中有多少个红色节点的程序

Question

我正在构建一个程序来确定红黑树中有多少个红色节点。我已经实现了一个 RED BLACK BST，它在读取文本输入后构建树。我被困在如何计算红色节点的数量上？我知道红色节点只能靠左，红色父节点不能有红色子节点。解决这个问题的合适方法是什么？

Answer 1

递归解决方案如下所示：

public static int countRed(Node node) {
    int nbRed = 0;
    if (node == null) {
        return 0;
    }
    nbRed += countRed(node.left);
    nbRed += countRed(node.right);

    if(node.isRed()){
        nbRed++;
    }
    return nbRed;
}

已测试

我用一个简单的循环测试了你的代码：

RedBlackBST tree = new RedBlackBST();
tree.root = tree.put(null, 0, 0);

for (int i = 1; i < 10; i++) {
    tree.root = tree.put(tree.root, i, i);
}
int redTotal = tree.countRed(tree.root);

这个returns一共3个红人。如果我在调试中检查它，它是准确的。如果您觉得该值无效，那么您应该在调试中检查您的树并确定结构中无效的内容。

Java计算红黑树中有多少个红色节点的程序

Java program to calculate how many red nodes are in a Red-Black Tree

java

counting

red-black-tree

已测试