帮助树递归 [英] Help with tree recursion

问题描述

我有一个Person类，我想创建一个树。这是Person类的contsructor。

I have a Person class, and I want to create a tree. Here is the contsructor for the Person class.

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

c1是左边的孩子，c2是右边的孩子。所以说我像这样创建三个人：

c1 is the child on the left, and c2 is the child on the right. And so say I create three Persons like so:

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和他的权利c是卡尔，依此类推。

So here you say Adam is the root node, and Adam's left child is b, which is Barbara and his right c which is Carl, and so on.

所以我想做的是写一个计数方法，计算包括此。所以a.count（）会返回6（如果Person f没有任何子节点）。

So what I want to do is write a count method, that counts the number of children including this. So a.count() would return 6 (if Person f doesnt have any children).

所以这里是我的代码：

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();
}

我在纸上试了好几​​次，它应该是正确的结果，但是当我实际运行它时由于某些原因它已经关闭。

I ran this on paper several times, and it should come up with the correct result, but it's off by a few for some reason when I actually run it.

推荐答案

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

Your code returns 0 if one of the children are null. This is incorrect because you don't account for the other child, or this. The count should always be >= 1 because you always have at least one node in the tree.

，如果您发现一个孩子 null ，则无法立即返回。你需要计算另一个孩子（如果存在）。

Also, you can't return right away if you see that one child is null. You need to count the other child too (if it exists).

以下是我将如何实现它：

Here is how I would implement it:

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;
}

您需要为这两个孩子负责，即使其中一个孩子 null 。

You need to account for both children, even if one of them is null.

这篇关于帮助树递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！