通过树递归计算性别

Question

我有一个具有以下构造函数的 Person 类：

public Person(String name, int age, char gender, Person c1, Person c2)

其中 c1 是左孩子，c2 是右孩子。我想编写一个方法来计算与给定性别（M 或 F）匹配的人数：

public int countGender(char gen)
{
    int count=0;
    if (this.gender==gen){
        count++;
    }
    if (child1!=null){
        if (child1.gender==gen){
            count+=1+child1.countGender(gen);
        }
        else count+=child1.countGender(gen);
    }
    if (child2!=null){
        if (child2.gender==gen){
            count+=1+child2.countGender(gen);
        }
        else count+=child2.countGender(gen);
    }
    return count;
}

我已经尝试了几乎所有方法。我很难想象每次函数调用自身时会发生什么。会重置吗？或者因为我使用的是+=，它会在重置之前保存自己吗？我的方法还有什么问题吗？请帮助我理解。

Answer 1

每次调用 countGender 都有自己的 count 变量，初始化为零。

您不需要检查一个人的两个孩子的性别，因为对每个孩子的递归调用都可以做到这一点。例如：

public int countGender(char gen) {

    int count = 0;

    if (this.gender == gen) {
        count++;
    }

    if (child1 != null) {
        count += child1.countGender(gen);
    }

    if (child2 != null) {
        count += child2.countGender(gen);
    }

    return count;
}

您可以将 p.countGender(...) 视为在其 p 所在的树中为您提供指定性别的人数。根。

这是以下各项之和：

• 1，如果 p 性别正确，则
• p 的 左 子树中性别正确的人数（如果有的话）
• p 的右子树中性别正确的人数（如果有的话）。

上面给出的代码对人物树执行深度优先遍历。它实际上是一个前序遍历（处理根节点，然后处理它的左子树和右子树）。也可以进行中序遍历（左子树，然后节点本身，然后右子树），或后序遍历（左子树，然后右子树，然后节点本身）。

对于计算节点，正如您在此处所做的那样，顺序实际上并不重要：结果将是相同的。但对于某些操作，例如显示树中的所有人员，它确实很重要。

Answer 2

我认为你加 1 的次数太多了。每次子进程运行 countGender 时，如果性别正确（第 5 行），计数就会加 1。但是，您在第 9 行和第 15 行再次检查孩子的性别，尽管每个孩子都检查自己的性别。因此，你对所有事情都进行了重复计算。

至于递归，countGender 的每次调用都是不同的，并且与任何其他调用分开。每个实例的count都是内存中的一个单独的变量，并且每次都初始化为0。