java - 帮助树递归

Question

我有一个 Person 类，我想创建一棵树。这是 Person 类的构造函数。

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

c1 是左侧的子级，c2 是右侧的子级。假设我创建了三个人，如下所示:

Person c = new Person("Carl", 50, 'M', null, f);

Person b = new Person("Barbara", 52, 'F', d, e);

Person a = new Person("Adam", 75, 'M', b, c);

所以这里你说 Adam 是根节点，Adam 的左子节点是 b，即 Barbara，右子节点是 Carl，等等。

所以我想做的是编写一个计数方法，计算包括 this 在内的子级的数量。所以 a.count() 将返回 6(如果 Person f 没有任何 child )。

这是我的代码:

public int count() // total person count including this object
{
    if(child1==null)
        return 0; //I tried return 1 for this too didnt work
    if (child2==null)
        return 0; //also tried 1 for this
    return 1+this.child1.count() +1+this.child2.count();
}

我在纸上运行了几次，它应该得出正确的结果，但当我实际运行它时，由于某种原因，它有一些偏差。

Answer 1

如果子级之一为 null，您的代码将返回 0。这是不正确的，因为您没有考虑另一个 child 或这个。计数应始终为 >= 1，因为树中始终至少有一个节点。

此外，如果您看到一个子项为 null，您也无法立即返回。您还需要计算另一个 child (如果存在)。

这是我的实现方法:

public int count() // total person count including this object
{
    int count = 1; // we count this node as 1 
    if (child1 != null) // if we have a left child, count its size
        count += child1.count();
    if (child2 != null) // if we have a right child, count its size
        count += child2.count()
    return count;
}

您需要考虑两个 child ，即使其中一个为 null。